《数据结构总结.docx》由会员分享，可在线阅读，更多相关《数据结构总结.docx（5页珍藏版）》请在三一文库上搜索。
1、命题说明章节第 1 章第 2 章第 3 章第 6 章第 7 章第 9 章第 10 章备注考核的重点及命题说明各种基本概念和术语(0 分 ) ；掌握算法描述和分析的方法(0 分 )线性表的逻辑结构和各种存储表示方法(0 分) ；以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算 (0 分 )栈和队列的特点 (0 分 ) ；栈在两种存储结构表示时的基本操作实现算法(0 分) ；循环队列和链队列的基本操作实现算法(0分)二叉树的各种存储结构的特点(0 分) ；二叉树各种遍历策略的递归和非递归算法(0 分 ) ；已知先序序列和中序序列或中序序列和后序序列建立二叉树的方法(0 分)
2、；二叉树的线索化过程； (0分 )树的各种存储结构及特点；(0分 )建立最优树和哈夫曼编码的方法(0分 )图的各种存储结构 (0 分 ) ；图的两种搜索路径的遍历（深度和广度）(0 分 ) ；最小生成树 (0 分 ) ；拓扑排序 (0 分 ) ；关键路径 (0 分 ) ；最短路径 (0 分 )顺序表和有序表的查找 (0分 ) ；二叉排序树的构造和查找(0 分 ) ；哈希表的构造方法 (0 分 )各种排序方法的执行过程和其依据的原则(0 分 ) ；各种排序方法时间复杂度的分析(0分 )一、单项选择（每题2 分，共 20分）1、分析下面程序段的时间复杂度：()i=1;j=1;while(i=n)i
3、=i*3;while(j=n)j+;C、O(logn)D、A、O(n+log n)B、 O(n)33O(n*log 3n)2、下面关于串的的叙述中，哪一个是不正确的：（）A、串是字符的有限序列B、空串是由空格构成的串C、模式匹配是串的一种重要运算D、串既可以采用顺序存储，也可以采用链式存储3、从逻辑上可以把数据结构分为两大类（）A动态结构、静态结构B顺序结构、链式结构C线性结构、非线性结构D初等结构、构造型结构4、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A顺序表B双链表C带头结点的双循环链表D单循环链表5、有六个元素6，5，4，3
4、，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 66、最大容量为 n 的循环队列，队尾指针是rear ，队头是 front，则队满的条件是（）A. (rear+1) MOD n=frontB. rear=frontC rear+1=frontD. (rear-l) MOD n=front7、在一个长度为 n 的顺序表中删除第 i 个元素，需向前移动（）个元素。A. nB.i-1C.n-iD.n-i+18、对一颗具有 n 个节点的树，其中所有度之和等于（）。A. nB.n-1C.
5、n-2D.n+19 、 某 二 叉 树 的 前 序 和 后 序 序 列 正 好 相 反 ， 则 该 二 叉 树 一 定 是 ：()A、高度等于其结点数B 、任意一个二叉树C 、所有节点均无左孩子D 、所有节点均无右孩子10、已知一棵完全二叉树的第6 层（根节点为第一层）有二叉树的节点个数至多是： A 、39B、528 个叶子节点，则完全C、111D、119()11、以下数据结构中，（）是非线性数据结构。A 树B字符串C队D12、设栈 N 和队列 M初始状态为空，元素1,2,3,4,5,6出栈后进队列 M，若 6 个元素出队的序列是2,4,3,6,5,1,栈依次通过栈 N，一个元素则栈 N 的容
6、量至少应该是：()A、 2B、313 、 一 棵 完 全 二 叉 树 上 有C、4D、5100个 结 点 ， 其 中 叶 子 结 点 的 个 数 是（ ）A 50B 51C52D4914、有关二叉树下列说法正确的是（）A二叉树的度为2BC二叉树中至少有一个结点的度为一棵二叉树的度可以小于22D 二叉树中任何一个结点的度都为 215 、一 棵二叉树的前 序遍 历序列为 ABCDEFG，它 的中序遍历序列可 能是（ ）ACABDEFGBABCDEFGC DACEFBGDADCFEG二、填空题（每题2 分，共 20分）1、设一行优先顺序存储的数组A55，A00的地址为 1000，且每个元素占2 个存
7、储单元，则A23的地址为。2、设循环队列用数组AM 表示，队首、队尾指针分别是front和 rear ，则循环队列的元素个数为。3、假定一棵二叉树的结点个数为200，则它的深度最少为。4、线性表 L=（a1,a2, ,an ）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是 _。5、带头结点的循环链表L 中只有一个元素结点的条件是：_三、简答题（每题5 分，共 1 0 分）1、什么是数据的逻辑结构？数据的逻辑结构主要有哪几种基本的类型？2、线性表有哪几种存储结构？分别有哪些优点？四、综合应用题（每题5 分，共 2 0 分）1、已知一棵二叉树的先序遍历为ABEC
8、DFGHIJ，中序遍历为 EBCDAFHIGJ。（ 1）给出后序遍历序列，（2）将该二叉树转换为森林。2、设有正文 AADBAACACCDACACAADBB,字符集为 A,B,C,D, 设计一套二进制编码，使得上述正文的编码最短。3、画出该逻辑结构的结构图。S=D,R, D=a,b,c,d,e,f,g, R=,4、已知图如下：(1) 给出该图的邻接矩阵和邻接表；(2) 若从顶点 V1 出发对该图进行遍历，分别给出本图的按深度优先搜索和按广度优先搜索的顶点序列；(3) 给出拓扑排序序列 。V 1V 2V 4V 35、给出如下图深度优先和广度优先遍历序列。ABE。CD6、应用普里姆算法和克鲁斯卡尔
9、算法求图的最小生成树。（具体步骤）15V 0V 1531102V 59V 2301412V 4V 322(v0,v4),(v0,v1),(v1,v2),(v1,v3),(v1,v5)(v0,v4),(v1,v2),(v1,v3),(v1,v5),(v0,v1)7、下图为带权有向图，求：（ 1）给出拓扑排序序列；（ 2）从顶点 A 到顶点 I 的关键路径。要求：给出具体计算过程，即列出所有事件的最早和最晚开始时间，所有活动的最早和最晚开始时间。BG21610A4EI471HC542DF8、给出 a 到其他顶点的单源最短路径，根据 dijkstra算法给出计算步骤。5b3d3a1112c4e9、已
10、知有序顺序表的元素分别为：10,15,20,25,30,35,40,45,50,55,60（ 1）使用顺序查找时查找成功情况下的平均查找长度为多少？（ 2）使用折半查找方法，画出二分查找树。10、输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），（ 1）画出按元素排列顺序输入生成的一棵二叉排序树。（ 2）请写出递归算法，从小到大输出该二叉排序树的所有结点。11、设散列函数为 H(K)=K %11,解决冲突的方法分别为（ 1）线性探测法和（ 2）链地址法，试将下列关键字集合 35,67,42,21,29,86,95,47 依次插入到散列表中（画出散列表的示意图） ，散列表长度为 11。画出两种冲突解决方法的查找表。12、已知序列（ 15，35， 11，51，45， 55，60，30），进行？排序算法的每一趟的结果。五、算法设计题（每题10 分，共 20 分）1、编写一个函数完成以下功能，删除链表中倒数第i 个结点。2、设计算法编写一个函数完成以下功能，统计一棵二叉树中所有度为 0 的结点的数目。