1、2021年4月高等教育自学考试全国统一命题考试数据结构试卷(课程代码02331)一、单项选择题:本大题共15小题，每小题2分，共30分。1.下列选项中，不属于线性结构的是（ D ）A.线性表 B.双向链表C.循环队列 D.二叉树2.某线性表L含有n个元素，采用单循环链表保存，仅有尾指针指向链表的终端结点。在最后一个结点之后插入一个结点及删除第一个结点的时间复杂度分别是（ A ）A.0(1)和O(1) B.0(1)和O(n)C.O(n)和O(1) D.0(n)和O(n)3.下列应用中会用到栈的是（ A ）A.计算后缀表达式的值 B.图的广度优先遍历C.对数组进行希尔排序 D.对散列表进行查找4.
2、设栈初始为空，入栈序列为1,2,3,4,5，下列选项中，不可能得到的出栈序列是（ B ）A.1,2,3,4,5 B.3,1,4,2,5C.4,3,2,5,1 D.5,4,3,2,15.已知广义表LS=(c,(d),(e,(f),(g,h),(m,n),head(LS)是（ D ）A.c B.(c)C.(c,(d) D.(c,(d),(e,(f)6.设线性表采用顺序存储方式保存，每个元素占8个存储单元。第1个元素的存储地址为200，则第5个元素占用的最后一个存储单元的地址是（ A ）A.239 B.240C.247 D.2487.一棵完全二叉树T的全部k个叶结点都在同一层中，每个分支结点都有两个
3、孩子结点。T中包含的结点数是（ B ）A.k B.2k-1C.k2 D.2k-18.设字符集中有n个字符,对其进行哈夫曼编码，得到的哈夫曼树的结点总数是（ A ）A.2n-1 B.2nC.2n+1 D.不确定9.设图G的邻接矩阵A如下所示。G的各顶点的度依次是（ C ） A.1,2,1,2 B.2,2,1,1C.3,4,2,3 D.4,4,2,210.对题10-11图进行深度优先遍历，下列选项中，正确的遍历序列是（ A ） A.1,2,3,4,5 B.2,3,5,4,1C.3,5,1,2,4 D.4,3,5,1,211.对题10-11图进行拓扑排序，下列选项中，正确的拓扑序列是（ D ）A.1
4、,2,3,4,5 B.2,3,1,4,5C.3,5,1,2,4 D.5,3,1,2,412.下列排序方法中，不是稳定排序方法的是（ D ）A.直接插入排序 B.冒泡排序C.归并排序 D.快速排序13.已知数据序列(18,19,20,4,51,6,30,1,2)是某种排序算法第二趟排序后得到的结果，则该算法可能是（ C ）A.选择排序 B.冒泡排序C.直接插入排序 D.快速排序14.对有序表(1,3,9,12,32,41,45,62,75,77)进行二分查找，查找关键字9时，进行比较的关键字依次是（ B ）A.1,3,9 B.32,3,9C.32,12,9 D.41,12,915.分别使用下列数
5、据序列建立二叉排序树，能得到高度最高的二叉树的是（ B ）A.10,8,9,6,12,11,13 B.10,6,8,9,12,11,13C.10,12,11,13,8,6,9 D.10,8,6,9,12,13,11二、填空题:本大题共10小题，每小题2分，共20分。16.数据的运算，即对数据元素施加的操作，是定义在数据的（ 逻辑 ）结构上的。17.在顺序表中，因为访问任一结点的方式是（ 随机访问 ）,所以访问每个结点的时间复杂度均为0(1)。18.带头结点的链队列可以由一个头指针和一个尾指针唯一确定。当头指针和尾指针相等时，表示队列（ 为空 ）19.稀疏矩阵采用压缩存储，只保存非零元素，得到的
6、顺序存储结构称为（ 三元组表 ）20.广义表(a),(b,c),(d,e,(f,g,h)的表尾是（ （b,c），（d,e,（f,g,b） ）21.中序线索化二叉树的过程，是在中序遍历过程中用线索取代（ 空指针 ）22.在有n个顶点、e条边的无向连通图中，e的取值范围是（ n-1WeWn(n-1) /2 ）23.对数据序列进行升序排序。采用堆排序算法时，首先应对初始数据建立（ 大 ）堆。24.在无序数组中进行查找操作，应使用的查找方法是（ 顺序查找（或线性查找） ）25.一棵高度为2的4阶B树中能够保存的关键字个数最多是（ 15 ）三、解答题:本大题共4小题，每小题5分，共20分。26.请画出题
7、26图所示的二叉树对应的树或森林。 答： 27.求题27图从顶点A到其余各顶点的最短路径，给出各条路径包含的顶点序列及路径长度。 答： 28.有以下数据序列(20,84,19,14,23,01,68,27,55,11,10,79,12),使用二路归并排序算法将其排成升序序列。给出各趟排序结果。答：初始：20，84，19，14，23，01，68，27，55，11，10，79，12一趟归并：20，84，14，19，01，23，27，68，11，55，10，79，12 （1分）二趟归并：14，19，20，84，01，23，27，68，10，11，55，79，12 （2分）三趟归并：01，14，19，
8、20，23，27，68，84，10，11，12，55，79 （1分）四趟归并：01，10，11，12，14，19，20，23，27，55，68，79，84 （1分）29.设有以下关键字:15,72,52,65,23,68，散列函数H(key)=key%7,散列表空间为0-6,采用线性探查法解决冲突。请回答下列问题。(1)构造散列表。(2)计算等概率情况下查找成功时的平均查找长度。答：(1)【评分说明】散列表中每正确填入2个项，给1分。(2)ASL查找成功=12/6=2 （2分）四、算法阅读题:本大题共4小题，每小题5分，共20分。30.答：(1)30，2，10，9，5，3 (3分)(2)根据所给的数据建立顺序表，将偶数从表头插入，奇数从表尾插入。(2分)答：(1)-38，-256，256，9，25，47，128，4，64 （3分）(2)找到数组中第一个非负数的位置。 （2分）答：(1)16 18 25 36 50 （3分）(2)查找二叉排序树T中所有满足大于等于K1且小于等于K2的元素，并按升序输出。（2分）答：(1)j=n （2分）(2)Rj.keyRk.key （2分）(3)k!=i （1分）五、算法设计题：本题10分。答：【评分参考】只要程序正确同样给分；部分正确，酌情给分。
