山东自考报名入口-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

设计出队列的算法 。

自考预报名

请选择您的报考层次 大专 本科 专本套读

提交报名信息 重置信息

我已阅读并同意《用户隐私条款》

个人信息授权与保护声明

关闭

鉴于网络的特性，本网站将无可避免地与您产生直接或间接的互动关系，故特此说明本网站对用户个人信息所采取的收集、使用和保护政策，请您务必仔细阅读：

信息收集范围

我们根据合法、正当、必要的原则，仅收集为您提供服务所必要的信息。包括：

1、您在使用我们服务时主动提供的信息

(2)您通过电话咨询方式提供的姓名、电话、住址、微信/QQ、备注等信息。

(3)您在使用网上咨询服务所提供的姓名、电话、住址、微信/QQ、备注等信息。

(4)您参与我们线上活动时填写的调查问卷中可能包含您的姓名、电话、地址等信息。

我们的部分服务可能需要您提供特定的个人敏感信息来实现特定功能。

若您选择不提供该类信息，则可能无法正常使用服务中的特定功能，但不影响您使用服务中的其他功能。

若您主动提供您的个人敏感信息，即表示您同意我们按本政策所述目的和方式来处理您的个人敏感信息。

本次报名数据服务由本网站提供，本网站不承担由于内容的不一致性所引起的一切争议和法律责任，报名结果以最终辅导报名系统为准。

信息使用用途

我们严格遵守法律法规的规定及与用户的约定，将收集的信息用于以下用途。若我们超出以下用途使用您的信息，我们将再次向您进行说明，并征得您的同意。

1、通过微信、电话形式建立沟通，向您提供学历咨询服务。

2、满足您的个性化需求。例如，学历途径规划、学历评估等。

3、项目开发和服务优化。例如，通过您的咨询问题及服务过程中您的建议等，优化我们的服务。

4、向您推荐您可能感兴趣的学校、资讯等。

5、学校推荐。例如，我们会根据您的具体要求以您所具备的条件向您推荐合适的院校。

为了让您有更好的体验、改善我们的服务或经您同意的其他用途，在符合相关法律法规的前提下，我们可能将通过某些服务所收集的信息用于我们的其他服务。例如，将您在使用我们某项服务时的信息，用于另一项服务中向您展示个性化的内容或广告、用于用户研究分析与统计等服务。

信息保护

我们仅在本《隐私政策》所述目的所必需的期间和法律法规要求的时限内保留您的个人信息。

本网站将对您所提供的资料进行严格的管理及保护，本网站将使用相应的技术，防止您的个人资料丢失、被盗用或遭篡改。

当政府机关依照法定程序要求本网站披露个人资料时，本网站将根据执法单位之要求或为公共安全之目的提供个人资料。在此情况下之任何披露，本网站均得免责。

由于您将用户密码告知他人或与他人共享注册帐户，由此导致的任何个人资料泄露。任何由于计算机问题、黑客政击、计算机病毒侵入或发作、因政府管制而造成的暂时性关闭等影响网络正常经营之不可抗力而造成的个人资料泄露、丢失、被盗用或被篡改情况时本网站亦毋需承担任何责任。

未成年人保护

本网站将建立和维持一合理的程序，以保护未成年人个人资料的保密性及安全性。本网站郑重声明：任何16岁以下的未成年人参加网上活动应事先得到家长或其法定监护人的可经查证的同意。若您是未成年人的监护人，当您对您所监护的未成年人的个人信息有相关疑问时，请通过与我们联系。

适用范围

我们的所有服务均适用本政策。但某些服务有其特定的隐私指引/声明，该特定隐私指引/声明更具体地说明我们在该服务中如何处理您的信息。如本政策与特定服务的隐私指引/声明有不一致之处，请以该特定隐私指引/声明为准。

您必须完全同意以上协议才能使用本网站的在线报名服务。