全国2020年8月自考数据结构导论02142真题试卷

注意事项:

1.答题前,考生务必将自己的考试课程名称姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。

2.每小题选出答案后,用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动,用橡皮擦干净后,再选涂其他答案标号。不能答在试题卷上。

一、单项选择题:本大题共15小题,每小题2分,共30分。在每小题列出的备选项中只有一项是最符合题目要求的,请将其选出。

1.下面程序段的时间复杂度为

for(int i=0; inext;

6.设某棵二叉树中有2000个结点,则该二叉树的最小高度为

A.9

B.10

C.11

D.12

7.对二叉树的结点从1开始进行连续编号,要求每个结点的编号大于其左、右孩子的编号,同.一结点的左右孩子中,其左孩子的编号小于其右孩子的编号,可 采用实现编号的遍历方法是

A.先序

B.后序

C.中序

D.层次

8.若一棵二叉树中度为1的结点个数是5,度为2的结点个数是3,则该二叉树叶子结点个数为

A. 2

B.3

C.4

D.5

9.对稀疏矩阵采用三元组表示法的目的是

A.便于输人和输出

B.便于进行矩阵运算

C.降低时间复杂度

D.节省存储空间

10.在图G中求两个结点之间的最短路径可以采用的算法是

A. Djkstra算法

B. Prim算法

C.克鲁斯卡尔算法.

D.广度优先遍历算法

11.如果按深度优先搜索算法从图中任意-一点出发均可以访问图中所有的顶点,则该图一定是

A.连通图

B.有回路图

C.完全图

D.无环图

12.假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进.行探测的次数是

A. k-1

B. k

C. k+1

D. k(k+1)/2

13.二叉排序树中,若它的左子树不空,则根结点的值比左子树上所有结点的值

A.小

B.大

C.小或相等

D.大或相等

14.设一组初始记录有8个关键字,使用直接插人排序得到有序序列，则需要经过的趟数最多是

A.5

B.6

C.7

D.8

15.在最好情况下,只需要一趟就可以完成对--个数组的排序,可选择的排序方法是

A.快速排序

B.冒泡排序

C.直接选择排序

D.直接插入排序

二、填空题:本大题共13空,每空2分,共26分。

16.数据结构是指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的      ▲     方式,以及定义在该组数据上的一组操作。

17.数据不可分割的最小识别单位是     ▲     。

18.树有如下三种常用的存储结构:孩子链表表示法、孩子兄弟链表表示法和      ▲     。

19.在带头结点的单链表L中,第一个数据元素结点的指针为     ▲     。

20.丽数的嵌套调用使用的数据结构是     ▲     。

21.图有n个顶点e条边，以邻接表作存储结构实现的拓扑排序算法的时间复杂度为     ▲     。

22.一个具有n个顶点的无向完全图的边数为     ▲     ,

23. -棵二叉树的度数最大为     ▲     

24. n个顶点的连通图的生成树有     ▲     条边。

25.就平均时间性能而言,快速排序方法的时间复杂度为     ▲     。

26.二分查找算法的时间复杂度为     ▲     。

27.解决冲突的方法主要有线性探查法、链地址法、多重散列法、公共溢出区法和     ▲     

28.冒泡排序的平均时间复杂度为     ▲     

三、应用题:本大题共5小题,每小题6分,共30分。

29.有二叉树如题29图所示,写出该二叉树的先序遍历、中序遍历和后序遍历序列。

30.如题30图所示的图结构,请写出以10为源点的广度优先搜索得到的顶点访问序列,并画出搜索过程图。(同等情况下,值小的结点优先访问)

31.设散列表的长度为11,散列丽数h(key)=key mod 11,采用线性探查法解决冲突。从空表开始,依次插人下列关键字值序列:80,40,7,18,13,2,请建立散列表。

32.依次输人键值序列:30,10, 20,50,40,60,构建二叉排序树,要求给出构建过程。

33.对序列(45,38,66 ,90,88,10,25,45)进行冒泡排序,写出前三趟排序结果。四算法设计题:本大题共2小题,每小题7分,共14分。

34.试写出二分查找的非递归算法。

35.已知丽数swap(R[min],R[i])功能是将记录R[min]和R[i]交换。试写出直接选择排序算法。如果大家想要获得