数据结构试卷及参考答案_41
需积分: 0 183 浏览量
2022-08-08
21:46:11
上传
评论
收藏 43KB DOCX 举报
数据结构试卷（四）
一、选择题(每题 1 分共 20 分)
1．设一维数组中有 n 个数组元素，则读取第 i 个数组元素的平均时间复杂度为（ ）。
(A) O(n) (B) O(nlog
2
n) (C) O(1) (D) O(n
2
)
2．设一棵二叉树的深度为 k，则该二叉树中最多有（ ）个结点。
(A) 2k-1 (B) 2
k
(C) 2
k-1
(D) 2
k
-1
3．设某无向图中有 n 个顶点 e 条边，则该无向图中所有顶点的入度之和为（ ）。
(A) n (B) e (C) 2n (D) 2e
4．在二叉排序树中插入一个结点的时间复杂度为（ ）。
(A) O(1) (B) O(n) (C) O(log
2
n) (D) O(n
2
)
5．设某有向图的邻接表中有 n 个表头结点和 m 个表结点，则该图中有（ ）条有向边。
(A) n (B) n-1 (C) m (D) m-1
6．设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ ）
趟的分配和回收才能使得初始关键字序列变成有序序列。
(A) 3 (B) 4 (C) 5 (D) 8
7．设用链表作为栈的存储结构则退栈操作（ ）。
(A) 必须判别栈是否为满 (B) 必须判别栈是否为空
(C) 判别栈元素的类型 (D) 对栈不作任何判别
8．下列四种排序中（ ）的空间复杂度最大。
(A) 快速排序 (B) 冒泡排序 (C) 希尔排序 (D) 堆
9．设某二叉树中度数为 0 的结点数为 N
0
，度数为 1 的结点数为 N
l
，度数为 2 的结点数为
N
2
，则下列等式成立的是（ ）。
(A) N
0
=N
1
+1 (B) N
0
=N
l
+N
2
(C) N
0
=N
2
+1 (D) N
0
=2N
1
+l
10.设有序顺序表中有 n 个数据元素，则利用二分查找法查找数据元素 X 的最多比较次数不
超过（ ）。
(A) log
2
n+1 (B) log
2
n-1 (C) log
2
n (D) log
2
(n+1)
二、填空题(每空 1 分共 20 分)
1． 设有 n 个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平
均时间复杂度为_________。
2． 设指针变量 p 指向双向循环链表中的结点 X，则删除结点 X 需要执行的语句序列为
_________________________________________________________（设结点中的两个指
针域分别为 llink 和 rlink）。
3． 根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为____________。
4． 深度为 k 的完全二叉树中最少有____________个结点。
5． 设初始记录关键字序列为(K
1
，K
2
，…，K
n
)，则用筛选法思想建堆必须从第______个元
素开始进行筛选。
6． 设哈夫曼树中共有 99 个结点，则该树中有_________个叶子结点；若采用二叉链表作为
存储结构，则该树中有_____个空指针域。
7． 设有一个顺序循环队列中有 M 个存储单元，则该循环队列中最多能够存储________个队
列元素；当前实际存储________________个队列元素（设头指针 F 指向当前队头元素的
前一个位置，尾指针指向当前队尾元素的位置）。
评论0