山东自考报名入口-2023年 4月高等教育自学考试 数据结构导论试题

绝密 ★ 考试结束前

2023年 4月高等教育自学考试

数据结构导论试题

课程代码 :02142

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

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

选择题部分

注意事项 :

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

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

1. 与数据元素本身的形式 、内容 、相对位置 、个数无关的是数据的

A. 存储结构                                                B. 逻辑结构

C. 类型                                                        D. 运算实现

2. 在单链表中 ,释放已移出结点 p 的空间使用语句

A. maloc(p)              B. sizeof(p)              C. fre(p)                D. p=NULL

3. 在表长为 n 的顺序表上做插入运算 ,平均要移动的结点数为

A. n/4                       B. n/3                      C. n/2                     D. n

4. 线性表实现顺序存储使用

A. 栈                          B. 队列                     C. 链表                     D. 数组

5. 栈可以实现

A. 函数的嵌套调用和操作系统中进程调度

B. 函数的嵌套调用和程序递归的处理

C. 程序递归的处理和操作系统中进程调度

D. 操作系统中进程调度和网络管理中的打印服务

6. 顺序队列结构类型中 ,data为

A. 一维数组                                                B. 二维数组

C. 单链表                                                    D. 循环链表

浙 02142# 数据结构导论试题 第 1 页(共 4 页)

7. 下列关于树的描述 ,正确的是

A. 树形结构不可以表示具有层次结构的数据

B. 树是 n(n≥0) 个结点的有限集合

C. 任何只含一个结点的集合不是一棵树

D. 树形结构的定义是非递归的

8. 叶子的度为

A. - 1                       B. 0                         C. 1                         D. 2

9. 树的遍历有三种 ,为

A. 先序 、中序和后序遍历                            B. 先序 、中序和层次遍历

C. 先序 、后序和层次遍历                            D. 中序 、后序和层次遍历

10. 二叉树的中序序列中 ,结点 P排在结点 Q之前的条件是 :在二叉树中

A. P 在 Q 的左边                                        B. P 在 Q 的右边

C. P是 Q 的祖先                                          D. P是 Q 的子孙

11. 无向图中一个顶点的度是指图中

A. 通过该顶点的简单路径数                      B. 与该顶点连通的顶点数

C. 通过该顶点的回路数                              D. 与该顶点相邻接的顶点数

12. 下列序列中 ,符合堆定义的是

A. (100,80,55,60,50,40,58,35,20)         B. (100,80,55,60,50,40,35,58,20)

C. (100,80,55,58,50,40,60,35,20)          D. (100,70,55,60,50,40,58,35,20)

13. 下列有关解决冲突的几种方法 ,描述正确的是

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

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

C. 链地址法是挑选部分同义词建单链表来解决冲突

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

14. 双向循环链表的对称性可以表示为

A. p   p->prior->next  p->next->prior

B. p   p->next  p->prior

C. p   p->next->next  p->prior->prior

D. p   p->next->next  p->next

15. 待排序记录的数量很大时 ,排序方法效果较好的是

A. 堆排序和快速排序                                 B. 堆排序和直接插入排序

C. 直接插入排序和直接选择排序               D. 直接选择排序和快速排序

浙 02142# 数据结构导论试题 第 2 页(共 4 页 )

非选择题部分

注意事项 :

用黑色字迹的签字笔或钢笔将答案写在答题纸上 ,不能答在试题卷上 。

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

16. 表示数据元素之间的关联方式主要有顺序存储方式和    ▲   存储方式 。

17. 在单链表中 ,如果让最后一个结点的指针域指向第一个结点可以构成    ▲   链表 。

18. 栈的插入运算称为    ▲   。

19. 队列的链接实现实际上是使用一个带有    ▲   的单链表来表示队列 。

20. 以    ▲   为界的上(下) 半部分是一个固定的值 c或零 ,这样的矩阵叫做下(上) 三角矩阵 。

21. 循环队列结构类型中含有三个域 :data、front和 rear,循环队列 SQ为空的条件是    ▲   。

22. 对于任何完全二叉树来说 , 可以采用以    ▲   作为数组的下标的方法将结点存入 一 维数 组中 。

23. 如果一棵二叉树中度数为 0 的结点有 6个 ,那么度数为 2 的结点有    ▲   个 。

24. 如果 G是一个有向图 ,则把以顶点 v为终点的弧的数目称为 v 的    ▲   。

25. 一个图的最小生成树是指该图的所有生成树中    ▲   的生成树 。

26. 若图的顶点个数为 n, 图的弧的数目为 e,则拓扑排序算法的时间复杂度为    ▲   。

27. 静态查找表最简单的实现方法是以    ▲   作为存储结构 。

28. 归并排序要求待排序列是由若干个    ▲   子序列组成 。

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

29. 题 29图给出了矩阵 A,请将矩阵 A表示成三元组表 。

(0  2  0  0  0  0)

0   0  0  0  0  0

A= 0  0  0  5  0  9

0   6  0  0  0  0

(0   0  0  0  4  0J

题 29图

30. 根据有向图的邻接表回答下列问题 :

(1) 如何判断图中有多少条弧?

(2) 如何判断图中是否存在从顶点 i到顶点 j的弧?

(3) 如何求顶点 i的出度?

31. 设某通 信 系 统 中 一 个 待 传 输 的 文 本 有 6 个 不 同 字 符 , 它 们 的 出 现 频 率 分 别 是 0. 5, 0. 8, 1. 4,2. 2,2. 3,2. 8,试设计哈夫曼编码 。

浙 02142# 数据结构导论试题 第 3 页(共 4 页)

32. 如题 32图所示长度为 13的散列表 ,其散列函数为 H(key) =key mod 13,在表中已填入键

值分别为 16,30,54的元素 。

(1) 现要插入键值为 29的元素 ,应用二次探测法 ,计算填入散列表中单元的序号 。 (要求给 出求解过程)

(2) 二次探测法有什么缺点?

0    1    2    3    4    5    6    7    8    9   10  11  12

54

16

30

题 32图

33. 给定表(19,14,22,01,66,21,83,27,56,13,10) ,试按元素在表中的次序将它们依次插入一 棵初始时为空的二叉排序树 ,画出插入完成后的二叉排序树 。

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

34. 写出计算方阵 A[n][n] 与 B[n][n] 的乘积 C[n][n] 的算法 。

35. 已知循环队列的结构类型如下 :

typedef  struct  cycqueue

{

DataType  data maxsize

int  front rear

}CycQue

CycQueCQ

设计出队列的算法 。