数据结构期末考试试题
一． 单项选择题（2分/题）
1． 一个栈的输入序列为12345，则下列序列中是栈的输出序列的是（A）。
A.23415 B.54132 C.31245 D.14253
2． 设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（D）。
A.r-f B.r-f+1 C.(r-f) mod n +1 D.(r-f+n) mod n
3． 二叉树在线索化后，仍不能有效求解的问题是（D）。
A.先序线索二叉树中求先序后继 B. 中序线索二叉树中求中序后继
C.中序线索二叉树中求中序前驱 D. 后序线索二叉树中求后序后继
4． 求最短路径的FLOYD算法的时间复杂度为（D）。
A.O(n) B.O(n+e) C.O(n2) D.O(n3)．
5 一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（B）。 A.0 B.1 C.2 D.不确定
6． 数组A[1..5,1..6]的每个元素占5个单元，将其按行优先顺序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为（A）。
A.1140 B.1145 C.1120 D.1125
7． 在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是（A）。
A.快速排序 B.希尔排序 C.冒泡排序 D.堆排序
8． 对有18个元素的有序表做折半查，则查A[3]的比较序列的下标依次为（C）。
A.1-2-3 B.9-5-2-3 C.9-5-3 D. 9-4-2-3
9． 下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（D）。
A.堆排序 B.冒泡排序 C.快速排序 D.直接插入排序
10． 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则做（B）型调整以使其平衡。
A.LL B.LR C.RL D.RR
三． 填空题（2分/空）
1．已知完全二叉树的第8层有8个结点，则其叶子结点数是（68）。68+8-4
2．将下三角矩阵A[1..8,1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[7,5]的地址是（1100）。
3．有n个顶点的强连通有向图G至少有（n）条弧。
4．有n个结点并且其高度为n的二叉树的数目是（2^（n-1））。
5．高度为8的平衡二叉树的结点数至少是（54）。
6．3个结点可构成（5）棵不同形态的树。
一、单选题 从供选择的答案中选出正确的答案，将其编号填入括号中。
1. 在数据结构的讨论中把数据结构从逻辑上分为（ ）。
A．内部结构与外部结构 B. 静态结构与动态结构
C. 线性结构与非线性结构 D. 紧凑结构与非紧凑结构
2. 采用线性链表表示一个向量时，要求占用的存储空间地址（ ）。
A. 必须是连续的 B. 部分地址必须是连续的
C. 一定是不连续的 D. 可连续可不连续
3. 采用顺序搜索方法查长度为n的顺序表时，搜索成功的平均搜索长度为（ ）。
A. n B. n/2 C. (n-1)/2 D. (n+1)/2
4. 在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ ）。
A. s→link = p→link; p→link = s; B. p→link = s; s→link = q;
C. p→link = s→link; s→link = p; D. q→link = s; s→link = p;
5. 如果想在4092个数据中只需要选择其中最小的10个，采用（ ）方法最好。
A. 起泡排序 B. 堆排序 C. 直接选择排序 D. 快速排序
6. 设有两个串t和p，求p在t中首次出现的位置的运算叫做（ ）。
A. 求子串 B. 模式匹配 C. 串替换 D. 串连接
7. 在数组A中，每一个数组元素A[i, j] 占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ ）。
A. 80 B. 100 C. 240 D. 270
8. 将一个递归算法改为对应的非递归算法时，通常需要使用（ ）。
A. 栈 B. 队列 C. 循环队列 D. 优先队列
9. 一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ ）。
A. 4, 3, 2, 1 B. 2, 4, 3, 1
C. 1, 2, 3, 4 D. 3, 2, 1, 4
10. 在循环队列中用数组-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ ）。
A. (front - rear + 1) % m B. (rear - front + 1) % m
C. (front - rear + m) % m D. (rear - front + m) % m
三、填空题 把合适的内容添到横线上。
1. 对于一个单链接存储的线性表，假定表头指针指向链表的第一个结点，则在表头插入结点
的时间复杂度为________，在表尾插入结点的时间复杂度为________。
2. 假定一棵三叉树（即度为3的树）的结点个数为50，则它的最小高度为________，假定树根结点为第0层。
3．一棵高度（假定树根结点为第0层）为4的完全二叉树中的结点数最少为________个，最多为________个。
4. 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要________条边。
5．从有序表(12,18,30,43,56,78,82,95)中分别折半查43和56元素时，其查长度分别为________和________。
6．对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个________。
7. 在开散列表中，处理冲突的方法为________法，在闭散列表中，处理冲突的方法为____________法。
8．在堆排序的过程中，对任一分支结点进行筛运算（即调整为子堆的过程）的时间复杂度为________，整个堆排序过程的时间复杂度为________。
9. 快速排序在平均情况下的时间复杂度为先序中序后序遍历二叉树________，在最坏情况下的时间复杂度为________。
10．在二路归并排序中，对n个记录进行归并的趟数为________。
四、运算题
1. 假定一棵普通树的广义表表示为a(b(e),c(f(h,i,j),g),d)， 分别写出先根、后根、按层遍历的结果。
先根：
后根：
按层：
2．若一个图的边集为{(A,B),(A,C),(A,D),(B,D),(C,F),(D,E),(D,F)}，从顶点A开始分别对该图进行深度优先搜索和广度优先搜索，要求顶点值小的邻接点被优先访问，则写出得到的深度优先搜索和广度优先搜索的顶点序列。
深度优先搜索得到的顶点序列：
广度优先搜索得到的顶点序列：
3．已知一个二叉搜索树的广义表表示为38(25(16),52(,74(68(,72),90)))，在下表中填写出每个元素的比较次数。
1 2 3 4 5 6 7 8
38 25 52 16 74 68 90 72

4. 假定一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70)，散列地址空间为HT[13]，若采用除留余数法构造散列函数和线性探测法处理冲突，试求出每一元素在闭散列表中的初始散列地址和最终散列地址，画出最后得到的散列表，求出平均查长度。
1 2 3 4 5 6 7 8 9 10
元素 32 75 29 63 48 94 25 46 18 70
初始散列地址
最终散列地址
0 1 2 3 4 5 6 7 8 9 10 11 12
散列表
平均查长度：
5. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用快速排序法进行排序时每一趟的排序结果。


