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

1、2022年4月高等教育自学考试全国统一命题考试数据结构试卷(课程代码02331)一、单项选择题:本大题共15小题，每小题2分，共30分。1.下列数据结构中，与存储结构相关的是（ C ）A.线性表 B.栈C.链队列 D.二叉树2.将20个数据元素的线性表存储在数组中，若第9个元素的存储地址是1000,第11个元素的存储地址是1040，则最后一个元素的存储地址是（ D ）A.1200 B.1210C.1215 D.12203.设栈的初始状态为空，元素1,3,5,2,4依次入栈，不能得到的出栈序列是（ A ）A.5,1,3,2,4 B.4,2,5,3,1C.2,4,5,3,1 D.1,3,5,2,4

2、4.设指针变量p指向非空单链表中的结点，next是结点的指针域，现要删除p所指结点的所有后继结点，则下列语句中正确的是（ D ）5.已知广义表LS=（(a,b),(c,d),(e,f,(g,h,i)），LS的深度是（ B ）A.2 B.3C.4 D.56.已知一棵高度为4的完全二叉树T的第4层上共有3个叶子结点，则T中叶子结点的个数是（ B ）A.4 B.5C.6 D.77.已知二叉树T的前序遍历序列为a,b,c,d,e,则前序遍历序列与T相同的不同二叉树个数(不包含T)是（ C ）A.11 B.12C.13 D.148.采用邻接矩阵存储含n个顶点和e条边的有向图G，邻接矩阵中0的个数是（ A

3、 ）A.nn-e B.nn-2eC.n(n-1)/2-e D.n(n-1)/2-2e9.无向图中所有项点的度数之和是10，则顶点的最大度数是（ A ）A.5 B.6C.7 D.1010.设有向图G含有n个顶点、e条边,使用邻接矩阵存储。对G求拓扑序列算法的时间复杂度是（ C ）A.0(n) B.O(e)C.0(n2) D.O(ne)11.对数据序列(15,12,13,12,8,4,5)采用冒泡排序进行升序排序，两趟排序后得到的排序结果是（ B ）A.12,13,12,8,4,5,15 B.12,12,8,4,5,13,15C.5,4,8,12,12,13,15 D.4,5,8,12,12,13

4、,1512.下列选项中，稳定的排序方法是（ A ）A.直接插入排序 B.直接选择排序C.希尔排序 D.堆排序13.关键码序列为30,77,57,12,25,86,建立的初始大根堆是（ B ）A.77,30,57,12,25,86 B.86,77,57,12,25,30C.86,77,57,30,25,12 D.86,57,77,25,30,1214.在一棵二叉排序树中，关键字n所在结点是关键字m所在结点的孩子结点，则（ D ）A.n一定大于m B.n一定小于mC.n一定等于m D.n与m的大小关系不确定15.设散列表长m=14,散列函数H(key)=key%13。采用线性探测法处理冲突。表中已

5、按散列地址保存了3个关键字16,30,18，此时存储关键字29的探查次数是（ D ）A.1 B.2C.3 D.4二、填空题:本大题共10小题，每小题2分，共20分。16.链栈、顺序队列的存储结构不同，数据的运算也不同，它们的（ 逻辑 ）结构相同。17.若指针p和q分别指向单链表L中的两个相邻结点，且q指向的是终端结点。则在p所指结点之后插入指针r所指结点的语句是r-next=q;（ p-next=r ）；。18.实现递归函数调用和返回的数据结构是（ 栈 ）19.广义表(a,b),(c,d),(e,f),(g,h)的表尾是( （c,d),(e,f),(g,h) )20.已知完全二叉树的按层遍历序

6、列存储在一维数组A0.n-1中，则Ai(1in-1)的父结点是（ A（i-1）/2 ）21.如果有向无环图G中至少有两个顶点的入度为0，则G中至少有（ 2 ）个不同的拓扑序列。22.将森林T转换为一棵二叉树T1,则T中叶子结点在T1中满足的条件为（ 无左孩子 ）23.对含n个元素的数据序列采用二路归并排序算法进行排序，算法的时间复杂度是（ O（nlogn） ）24.散列表的平均查找长度不是结点个数n的函数，而是（ 装填因子 ）的函数。25.假设顺序存储的有序表R含有13个关键字，进行二分查找时，查找成功时平均查找长度为（ 41/13 ）三、解答题:本大题共4小题，每小题5分，共20分。26.设

7、电文字符集是e1,e2,e3,e4,e5,e6,各字符出现的频次分别为20,21,1,15,22,3。现要为该字符集设计哈夫曼编码。请回答下列问题。(1)给出构造的哈夫曼树。答：(2)给出各字符的哈夫曼编码。答：27.已知图G采用邻接矩阵存储，邻接矩阵如题27图所示。 (1)根据邻接矩阵画出图G.(2)写出图G的从顶点A开始的1个拓扑序列。答：28.有数据序列(15,16,04,12,21,23,43,31,16,13)，使用希尔排序方法将其排成升序序列。请回答下列问题。(1)分别写出增量序列的取值依次为4,1的希尔排序结果。(2)计算增量为4时希尔排序中数据元素之间的总交换次数(两个元素之间的交换记1次)。答：29.设二叉排序树T如题29图所示。现需在T中删除结点22。请回答下列问题。(1)删除结点22有几种不同的方法?(2)分别画出对应于(1)中不同方法删除结点22后的二叉排序树。 答： 四、算法阅读题：本大题共4小题，每小题5分，共20分。 答：(1)30 （2分）(2)分别计算两个顺序表中元素的平均值，输出最大的平均值。（3分）答：(1)A C D E B (3分)(2)O(n) (2分)答： 答：五、算法设计题：本题10分。答：