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

数据结构试卷（三）

一、选择题(每题2分，共20分)

1.设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={01，02，01，03，01，04，02，05，02，06，03，07，03，08，03，09}，则数据结构A是(B)。

A.线性结构

B.树形结构

C.物理结构

D.图形结构

2.下面程序的时间复杂度为(B)。

?1?

i=1

?2?

s=0

?3?

whilei=n:

?4?

???i+=1

?5?

???t=1

?6?

???forjinrange(1,i):

?7?

???????t=t*j

?8?

???????s=s+t

A.O(n)

B.O(n2)

C.O(n3)

D.O(n4)

3.设指针变量p指向单链表中的结点A，若删除单链表中的结点A，则需要修改指针的操作序列为(A)。

A.q=p.next；p.data=q.data；p.next=q.next；

B.q=p.next；q.data=p.data；p.next=q.next；

C.q=p.next；p.next=q.next；

D.q=p.next；p.data=q.data；

4.设有n个待排序的记录关键字，在堆排序中需要(A)个辅助记录单元。

A.1

B.n

C.nlog2n

D.n2

5.设一组记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为(A)。

A.10，15，14，18，20，36，40，21

B.10，15，14，18，20，40，36，21

C.10，15，14，20，18，40，36，21

D.15，10，14，18，20，36，40，21

6.设二叉排序树中有n个结点，则二叉排序树的平均查找长度为(B)。

A.O(1)

B.O(log2n)

C.O（n）

D.O(n2)

7.设无向图G中有n个顶点、e条边，则其对应的邻接表中的表头结点和表结点的个数分别为(D)。

A.n、e

B.e、n

C.2n、e

D.n、2e

8.设某强连通图中有n个顶点，则该强连通图中至少有(C)条边。

A.n(n-1)

B.n+1

C.n

D.n(n+1)

9.设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列(B)方法可以达到此目的。

A.快速排序

B.堆排序

C.归并排序

D.插入排序

10.下列4种排序中(D)的空间复杂度最大。

A.插入排序

B.冒泡排序

C.堆排序

D.归并排序

二、填空题(每空1分，共20分)

1.数据的物理结构主要包括顺序存储结构和链式存储结构两种情况。

2.设一棵完全二叉树中有500个结点，则该二叉树的深度为____9_____；若用二叉链表作为该完全二叉树的存储结构，则共有_____501____个空指针域。

3.设输入序列为（1，2，3），则经过栈的作用后可以得到___5______种不同的输出序列。

4.设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上的所有元素之和等于顶点i的_____出度____，第i列上的所有元素之和等于顶点i的___入度______。

5.设哈夫曼树中共有n个结点，则该哈夫曼树中有____0_____个度数为1的结点。

6.设有向图G中有n个顶点、e条有向边，所有的顶点入度数之和为d，则e和d的关系为____e=d_____。

7.____中序_____遍历二叉排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序)。

8.设查找表中有100个元素，如果用二分查找方法查找数据元素X，则最多需要比较_____7____次就可以断定数据元素X是否在查找表中。

9.不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为___O(1)______。

10.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点的编号为___i/2(向下取整)______，右孩子结点的编号为___2*i+1______。

11.设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序的结果为___51