2020年8月自考02142数据结构导论试卷及答案

自考生网为考生们整理提供了“2020年8月自考02142数据结构导论试卷及答案”，更多02142数据结构导论内容可点击查看自考02142数据结构导论试卷及答案汇总。

注：不同省份、不同专业的自考历年真题及答案，只要课程代码和课程名称相同，都可参考使用。

点击查看：更多自考02142数据结构导论试卷及答案

2020年8月自考02142数据结构导论试卷

全国2020年8月高等教育自学考试

数据结构导论试题

课程代码:02142

请考生按规定用笔将所有试题的答案涂、写在答题纸上。

选择题部分

注意事项:

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

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

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

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

A.2

B.3

C.4

D.5

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

A.便于输入和输出

B.便于进行矩阵运算

C.降低时间复杂度

D.节省存储空间

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

A. Dijkstra算法

B.Prim算法

C.克鲁斯卡尔算法

D.广度优先遍历算法

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

A.连通图

B.有回路图

C.完全图

D.无环图

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

A.k-1

B. k

C.k+I

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个顶点c条边,以邻接表作存储结构实现的拓扑排序算法的时间复杂度为_____

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

23.一棵二叉树的度数最大为_____

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

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

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

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

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

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