参考解答
一、单选题:
1. C 2. D 3. D 4. D 5. B 6. B 7. C 8. A 9. C 10. D

三、填空题
1. O(1) O(n)
2．4
3．16 31
4. n-1
5. 1 3
6. 有序序列
7. 链接 开放定址
8．O(log2n) O(nlog2n)
9．O(nlog2n) O(n2)
10．?log2n?
四、运算题
1. 先根：a,b,e,c,f,h,i,j,g,d;
后根：e,b,h,i,j,f,g,c,d,a;
按层：a,b,c,d,e,f,g,h,i,j
2. 深度优先搜索得到的顶点序列：A,B,D,E,F,C
广度优先搜索得到的顶点序列：A,B,C,D,F,E
3．1 2 3 4 5 6 7 8
38 25 52 16 74 68 90 72
1 2 2 3 3 4 4 5
4．平均查长度为14/10。
1 2 3 4 5 6 7 8 9 10
元素 32 75 29 63 48 94 25 46 18 70
初始散列地址 6 10 3 11 9 3 12 7 5 5
最终散列地址 6 10 3 11 9 4 12 7 5 8
0 1 2 3 4 5 6 7 8 9 10 11 12
散列表 29 94 18 32 46 70 48 75 63 25

5．
1 2 3 4 5 6 7 8 9 10
(0) [46 74 53 14 26 38 86 65 27 34]
(1) [34 14 26 38 27] 46 [86 65 53 74]
(2) [27 14 26] 34 38 46 [74 65 53] 86
(3) [26 14] 27 34 38 46 [53 65] 74 86
(4) [14 26] 27 34 38 46 53 65 74 86
《数据结构》期末复习题
一、单项选择题
1. 一个栈的入栈序列是：a,b,c,d,e, 则栈的不可能的输出序列是  C    。
A．edcba              B.decba              C. dceab              D abcde
2. 不带头结点的单链表head为空的判定条件是 A    。
A. head= =NULL      B. headnext= =NULL      C. headnext= =head        D head!=NULL
3. 串是一种特殊的线性表，其特殊性表现在    B    。
A．可以顺序存储              B 数据元素是一个字符
C．可以链接存储              D 数据元素可以是多个字符
4. 一个广义表的表尾总是一个广义表，这个断言是 A     。
A．正确的                B 错误的
5.一个向量第一个元素的存储地址是200，每个元素的长度为2，则第五个元素的地址是（A ）
A、210                  B、208            C、200                  D、220
6. 一个队列的入队序列是：1,2,3,4, 则队列的输出序列是   B  。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。