2022年全国10月自考《数据结构》试题及其答案

1、请在百度文库下载仅限个人使用2021 年 10 月高等训练自学考试全国统一命题考试数据结构试题和答案课程代码： 02331 第一部分 挑选题一、单项挑选题 本大题共 l5 小题，每道题 2 分；共 30 分在每道题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡” 的相应代码涂黑；未涂、错涂或多涂均无分；1. 以下选项中，属于规律结构的是a. 线性表b链表c次序栈d循环队列2. 以下关于算法输出的表达中，正确选项a. 算法肯定没有输出b算法可以没有输出c算法至少有一个输出d算法必需有多个输出3针对线性表规律上相邻的两个元素，以下表达中，正确选项 a采纳次序储备时肯定相邻，采纳

2、链式储备时也肯定相邻 b采纳次序储备时肯定相邻，采纳链式储备时不肯定相邻 c采纳次序储备时不肯定相邻，采纳链式储备时肯定相邻 d采纳次序储备时不肯定相邻，采纳链式储备时也不肯定相邻 4队列和栈的特点分别是a先进先出，先进后出b先进先出，先进先出c先进后出，先进先出d先进后出，先进后出5在二维数组 a810中，每个数组元素aij占用 3 个储备空间，全部数组元素存放在一个连续的储备空间中，就该数组需要的储备空间个数是a 80b 100c 240d 2706广义表 a=a ， b ， e， e ， f ， g，h的表长是a 2b 3c 4d 7 7设深度为 kk 1 的二叉树中只有度为0 和度为

3、2 的结点，就该二叉树中所包含的结点数至少是a k+1b 2k+1c 2k-ld 2k 8以下选项中，可以唯独确定一棵二叉树的两种遍历序列是a前序遍历序列和中序遍历序列b前序遍历序列和后序遍历序列c前序遍历序列和层次遍历序列d后序遍历序列和层次遍历序列9. 以下关于无向连通图特性的表达中，正确选项a. 边数大于顶点个数减lb全部顶点的度之和为偶数 c度为 l 的顶点个数肯定为偶数d度为 l 的顶点个数肯定为奇数10以下关于无向图广度优先搜寻序列的表达中，正确选项 a广度优先搜寻序列只有一种b广度优先搜寻序列可能不存在c广度优先搜寻序列可能有多种d广度优先搜寻序列肯定有多种11设带权连通图 g中

4、含有 nn>1 个顶点 e 条边；以下关于 g的最小生成树的表达中，正确选项a. 生成树中肯定含有权值最小的e 条边- 0 -百度文库下载仅个人使用b. 生成树中可能含有权值最小的n+1 条边c生成树中肯定含有权值最小的n 条边d生成树中可能含有权值最小的n-1 条边 12以下排序方法中，时间复杂度与数据初始状态相关的是a直接挑选排序b快速排序c基数排序d箱排序13. 以下排序方法中，效率较高且稳固的方法是a直接插入排序b冒泡排序c快速排序d归并排序14. 以下表达中，不符合m阶 b 树定义的是a根结点最多有m棵子树b全部叶结点都在同一层上 c各结点内关键字均升序或降序排列d叶结点之间通

5、过指针链接 15假设散列表长 m=11，散列函数 hkey=key 11；表中已有4 个结点： h39=6 h41=8 ， h53=9 ，h76=10 ，占了 4 个位置，其余位置为空；现采纳线性探查法处理冲突，储备关键字85 时需要探查的次数是a 2b 3c 4d5其次部分非挑选题二、填空题 本大题共 l0 小题，每道题 2 分，共 20 分 请在答题卡上作答；三、简答题 本大题共 4 小题，每道题 5 分；共 20 分请在答题卡上作答；26. 设 q是有 n 个储备空间的循环队列，初始状态front=rear=0，商定指针 rear指向的单元始终为空，回答以下问题；(1) 写出数据元素 x

6、人队的语句序列；(2) 写出队首元素出队并储存到变量y 的语句序列；(3) 给出运算队列长度l 的表达式；27. 已知稀疏矩阵 m如下，采纳三元组表储备；- 1 -请回答以下问题；(1) 给出三元组表的类型定义；(2) 画出矩阵 m按行优先的三元组表；28将百分制成果分成五个等级，已知成果的对应关系及分布情形如下表所示：请依据最优二叉树的基本原理，采纳类c语言，描述你所设计的成果判定过程；29给定有向无环图g如题 29 图所示，写出 g的 5 种不同的拓扑排序序列；四、算法阅读题 本大题共 4 小题，每道题 5 分；共 20 分请在答题卡上作答；30. 请写出以下程序段的输出结果；- 2 -31. 带头结点的单链表定义如下，其中 freq 域记录本结点被拜访的次数，初值为 0，单链表始终以 freq 值从大到小有序；函数 f3l 完成的功能是： 查找给定关键字所在结点， 如查找胜利， 就该结点的 freq 域加 l ，并按 freq 值调整结 r 旨位置；请将空白处 1 3 补充完整；在答题卡上作答；- 3 -32. 阅读程序，回答以下问题；- 4 -如次序表r 的元素个数 n=6，关键字依次为 41 ， 82， 75， 24， 8， 16 ，就：(1) 写出函数 f32 执行