2022年4月自考02142数据结构导论试题（历年真题）

2022年4月自考数据结构导论真题试卷出来了，免费下载哦，欢迎有需要的同学下载学习哦，此外还包含2022年4月高等教育自学考试全国统一命题考试真题试卷免费下载。

绝密★启用前

2022年4月高等教育自学考试全国统一命题考试数据结构导论

(课程代码02142)

注意事项：

1. 本试卷分为两部分，第一部分为选择题，第二部分为非选择题。
2. 应考者必须按试题顺序在答题卡(纸)指定位置上作答，答在试卷上无效。
3. 涂写部分、画图部分必须使用2B铅笔，书写部分必须使用黑色字迹签字笔。

点击免费下载：2022年4月高等教育自学考试全国统一命题考试

第一部分选择题

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

1. 算法时间复杂度指的是
2. 一个算法需要的存储量

C.算法在给定输入下的计算量

2. 双向循环链表结点结构为
3. 一个程序的确切执行时间

D.算法在给定时间下的计算量

在M中所对应的下标位置是

1. 8 B. 12 C. 13 D. 55
2. 任何一个带权的无向连通图的最小生成树

A.只有一棵 B. 一定有多棵 C.有一棵或多棵 D.可能不存在

12. 有关解决冲突的方法中，描述正确的是

• 多重散列法不易产生“堆积”

1. 线性探测法生成后继散列地址计算复杂

• 二次探测法生成的后继散列地址是连续的

1. 二次探测法容易探测到整个散列表的所有空间
2. 依次输入键值序列50,72,43,85,75,20,35,45,65,30,建立对应的二叉排序树以后，查找

A, data、next、node

1. prior、data、next
2. prior、data、tear
3. rear、data、next

3.设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为

元素35要进行元素间的比较次数为

1. 4 B. 5 C. 7

14.在散列函数H(k)=k MOD m中，一般来讲,m应取

1. 队列可以实现
2. 函数的嵌套调用和操作系统中进程调度
3. 函数的嵌套调用和程序递归的处理
4. 程序递归的处理和操作系统中进程调度
5. 操作系统中进程调度和网络管理中的打印服务
6. 在单链表中，释放已移出结点p的空间使用语句
7. malloc(p) B. sizeof(p)
8. 循环队列空条件为
9. free(p)
10. p = NULL
11. CQ. rear= =CQ. front
12. CQ. rear = CQ. front
13. CQ. rear+ 1 = CQ. front
14. CQ. rear+I = = CQ. front+1

7,元素的进栈次序为A,B,C,D,E,则出栈中不可能的序列是

1. A,B,C,D,E
2. B,C,D,E,A

C, E,A,B,C,D

1. E,D,C,B,A

A.奇数 B.偶数

15.下列序列中，符合堆定义的是

1. (100,80,55,60,50,40,58,35,20)
2. (100,80.55,58,50,40,60,35,20)

第二部分

D.合数

1. (100,80,55,60,50,40,35,58,20)
2. (100,70,55,60,50,40,58,35,20)

非选择题

二、填空题：本大题共13空，每空2分，共26分。

• 数据及数据的组织方式称为数据的_丄_。

17. 设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的语句序列是▲ ；r=s；r->next=NULL。

18. 栈初始化时，生成一个结点，将该结点的next域设置为 ▲
19. 链队列中，单链表的头结点的next域指向队列 ▲结点。
20. 数组釆用存储结构来存储数据元素。
21. 一棵树中所有结点的度的称为该树的度。
22. 由先序序列的第一个结点可以确定这棵树的—▲—结点。
23. 一棵树的最少结点个数为▲。
24. 任何两点之间都有边的无向图称为无向图。
25. 已知完全二叉树的第7层有20个结点.则整个完全二叉树的叶子结点数是_4_。
26. 任何一个无环有向图，其全部顶点可以排成一个丄—序列。
27. 稀疏矩阵可以釆用▲表示法进行压缩存储。
28. 相同键值的两个记录在排序前后相对位置的变化情况是排序算法研究中经常关注的一个 问题，这个问题称为排序算法的 室_。

三、应用题：本大题共5小题，每小题6分，共30分。

29. 二叉树的五种基本形态如题29图所示。(1)子树用什么形状表示？(2)分别写出题29-1 图、题29-2图和题29-5图的形态。
30. 给定无向图如题30图所示。

• 计算 D(vQ和 DC%)。
• 写出以顶点Vo为起点到V3的所有简单路径。

33. 已知散列函数为H(key)=key mod 7,构造散列表如题33表，并用线性探测法解决冲突。 若要用该散列表查找元素25,32,68,请分别给出所需的比较次数。

题33表

0 1 2 3 4 5 6

68 50 25 32 48

四、算法设计题：本大题共2小题，每小题7分，共14分。

34. 写出实现对一个nXn阶矩阵进行转置的算法。
35. 已知二叉链表的类型定义如下：

typedef struct btnode

{ DataType data;struct btnode * Ichild, * rchild:} * BinTree;

假定visit(bt)是一个已定义的过程，其功能是访问指针bt所指结点。设计在二叉链表上 的先序遍历算法和中序遍历算法。

31. 给定一组键值{45,38,66,90,88,10,25,45},假设在排序过程中，前4个记录已按键值递增 顺序重新排列，构成了一个有序序列为{38,45,66,90}。

• 请写出应用直接插入排序方法对剩余键值排序的排序过程。
• 直接插入排序方法是否稳定？

32. 设有m个顶点的无向图G,釆用邻接矩阵作存储结构，在邻接矩阵上判断下列有关问题, 给出简单的算法描述。

• 图中有多少条边？
• 任意两个顶点i和j是否有边相连？
• 任意一个顶点的度是多少？

点击免费下载：2022年4月高等教育自学考试全国统一命题考试

以上就是2022年4月自考数据结构导论真题试卷，有需要的同学可以自行下载使用，有什么问题可以随时留言咨询。