发布时间 : 星期二 文章数据结构 总结更新完毕开始阅读3f9339277dd184254b35eefdc8d376eeaeaa17fc
命题说明 考核的重点及命题说明 章节 第1章 第2章 各种基本概念和术语(0分)； 掌握算法描述和分析的方法(0分) 线性表的逻辑结构和各种存储表示方法(0分)； 以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算(0分) 栈和队列的特点(0分)； 栈在两种存储结构表示时的基本操作实现算法(0分)； 循环队列和链队列的基本操作实现算法(0分) 二叉树的各种存储结构的特点(0分)； 二叉树各种遍历策略的递归和非递归算法(0分)； 已知先序序列和中序序列或中序序列和后序序列建立二叉树的方法(0分)； 二叉树的线索化过程；(0分) 树的各种存储结构及特点；(0分) 建立最优树和哈夫曼编码的方法(0分) 图的各种存储结构(0分)； 图的两种搜索路径的遍历（深度和广度）(0分)； 最小生成树(0分)； 拓扑排序(0分)； 关键路径(0分)； 最短路径(0分) 顺序表和有序表的查找(0分)； 二叉排序树的构造和查找(0分)； 哈希表的构造方法(0分) 各种排序方法的执行过程和其依据的原则(0分)； 各种排序方法时间复杂度的分析(0分) 第3章 第6章 第7章 第9章 第10章 备注 一、单项选择（每题2分，共 20 分）
1、分析下面程序段的时间复杂度： ( )
i=1;j=1;
while(i<=n) i=i*3; while(j<=n) j++;
A、O(n+log3n) B、O(n) C、O(log3n) D、O(n*log3n)
2、下面关于串的的叙述中，哪一个是不正确的： （ ）
A、串是字符的有限序列 B、空串是由空格构成的串
C、模式匹配是串的一种重要运算 D、串既可以采用顺序存储，也可以采用链式存储
3、从逻辑上可以把数据结构分为两大类 （ ）
A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构
4、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表
5、有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？ （ ）
A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6
6、最大容量为n的循环队列，队尾指针是rear，队头是front，则队满的条件是 （ ）
A. (rear+1) MOD n=front B. rear=front
C．rear+1=front D. (rear-l) MOD n=front
7、在一个长度为n的顺序表中删除第i个元素，需向前移动（ ）个元素。
A. n B.i-1 C.n-i D.n-i+1 8、对一颗具有n个节点的树，其中所有度之和等于（ ）。
A. n B.n-1 C.n-2 D.n+1
9、某二叉树的前序和后序序列正好相反，则该二叉树一定是： ( )
A、高度等于其结点数 B、任意一个二叉树 C、所有节点均无左孩子 D、所有节点均无右孩子
10、已知一棵完全二叉树的第6层（根节点为第一层）有8个叶子节点，则完全
二叉树的节点个数至多是： A、39 B、52 C、111 D、119 ( ) 11、以下数据结构中，（ ）是非线性数据结构。
A．树 B．字符串 C．队 D．栈
12、设栈N和队列M初始状态为空，元素1,2,3,4,5,6依次通过栈N，一个元素出栈后进队列M，若6个元素出队的序列是2,4,3,6,5,1,则栈N的容量至少应该
是： ( )
A、2 B、3 C、4 D、5
13、一棵完全二叉树上有100个结点，其中叶子结点的个数是 （ ）
A． 50 B． 51 C．52 D．49
14、有关二叉树下列说法正确的是 （ ）
A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2
15、一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是 （ ）
A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG
二、填空题（每题2分，共 20 分）
1、设一行优先顺序存储的数组A[5][5]，A[0][0]的地址为1000，且每个元素占2个存储单元，则A[2][3]的地址为 。
2、设循环队列用数组A[M]表示，队首、队尾指针分别是front和rear，则循环队列的元素个数为 。 3、假定一棵二叉树的结点个数为200，则它的深度最少为 。
4、线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。
5、带头结点的循环链表L中只有一个元素结点的条件是：___ _____
三、简答题（每题5分，共1 0分）
1、什么是数据的逻辑结构？数据的逻辑结构主要有哪几种基本的类型？
2、线性表有哪几种存储结构？分别有哪些优点？ 四、综合应用题（每题5分，共2 0分）
1、已知一棵二叉树的先序遍历为ABECDFGHIJ，中序遍历为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) 给出拓扑排序序列 。
V1V2V4V3
5、给出如下图深度优先和广度优先遍历序列。
AB。ECD
6、应用普里姆算法和克鲁斯卡尔算法求图的最小生成树。（具体步骤）
0V230153110914V 15V 5V 212V 422V 3 (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的关键路径。要求：给出具体计算过程，即列出所有事件的最早和最晚开始时间，所有活动的最早和最晚开始时间。
B 6 A 4 1 10 E 1 G 2 I 7 H 4 4 5 C 2 D F
8、给出a到其他顶点的单源最短路径，根据dijkstra算法给出计算步骤。
5a2b1c331d1e
9、已知有序顺序表的元素分别为：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 ,解决冲突的方法分别为（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的结点的数目。
4