2021年10月自考02331数据结构试题及答案.docx

1、2021年10月高等教育自学考试全国统一命题考试数据结构试卷(课程代码02331)一、单项选择题:本大题共15小题，每小题2分，共30分。1.下列关于数据项和数据元素的叙述中，正确的是（ C ）A.数据项只能是数值类型 B.数据项可以包含数据元素C.数据元素是数据的基本单位 D.数据元素是由数据项组成的集合2.下列关于抽象数据类型的叙述中，正确的是（ D ）A.抽象数据类型与具体实现相关B.抽象数据类型是由C语言本身提供的C.抽象数据类型是C语言提供的类型的逻辑描述D.抽象数据类型将数据定义和数据操作封装在一起3.设有初始为空的栈S，入栈序列是f,e,d,c,b,a,出栈序列是d,e,a,b,

2、c,f,则需要为S分配的空间大小至少是（ C ）A.2 B.3C.4 D.54.指针head指向带头结点的单链表L的表头，结点结构为:,其中，data为int型，next是指向后继结点的指针。指针p指向L中的首个数据结点，指针q指向p的后继结点。现要交换p.q所指向的两结点中的data值，下列选项中，不能完成该任务的操作是（ C ）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-da

3、ta=q-data;q-data=temp;5.采用行优先压缩存储方式保存6行6列对称矩阵A的上三角部分，每个元素占2个单元，若A中第一个元素a11的存储地址是10,则元素a34的存储地址是（ C ）A.22 B.26C.34 D.406.已知广义表L=(,i),h),(x,i,a,o)，下列运算中，结果得到h的是（ B ）A.head(tail(L) B.head(tail(head(L)C.head(head(tail(L) D.head(head(tail(tail(L)7.下列关于二叉树的叙述中，错误的是（ C ）A.二叉树可以为空B.二叉树可以保存在数组中C.二叉树中叶结点的个数多于

4、度为1结点的个数D.二叉树中叶结点的个数多于度为2结点的个数8.若二叉树的前序遍历序列是ABCD,中序遍历序列是ACDB，则其后序遍历序列是（ D ）A.ABDC B.ACDBC.CDBA D.DCBA9.对下图进行广度优先搜索遍历，正确的遍历序列是 （ B ） A. Bdeac B. badceC. Acedb D. abced10.关于图G的深度优先生成树T1与广度优先生成树T2，下列叙述中正确的是（ B ）A.T1与T2一定相同 B.T1与T2可能相同C.T1与T2一定不相同 D.T1与T2中所含边数不相等11.对n个记录进行排序，最坏情况下，时间复杂度不是O(n2)的排序方法是（ D

5、）A.直接插入排序 B.冒泡排序C.快速排序 D.堆排序12.下列排序方法中，不宜在链表上实现的是（ B ）A.直接插入排序 B.快速排序C.归并排序 D.基数排序13.若元素序列11,13, 15,7,8, 9,23,2, 5是采用下列排序算法之一，得到的第2趟排序后的结果，则该排序算法是（ A ）A.直接插入排序 B.冒泡排序C.选择排序 D.二路归并排序14.在长度为n (n100) 的有序线性表中进行二分查找，查找成功时，查找长度不多于4的关键字个数是（ C ）A.4 B.7C.15 D.10015.将下列数据分别依次插入到初始为空的二叉排序树中，能得到高度最低二叉排序树的是（ B ）

6、A.9,7,2,1,4,10 B.6,4,1,8,10,5C.5,1,2,6,3,4 D.2,4,7,5,8,10二、填空题:本大题共10小题，每小题2分，共20分。16.非空的带头结点的单循环链表中，终端结点的指针域指向的是链表的（ 头结点 ）。17.己知循环队列存储在- -维数组A0.n-1中，头指针是front,尾指针是rear,初始时front的值和rear的值均是0，则第1个入队元素存储在数组中存储位置的下标是（ 0 ）。18.将中缀表达式9-(2+4*7)转换为后缀表达式的结果是（ 9 2 4 7 *+ - ）。19.广义表G= (27, G)的深度是（ ）。20.具有n (n1)

7、个结点的二叉树，采用二叉链表存储，空指针域的个数是（ n+1 ）。21.两个无向连通图均含有10 个顶点，它们之间的边数差最大是（ 36 ）。22.有向图G存在拓扑序列的条件是（ 图中不存在环（或无环） ）。23.若用C语言的数组A保存含n (n10) 个元素的大根堆，则第3大元素在A中的下标最大是（ 6 ）。24.分块查找又称为（ 索引顺序查找 ）。25.非空的3阶B树中，每个非根结点中含有的关键字个数最少是（ 1 ）三、解答题:本大题共4小题，每小题5分，共20分。26.链栈为什么不必设置头结点?答：链栈是运算受限的单链表，链表的头指针可以看作是栈顶指针，入栈和出栈操作仅限制在表头位置（栈

8、顶）进行，因此不必设置头结点。（5分）27.已知字符集 a,b,c, d,e 中各字符出现的频次分别为2,3, 6, 8, 10,对字符集进行哈夫曼编码，字符a的编码是000,字符e的编码是11,则其余3个字符的编码分别是什么?答：字符b的编码是001，（1分）字符c的编码是01，（2分）字符d的编码是10。（2分）28.设有向图G如题28图所示，给出图G的邻接矩阵。 答： 29.设有关键字16, 15,32, 11, 6, 30，将它们依次保存在哈希表(长度为7的一维数组)中，哈希函数为H(k) = k mod 7,采用线性探查法解决冲突。已知关键字16已放置在数组下标为2的位置。请画出哈希

9、表。答：四、算法阅读题:本大题共4小题，每小题5分，共20分。30.程序f30( )创建了一个带头结点的含n (n3)个数据结点的单链表L, L前两个数据结点中的data值均为1,从第3个结点开始，结点的data值是其前两个结点data值之和。请在空白处填上适当内容将算法补充完整。答：(1)preOne-data+preOne-next-data （2分）(2)NULL（或prenOne-next-next） （1分）(3)preOne-next-next （2分)答：(1)count=0 （2分）(2)g.arcsij!=0（或g.arcsij=1或g.arcsij） （2分）(3)countmax （1分）答：(1)对给定的两个整数k1和k2，按升序输出二叉排序树中所有满足k1结点值k2的值。（3分）(2)154，170，275，503，509，512，612。 （2分）答：(1)f33=2 （2分）(2)在数组中釆用二分查找（折半查找）法查找指定元素，若查找成功，则返回指定元素在数组中的下标；如果查找失败，则返回-1。 （3分）五、算法设计题：本题10分。34.设n个整数存放在数组A中，请编写函数f34(intA,intn),将所有奇数调整到所有偶数之前。答：