2022年10月四川自考02331《数据结构》真题
1.请考生按规定用笔将所有试题的答案涂、写在答题纸上。
2.答题前,考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。
一、单项选择题:本大题共15小题，每小题2分，共30分。在每小题列出的备选项中只有一项是最符合题目要求的，请将其选出。
1.下列选项中，采用了链式方式存储的是
A.顺序栈
B.三元组
C.二叉链表
D.邻接矩阵
2.线性表采用顺序存储时的优点是
A.插入运算方便
B.删除运算方便
C.存储空间不必连续
D.可随机访问各元素
3.带头结点的单链表L的头指针是head,结点结构为: ， 若要求当L不为空时判定条件为“真”，则正确的表达式是
A. head->next != NULL
B. head->next = NULL
C. head != head
D. head = NULL
4. n阶方阵A是对称矩阵，现要使用一维数组B按行优先存储A的上三角部分，B 的元素个数至少是
A. nx(n+1)/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,采用线性探查法处理冲突。表中已保存3个关键字: 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图所示连通网的最小生成树，并计算最小生成树的权。
28.有以下关键字序列(25, 30, 14, 2, 21, 36, 51,3),使用二路归并排序进行升序排序，给出归并过程。
29.设有一组关键字(2, 13, 18, 25, 30, 33, 36, 55),请画出描述二分查找过程的二叉树。
四、算法阅读题:本大题共4小题，每小题5分，共20分。
30.链表类型定义如下:
Tags：