数据结构试卷(五)
一、选择题(20 分)
1.数据的最小单位是( )。
(A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量
2.设一组初始记录关键字序列为(50,40,95,20,15,70,60,45),则以增量 d=4 的一
趟希尔排序结束后前 4 条记录关键字为( )。
(A) 40,50,20,95 (B) 15,40,60,20
(C) 15,20,40,45 (D) 45,40,15,20
3.设一组初始记录关键字序列为(25,50,15,35,80,85,20,40,36,70),其中含有 5
个长度为 2 的有序子表,则用归并排序的方法对该记录关键字序列进行一趟归并后的结
果为( )。
(A) 15,25,35,50,20,40,80,85,36,70
(B) 15,25,35,50,80,20,85,40,70,36
(C) 15,25,35,50,80,85,20,36,40,70
(D) 15,25,35,50,80,20,36,40,70,85
4.函数 substr(“DATASTRUCTURE”,5,9)的返回值为( )。
(A) “STRUCTURE” (B) “DATA”
(C) “ASTRUCTUR” (D) “DATASTRUCTURE”
5.设一个有序的单链表中有 n 个结点,现要求插入一个新结点后使得单链表仍然保持有序,
则该操作的时间复杂度为( )。
(A) O(log
2
n) (B) O(1) (C) O(n
2
) (D) O(n)
6.设一棵 m 叉树中度数为 0 的结点数为 N
0
,度数为 1 的结点数为 N
l
,……,度数为 m 的结
点数为 Nm,则 N
0
=( )。
(A) N
l
+N
2
+……+Nm (B) l+N
2
+2N
3
+3N
4
+……+(m-1)Nm
(C) N
2
+2N
3
+3N
4
+……+(m-1)Nm (D) 2N
l
+3N
2
+……+(m+1)Nm
7.设有序表中有 1000 个元素,则用二分查找查找元素 X 最多需要比较( )次。
(A) 25 (B) 10 (C) 7 (D) 1
8.设连通图 G 中的边集 E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从
顶点 a 出发可以得到一种深度优先遍历的顶点序列为( )。
(A) abedfc (B) acfebd (C) aebdfc (D) aedfcb
9.设输入序列是 1、2、3、……、n,经过栈的作用后输出序列的第一个元素是 n,则输出
序列中第 i 个输出元素是( )。
(A) n-i (B) n-1-i (C) n+1-i (D) 不能确定
10 设一组初始记录关键字序列为(45,80,55,40,42,85),则以第一个记录关键字 45 为
基准而得到一趟快速排序的结果是( )。
(A) 40,42,45,55,80,83 (B) 42,40,45,80,85,88
(C) 42,40,45,55,80,85 (D) 42,40,45,85,55,80
二、填空题(共 20 分)
1. 设有一个顺序共享栈 S[0:n-1],其中第一个栈项指针 top1 的初值为-1,第二个栈顶
指针 top2 的初值为 n,则判断共享栈满的条件是____________________。
2. 在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。
评论0