1、2020年10月高等教育自学考试全国统一命题考试数据结构试卷(课程代码02331)一、单项选择题:本大题共15小题，每小题2分，共30分。1.数据结构研究的基本内容是（ A ）A.数据的逻辑结构、存储结构和对数据元素施加的操作B.数据的类型、数据的定义、算法描述和各种操作实现C.数据的线性结构、树型结构、图型结构及相关的算法D.数据元素之间的逻辑关系、物理存储和相关程序实现2.数据结构中，评价算法好坏的重要指标之一是（ D ）A.程序的执行时间 B.源程序的代码长度C.程序采用的语言 D.算法的时间复杂度3.等概率情况下，在长度为n的顺序表中插入1个元素需要移动元素的平均次数是（ B ）A.1
2、 B. n/2C. N D. n+14.已知head 为指向带头结点的单链表的头指针，指针变量p指向一个新结点，next是结点的指针域，若要将p所指结点插入到单链表的表头，则正确的语句序列是（ D ）A. head-next= p; p-next= head; B. p-next = head-next; head = p;C. head = p; p-next = head-head; D. p-next = head-next; head-next p;5.后缀表达式求值的过程中要用到的数据结构是（ B ）A.一个保存各种操作符的栈 B.一个保存操作数及运算结果的栈C.两个分别保存操作符和
3、操作数的栈 D.两个分别保存操作数和运算结果的栈（ D ）（ A ）8.用n (n2)个带权值的结点作为叶结点构造一 棵哈夫曼树， 下列选项中正确的是（ B ）A.哈夫曼树是叶结点权值之和最小的二叉树B.哈夫曼树是带权路径长度WPL最小的二叉树C. n个带有权值的结点可以构造出唯一棵哈夫曼树D.哈夫曼树是有n个叶结点的二叉树中高度最低的二叉树9.将一棵树T转换为等价的二叉树T1，与T的后序遍历序列相同的是T1的（ B ）A.前序遍历序列 B. 中序遍历序列C. 后序遍历序列 D. 按层遍历序列.10. 要在带权图(权值0)中求从某一顶点到其余各顶点的最短路径，应采用的算法是（ D ）A.哈夫曼
4、算法 B.普里姆算法C.克鲁斯卡尔算法 D.迪杰斯特拉算法11.设图G存在拓扑序列，则下列结论中正确的是（ D ）A.图G是一个有向图 B.图G的拓扑序列唯一C.图G是一个无向图 D.图G是一个有向无环图.12.内排序过程中，待排序数据保存在（ B ）A. CPU中 B.内存储器中C.外存储器中 D.计算机中13.下列排序方法中，关键字总的比较次数与记录的初始排列次序无关的是（ D ）A.冒泡排序 B.希尔排序C.直接插入排序 D.直接选择排序14.散列查找方法可以达到的最好时间复杂度是（ A ）A.0(1) B. O(n)C. O(log n) D.0(n2)15.下列关于二分查找判定树T的
5、叙述中，正确的是（ A ）A. T是一棵二叉树 B. T是一棵满二叉树C. T是一棵完全二叉树 D. T的叶结点在同一层二、填空题:本大题共10小题，每小题2分，共20分。16.算法必须满足的五个准则是:输入、输出、有穷性、确定性和（ 可行性 ） 17.将100个数据元素保存在顺序表中，若第一个元素的存储地址是1000,第二个元素的存储地址是1004，则该顺序表最后一个元素的存储地址是（ 1396 ） 18.循环队列保存在长度为M的数组中，队头为front, 队尾为rear,若要求队满时条件为真，则条件表达式应是（ （rear+1）%M=front ） 19.广义表()的长度是（ 1 ） 20
6、.具有n个结点的完全二叉树的深度为（ ） 21.图G的邻接矩阵不是一个对称矩阵，则图G一定是（ 有向 ）图。22.顶点表示活动、边表示活动间先后关系的有向无环图称为（ 顶点活动（或AOV） ）网。23.在排序过程中，如果具有相同关键字的记录之间的相对次序保持不变，则称该排序方法是（ 稳定 ）的。24.对二叉排序树BT进行（ 中序 ）遍历可以得到BT中所有结点的有序序列。25.在一棵25阶的B树中，非根结点内所包含的关键字个数至少是（ 12 ）个。三、解答题:本大题共4小题，每小题5分，共20分。26.将中缀表达式“a*(b+c)”转换为后缀表达式，请回答下列问题。(1)画出转换过程中栈的变化过
7、程。(2)写出转换后得到的后缀表达式。答：(1)栈的变化过程如下。(2)后缀静态式：abc+* （1分）27.已知二叉树T的前序遍历序列为: a d b c e, 中序遍历序列为: d a c e b.请回答下列问题。(1)画出对应的二叉树T。(2)建立并画出二叉树T的后序线索。答： 28.求题28图的最小生成树。要求:按照克鲁斯卡尔算法的思想，依次写出进入最小生成树的边。 答：权值依次为：1,2,3,4,7。29.已知数据序列(19, 14, 23, 01, 68, 79, 84, 27,55, 11, 10)，请画出建立大根堆的过程。答：答：(1)输出结果：019(2)输入n等于5，且5大于2，返回值5+f30（5-2），即5+f30（3）；输入n等于3，且3大于2，返回值3+f30（3-2），即3+f30（1）；输入n等于1，且01next答：(1)输出结果：2，10，12，24，33，43，50，66，88。(2)存储排序增量。(3)对待排关键字序列进行希尔排序。答：
