大学计算机《数据结构》试卷及答案(八).pdfVIP

大学计算机《数据结构》试卷及答案

一、选择题(30分)

1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为

（）。

2

(A)O(n)(B)O(nlogn)(C)O(1)(D)O(n)

2

2．设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。

kk-1k

(A)2k-1(B)2(C)2(D)2-1

3．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。

(A)n(B)e(C)2n(D)2e

4．在二叉排序树中插入一个结点的时间复杂度为（）。

2

(A)O(1)(B)O(n)(C)O(logn)(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，度数为1的结点数为N，度数为2的

0l

结点数为N，则下列等式成立的是（）。

2

(A)N=N+1(B)N=N+N(C)N=N+1(D)N=2N+l

010l20201

10.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多

比较次数不超过（）。

(A)logn+1(B)logn-1(C)logn(D)log(n+1)

2222

二、填空题(42分)

1．设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，

快速排序的平均时间复杂度为_________。

2．设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语

句序列为_________________________________________________________（设

结点中的两个指针域分别为llink和rlink）。

3．根