《数据结构》四川大学 - 期终复习试题+答案

模拟试题（四）

一、单项选择题（每小题 2 分，共20分）

（1）以下数据结构中哪一个是线性结构？（ ）

A）有向图 B）栈 C）二叉树 D）B树

（2）若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（ ）存储方式最节省时间。

A）单链表 B）双链表 C）带头结点的双循环链表 D）单循环链表 （3）（ ）不是队列的基本运算。

A）在队列第i个元素之后插入一个元素 B）从队头删除一个元素 C）判断一个队列是否为空 D）读取队头元素的值

（4）字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（ ）个不同的字符串？

A）15 B）14 C）16 D）21

（5）由权值分别为4,7,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（ ）。

A）11 B）37 C）19 D）53

以下6-8题基于下面的叙述：若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G，后序遍历的序列为B、D、C、A、F、G、E。

（6）则该二叉树结点的前序遍历的序列为（ ）。

A）E、G、F、A、C、D、B B）E、A、G、C、F、B、D C）E、A、C、B、D、G、F D）E、G、A、C、D、F、B （7）该二叉树有（ ）个叶子。

A）3 B）2 C）5 D）4 （8）该二叉树的按层遍历的序列为（ ）。

A）E、G、F、A、C、D、B B）E、A、C、B、D、G、F C）E、A、G、C、F、B、D D）E、G、A、C、D、F、B （9）下面的二叉树中，（ ）不是完全二叉树。

（10）设有关键码序列(q,g,m,z,a)，（ ）序列是从上述序列出发建的小根堆的结果。

A）a,g ,m,q,z B）a,g,m,z,q C）g,m,q,a,z D）g, m, a,q,z 二、（本题8分）

试述顺序查找法、折半查找法和分块查找法对被查找的表中元素的要求，对长度为n的查找表来说，三种查找法在查找成功时的查找长度各是多少？

三、（本题8分）

设有一个输入数据的序列是{ 46, 25, 78, 62, 12, 80 }，试画出从空树起，逐个输入各个数据而生成的二叉排序树。

四、（本题8分）

给定一个关键字序列｛24，19，32，43，38，6，13，22｝，请写出快速排序第一趟的结果；堆排序时所建的初始堆；然后回答上述两种排序方法中哪一种方法使用的辅助空间最小，在最坏情况下哪种方法的时间复杂度最差？

五、（本题8分）

设二维数组A[0:10,-5:0]，按行优先顺序存储，每个元素占4个单元，A[0][-5]的存储地址为1000，则A[9][-2]的存储地址为多少？

六、（本题8分）

用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。

七、（本题8分）

请说明对一棵二叉树进行前序、中序和后序遍历，其叶结点的相对次序是否会发生改变？为什么？

八、（本题8分）

对于如下图所示的G，用Kruskal算法构造最小生成树，要求图示出每一步的变化情况。

九、（本题9分）

已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。 先序序列：ABCDEFGHIJ 中序序列：CBEDAGHFJI 十、（本题15分）

已知二叉排序树采用二叉链表存储结构，根结点的指针为T，请写出递归算法，从小到大输出该二叉排序树中所有关键字值≥K的结点的关键字的值。

模拟试题（四）参考答案

一、单项选择题（每小题 2 分，共20分） （1）B （2）C （3）A （4）B （6）C （7）A （8）C （9）C

（5）B

（10）B

二、（本题8分）

三种方法对查找的要求分别如下： ? ? ?

顺序查找法：表中元素可以任意存放；

折半查找法：表中元素必须以关键字的大小递增或递减的次序存放：

分块查找法：表中元素每块内的元素可任意存放，但块与块之间必须以关键字的大小递增（或递减）存放，即前一块内所有元素的关键字都不能大于（或小）后一块内任何元素的关键字。 三种方法的平均查找长度分别如下：

顺序查找法：查找成功的平均查找长度为

? ? ?

n?1； 2折半查找法：查找成功的平均查找长度为log2(n+1)+1； 分块查找法：若用顺序查找确定所在的块，平均查找长度为

1n(?s)?1；若用2s折半确定所在块，平均查找长度为log2(三、（本题8分） 如下图所示：

ns?1)?。 s2

四、（本题8分）

快速排序的第一趟结果为｛22,19,13,6,24,38,43,12｝；堆排序时所建立的初始大顶堆如所图所示：

两种排序方法所需辅助空间：堆是O(1)，快速排序是O(logn)，可见堆排序所需辅助空间较少；在最坏情况下两种排序方法所需时间：堆是O(nlogn)，快速排序是O(n2)，所以，可见快速排序时间复杂度最差。

?

注意：快速排序的平均时排序速度最快，但在最坏情况下不一定比其他排序方法快。

五、（本题8分）

依题意A的起始地址为1000，则有：

Loc(9,-2)=1000+[(9-0)*(0-(-5)+1)+(-2-(-5))]*4=1228。 六、（本题8分）

先画出该二叉树的树形结构。对其进行后序遍历得到后序序列为：HIDJKEBLFGCA。

七、（本题8分）

二叉树任两个中叶结点必在某结点的左/右子树中，三种遍历方法对左右子树的遍历都是按左子树在前、右子树在后的顺序进行遍历的。所以在三种遍历序列中叶结点的相对次序是不会发生改变的。

八、（本题8分）

用Kruskal算法构造最小生成树的过程如下图所示：

九、（本题9分）

先由先序序列的第一个结点确定二叉树的根结点，再由根结点在中序序列中左侧部分为左子树结点，在右侧部分为右子树结点，再由先序序列的第一个结点确定根结点的左右孩子结点，由类似的方法可确定其他结点，如下图所示。

十、（本题15分）

由于二叉排序树是中序有序的，因此对二叉排序树采用中序遍历依次输出大于等于K