2022年10月重庆自考02331 《数据结构》 真题
1 .请考生按规定将所有问题的答案用钢笔涂掉并写在答案纸上。
2 .答题前,考生必须用黑字签字笔或钢笔将自己的考试课程名称、姓名、准考证号填写在答题纸上的规定位置。
一、单项选择题:本大题共15小题,每小题2分,共30分。在每小题列出的备选项中只有一项是最符合题目要求的,请将其选出。
1 .在以下选项中,以链式保存的是
a .序列堆栈
b .三元组
c .二叉链表
d .邻接矩阵
2 .在线性表中采用顺序存储的好处是
a .插入运算容易
b .便于删除运算
c .存储空间不必是连续的
d .可随机访问各要素
3 .起始节点的单链接列表l的起始指针为head,节点结构如下。
,求出l不为空时的判定条件为“真”,则正确的公式为
a .头下一步!=空
B. head-next=NULL
C. head!=头
D. head=NULL
4. n阶方阵a是对称矩阵。 现在,使用一维排列b逐行优先存储a的上三角部分。 b的要素数至少
a.NX(n1 )/2
b.NX(n-1 )/2
C. nxn/2
D. n
5 .广义表是已知的
LS的深度是
A.5
B.4
C.3
D.2
6 .具有20个节点的二叉树t依次被收纳在数组b中。 假设在B[7]中保存了的节点v,则保存v的父节点是因为
A. B[0]。
B. B[2]。
C. B[3]。
D. B[4]。
7 .在非空二叉树中顺序扫描序列中,位于根节点之后的是
a .左侧子树的部分节点
b .右子树的部分节点
c .左侧子树的所有节点
d .右子树的所有节点
8 .在以下关于二叉树和森林相互转换的描述中,正确的是
a .将二叉树转换为森林时,获得的森林不是唯一的
b .将二叉树转换为森林时,得到的森林一定是唯一的
c .将森林转换为二叉树时,得到的二叉树不是唯一的
D .将森林转换为二叉树时,得到的二叉树可能不是唯一的
9 .在有向图g中,如果顶点v的出度和入度都是2,则g中的弧数最少
A.5
B.4
C.3
D.2
10 .对下图进行拓扑排序后,可以获得以下拓扑顺序
a.3、1、2、4、5、6
b.3、1、2、4、6、5
c.3、1、4、2、5、6
d.3、1、4、2、6、5
11 .如果初始关键字序列为15、10、12、5、48、30,按升序直接进行插入排序,则三次排序的结果为
a.5、10、12、15、48和30
b.5、10、12、15、30和48
c.10、15、12、5、48和30
d.10、12、15、5、48和30
12 .在以下排序方法中,排序期间使用的辅助区域不是0(1)的是
a .直接插入排序
b .冒泡排序
c .希尔排序
d .基数排序
13 .在以下关于二叉树t操作的描述中,正确的是
在A.T中删除一个关键词时,树的高度一定要减去1
即使在b.t中删除一个关键词,树的高度也不会改变
在c.t中插入新关键词时,树的高度必须加1
d .用t寻找某个关键词时,树的高度不变
14 .哈希表长度m=7,哈希函数h(key )=key %7,用线性探测方法处理冲突。 表中保存了h(21 )=0,h )8)=1,h ) 25 )=4这三个关键词,剩下的地址都是开放地址。 在此插入关键字14。 散列表的下标地址是
A.0
B. 1
C.2
D.3
15 .当按顺序搜索数据序列时,必须满足以下条件
a .数据必须保存在数组中
b .数据必须保存在链表中
c .数据必须按升序排列
d .数据应可进行比较操作
二、填空题:本大题共10小题,每小题2分,共20分。
16 .数据运算在数据的________结构中定义。
17 .在非空线性表中,没有前导的元素称为_ _ _ _ _ _。
18 .使用数组保存的堆栈为_________。
19 .如果设置广义表l(a,b )、c,d,e )、f )、g )、h ),则head ) head(l ) )的结果为_____。
20 .在非空二叉树t的前(先)序扫描序列中,第一个元素是_ _ _ _ _ _。
21 .图g的遍历过程实际上是对各个顶点搜索_________的过程。
22 .如果有向图g中存在拓扑序列,则序列中第一个顶点的入度值为_ _ _ _ _ _。
23 .快速排序划分数据序列。 为此,请选择元素作为________。
24 .要按升序对数据序列进行排序,请首先创建初始序列,作为_ _ _ _ _ _。
25 .散列方式中,实现关键字到存储地址的映射是_ _ _ _ _ _。
三、解答题:本大题共4小题,每小题5分,共20分。
26 .二叉树t的前相遍历序列为ABDEHCFGI,中相遍历序列为DBHEAFCIG。 请画一棵树t。
27 .问题27求解图27所示连通网的最小生成树,计算最小生成树的权重。
28 .有以下关键词序列( 25、30、14、2、21、36、51、3 ) ),采用双路归并排序进行升序排序,给出归并过程。
29 .有一组关键字( 2、13、18、25、30、33、36、55 )。 请绘制描述二叉树以描述二叉树搜索过程。
四、算法阅读题:本大题共4小题,每小题5分,共20分。
30 .链表的类型定义如下: