数据结构-Python语言描述试卷(五)附答案.pdf

数据结构试卷（五）

一、选择题（每题2分，共20分）

1.数据的最小单位是(A)。

A.数据项

B.数据类型

C.数据元素

D.数据变量

2.设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一

趟希尔排序结束后前4条记录关键字为(B)。

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)。

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.函数函数，5，9)的返回值为(A)。

5.设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，

则该操作的时间复杂度为(D)。

A.O(logn)

2

B.O(1)

C.O(n2)

D.O(n)

6.设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为N1，…，度数为m的结点

数为Nm，则N0=(B)。

A.N+N+…+N

12m

B.1+N+2N+3N+…+(m-1)N

234m

C.N+2N+3N+…+(m-1)N

234m

D.2N+3N+…+(m+1)N

12m

7.设有序表中有1000个元素，则用二分查找法查找元素X最多需要比较(B)次。

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出发可以得到一种深度优先遍历的顶点序列为(B)。

A.abedfc

B.acfebd

C.aebdfc

D.aedfcb

9.设输入序列是（1，2，3，…，n），经过栈的作用后输出序列的第一个元素是n，则输出

序列中的第i个输出元素是(C)。

A.n-I

B.n-1-I

C.n+1-I

D.不能确定

10.设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为

基准得到的一趟快速排序的结果是(C)。

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

二、填空题（除第1、2、8题2分外每空1分，共20分）

1.设有一个顺序共享栈S[0：n-1]，其中第一个栈顶指针top1的初值为-1，第二个栈顶

指针top2的初值为n，则判断共享栈满的条件是__top1+1=top2__。

2.在图的邻接表中用顺序存储结构存储表头结点的优点是_可以随机访问到任一个顶点的

简单链表_。

3.设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素(包括对角线上

的元素)存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_i*（i+1)/2+j-

1__个数据元素。

4.栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为FILO

表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以

又把队列称为_FIFO表。

5.设一棵完全二叉树的顺序存储结构中的存储数据元素为ABCDEF，则该二叉树的前序遍历

序列为_ABDECF_、中序遍历序列为_DBEAFC_、后序遍历序列为_DEBFCA_。

6.设一棵