辽宁2021年10月高等教育自学考试数据结构试题
课程代码:02331
1.请考生按规定用笔将所有试题的答案涂、写在答题纸上。
2.答题前,考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。
选择题部分
注意事项:每小题选出答案后,用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动,用橡皮擦干净后,再选涂其他答案标号。不能答在试题卷上。
一、单项选择题:本大题共15小题，每小题2分，共30分。在每小题列出的备选项中只有一项是最符合题目要求的，请将其选出。
1.下列关于数据项和数据元素的叙述中，正确的是
A.数据项只能是数值类型
B.数据项可以包含数据元素
C.数据元素是数据的基本单位
D.数据元素是由数据项组成的集合
2.下列关于抽象数据类型的叙述中，正确的是
A.抽象数据类型与具体实现相关
B.抽象数据类型是由C语言本身提供的
C.抽象数据类型是C语言提供的类型的逻辑描述
D.抽象数据类型将数据定义和数据操作封装在一起
3.设有初始为空的栈S，入栈序列是f,e,d,c, b,a,出栈序列是d,e,a,b,c,f,则需要为S分配的空间大小至少是
A.2
B.3
C.4
D.5
4.指针head指向带头结点的单链表L的表头，结点结构为: 
,其中，data为int型，next 是指向后继结点的指针。指针p指向L中的首个数据结点，指针q指向p的后继结点。现要交换p. q所指向的两结点中的data值，下列选项中，不能完成该任务的操作是
A. head->next=q; p->next=q->next; q->next= p;
B. p->next= q->next; head->next=q; q->next= p;
C. q->next- P; p->next= q->next; head->next = q;
D. int temp= p->data; p->data = q->data; q->data = temp;
5.采用行优先压缩存储方式保存6行6列对称矩阵A的上三角部分，每个元素占2个单元，若A中第一个元素a11的存储地址是10,则元素a34的存储地址是
A.22
B.26
C.34
D.40
6.已知广义表L=((, i), h), (x,i,a,o))， 下列运算中， 结果得到h的是
A. head( tail(L))
B. head( tail( head(L)))
C. head( head( tail(L)))
D. head( head( tail( tail(L))))
7. 下列关于二叉树的叙述中，错误的是
A.二叉树可以为空
B.二叉树可以保存在数组中
C.二叉树中叶结点的个数多于度为1结点的个数
D.二叉树中叶结点的个数多于度为2结点的个数
8.若二叉树的前序遍历序列是ABCD,中序遍历序列是ACDB，则其后序遍历序列是
A. ABDC
B. ACDB
C. CDBA
D. DCBA
9.对下图进行广度优先搜索遍历，正确的遍历序列是
A. bdeac
B. badce
C. acedb
D. abced
10.关于图G的深度优先生成树T1与广度优先生成树T2，下列叙述中正确的是
A.T1与T2一定相同
B.T1与T2可能相同
C.T1与T2一定不相同
D. T1与T2中所含边数不相等
11. 对n个记录进行排序，最坏情况下，时间复杂度不是O(n2)的排序方法是
A.直接插入排序
B.冒泡排序
C.快速排序
D.堆排序
12.下 列排序方法中，不宜在链表上实现的是
A.直接插入排序
B.快速排序
C.归并排序
D.基数排序
13.若元素序列11,13, 15,7,8, 9,23,2, 5是采用下列排序算法之一，得到的第2趟排序后的结果，则该排序算法是
A.直接插入排序
B.冒泡排序
C.选择排序
D.二路归并排序
14. 在长度为n (n≥100) 的有序线性表中进行二分查找，查找成功时，查找长度不多于4的关键字个数是
A.4
B.7
C.15
D.100
15.将下列数据分别依次插入到初始为空的二叉排序树中，能得到高度最低二叉排序树的是
A.9,7,2,1,4, 10
B.6,4, 1,8, 10, 5
C. 5,1,2, 6,3, 4
D.2,4,7,5, 8, 10
非选择题部分
注意事项:用黑色字迹的签字笔或钢笔将答案写在答题纸上,不能答在试题卷上。
二、填空题:本大题共10小题，每小题2分，共20分。
16.非空的带头结点的单循环链表中，终端结点的指针域指向的是链表的_______。
17.己知循环队列存储在- -维数组A[0..n-1]中，头指针是front,尾指针是rear,初始时front的值和rear的值均是0，则第1个入队元素存储在数组中存储位置的下标是_______。
18.将中缀表达式9- (2+4*7)转换为后缀表达式的结果是________。
19.广义表G= (27, G)的深度是________。
20.具有n (n≥1)个结点的二叉树，采用二叉链表存储，空指针域的个数是_______。
21.两个无向连通图均含有10 个顶点，它们之间的边数差最大是________。
22.有向图G存在拓扑序列的条件是________。
23.若用C语言的数组A保存含n (n≥10) 个元素的大根堆，则第3大元素在A中的下标最大是________。
24.分块查找又称为_______。
25.非空的3阶B树中，每个非根结点中含有的关键字个数最少是_
三、解答题:本大题共4小题，每小题5分，共20分。
26.链栈为什么不必设置头结点?
27.已知字符集{ a,b,c, d,e }中各字符出现的频次分别为2,3, 6, 8, 10,对字符集进行哈夫曼编码，字符a的编码是000,字符e的编码是11,则其余3个字符的编码分别是什么?
28.设有向图G如题28图所示，给出图G的邻接矩阵。
题28图
29.设有关键字16, 15,32, 11, 6, 30，将它们依次保存在哈希表(长度为7的一维数组)中，哈希函数为H(k) = k mod 7,采用线性探查法解决冲突。已知关键字16已放置在数组下标为2的位置。请画出哈希表。
四、算法阅读题:本大题共4小题，每小题5分，共20分。
30.程序f30( )创建了一个带头结点的含n (n≥3)个数据结点的单链表L, L前两个数据结点中的data值均为1,从第3个结点开始，结点的data值是其前两个结点data值之和。请在空白处填上适当内容将算法补充完整。
五、算法设计题:本题10分。
34.设n个整数存放在数组A中，请编写函数f34(intA[],intn),将所有奇数调整到所有偶数之前。