全国2019年4月自考02142数据结构导论试题及答案

1、一、草项迭择題：*大亀共15小題每小& 2分共30分。在每小通列出的备选项中只有一项 是符合题目要求的请将其选出。I.下列几种时间复杂度中，阶数呂小的是A.O（log2n）B.O（n）2 栈和队列的共同待点是A.都是线性表B.先进先出C.O(n:)D.O(l)C.后进先出D只能插入操作绝老启用前2019年4月高等教育自学考试全国统一命题考试数据结构导论（课程代码02142）注意事项：1. 本试卷分为两部分，第一部分为选择題，第二部分为非选择題。2. 应考者必須按试亀顺序在答!卡（纸）指定位上作答，答在试卷上无效。3. 涂写部分画图都分必须便用2B铅笔，书写部分必须便用黑色字迹签字笔。第

2、一部分选择题3.假设一个10X10的上三角矩阵A按照列优先順序压编存储在一维数组B中，则B效组的 大小应为D.101A.50B.55C.1004一个栈的入栈序列是a, b. c, d. s则栈可能的输岀序列是D.dceabA.edcabB.deabcC.abcde5假定一个順序存储的循环队列的队头和队尾折针分别为f和“則判断队空的条件为A.f = = NULLB.f = rCr+1 = = fDf+1 = = r6如果结点A有2个兄弟结点结点B为A的双亲，则结点B的度为A.2B.3C.4D.57二叉树的中序遍历中结点P排在结点Q之前的条件是在二叉树中A.P在Q的左边B.P在Q的右边C.P是Q的

3、祖先 D.P是Q的子孙&二叉树的第k层的结点数最多为A.2k-1B2+C.2klD.2®9.A是7X4的二维数组按行优先方式顺序存储元素A00的存储地址为1000若每个元 索占2个字节则元素A33的存储地址为D.1032A.1O26B.1028C.1030数据结构导论试题第1页（共3页）10在表长为n的顺序表上做删除运算其平均时间复杂度为A.O(l)B.O(n)C.O(nIog:n)D.O(n,)11. 庄含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为A.eB.2eC.n:eD.n1 2e12. 设顺序表的长度为n,则插入算法的平均移动次数约为A.nB.n/2C.n-

4、1D.(n-l)/213 设一组初始记录关犍字序列为(13,18.24.35.47.5O.62.83.90,115.134).则利用二分査找算法査找关键字90需要比较的关键字个数为A.1B.2C.3D.414.以下排序方法中，稳定的是A.直接插入排序和快速排序B.快速排序和胃泡排序C.直接选择排序和冒泡排序D.H泡排序和克接插入排序15对D个记录的文件进行快速排序所需耍的辅助存储空间的空间复杂度为, i .：.v .； j -； .? , .t r ： >.A.O(1)B.O(n)C.O(log:n)D.OCn1)s第二部分非选择题二、填空题：本大题共13空，毎空2分，共26分。16.1

5、976年瑞士计算机科学家Niklaus Wirth忡提出一个着名公式：程序=数据结构+ 个利黑t 廿厶17.简单地说，数据结构是计算机_厶_数据和存储数据的方式.1&线性表中结点个数n称为 ,19.线性表上的插入和制除运算限定在表的某一端进行的数据结构是.A20 对稀嫌矩阵进行压缩存储的目的是节省21 个具有n个顶点的有向完全图的弧数为巴= 22构造最小生成树的算法冇两种：Prim算法和 _算法.23. 棵树的结点个数最少为24. 有K个叶子结点的哈夫曼树，其结点的总数为_ _25由二叉树的后序序列和 序列可以唯一确定一棵二叉树26 二分査找算法的平均时间复杂度为A_.27 若待排序的

6、序列中存在多个记录具有相同的键值经过排序这些记录的相对次序仍然保持不变则称这种排序方法是 的.28在最坏悄况下即对几乎已是排好序的入序列快速排序算法的效率较低此时其时间复杂度近似为数据结构导论试题第2页(共3页)三、应用&：本大BS共5小&毎小聽6分共30分。29. 有一个轅数序列其输入顺序为20,30.90, 10,45,78.试利用栈将其输岀序列改变为30,10.45.90.78.20.写出谏粮数序列进栈和出栈的操作步骤。(用push(x)表示x进栈, pop(x)表示X出栈)/30. 分别写出题30图所示的二叉树的先序遍历、中序遍历和后序遍历三种访问方式的结点访问序列C；£ 訂题30图31 设有字符集 A. B, C, D, E, F ,各字符使用频率对应为2. 4, 5, 13, 9, 18,试画出哈 夫曼树(要求任一结点的左孩子权值小于右孩子).32.已知散列表的长度为11,散列阪数H(key) = key%ll,采用线性探测法解决冲突，试用关 键字值的序列：75,25,80,35,60,46.50,55建立散列表。33试用冒泡法对数列(45. 73, 12, 23, 52, 5, 38)进行递增排序，写出第1、2、3、4趙排序结 果，并给出冒泡排序算法的时间