}
模拟试题（四）
一、单项选择题（每小题 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分）
设有带权无向网Net如下图所示。
试给出：
（1）Net的邻接矩阵表示；
（2）从V1开始的深度优先遍历； （3）从V1开始的广度优先遍历；
（4）从V1开始执行的普里姆（Prim）算法过程中所选边的序列。 六、（本题8分）
用一维数组存放一棵完全二叉树：ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。
七、（本题8分）
已知哈希表地址空间为0..8，哈希函数为H(key)=key%7，采用线性探测再散列处理冲突，将数据序列{100,20,21,35,3,78,99,45}依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度。
八、（本题8分）
对于如下图所示的G，用Kruskal算法构造最小生成树，要求图示出每一步的变化情况。
九、（本题9分）
已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。 先序序列：ABCDEFGHIJ 中序序列：CBEDAGHFJI 十、（本题15分）
试写一递归算法，从大到小输出二叉排序树中所有的关键字值小于key的元素值。 。
模拟试题（四）参考答案
一、单项选择题（每小题 2 分，共20分）
（1）B （2）C （3）A （4）B （5）B （6）C （7）A （8）C （9）C （10）B 二、（本题8分）
三种方法对查找的要求分别如下： 顺序查找法：表中元素可以任意存放；
折半查找法：表中元素必须以关键字的大小递增或递减的次序存放：
分块查找法：表中元素每块内的元素可任意存放，但块与块之间必须以关键字的大小递增（或递减）存放，即前一块内所有元素的关键字都不能大于（或小）后一块内任何元素的关键字。
三种方法的平均查找长度分别如下：
顺序查找法：查找成功的平均查找长度为
n?1； 21n(?s)?1；若用折半2s折半查找法：查找成功的平均查找长度为log2(n+1)+1； 分块查找法：若用顺序查找确定所在的块，平均查找长度为
确定所在块，平均查找长度为log2(三、（本题8分） 如下图所示：
ns?1)?。 s2
四、（本题8分）
快速排序的第一趟结果为｛22,19,13,6,24,38,43,12｝；堆排序时所建立的初始大顶堆如所图所示：
五、（本题8分）
（1）Net的邻接矩阵表示：
???10??3??????????????10??41???3????56???????41???????56??
?????9?????8?????7????7????98?????
（2）从V1开始的深度优先遍历：V1 V2 V4 V8 V5 V3 V6 V7
（3）从V1开始的广度优先遍历：V1 V2 V3 V4 V5 V6 V7 V8 （4）从V1开始执行的普里姆（Prim）算法过程中所选边的序列：
(V1,V3)，(V3,V6)，(V3,V7)，(V1,V2)，(V2,V5)，(V2,V4)，(V5,V8)
六、（本题8分）
先画出该二叉树的树形结构。对其进行后序遍历得到后序序列为：HIDJKEBLFGCA。
七、（本题8分）
哈希表及查找各关键字要比较的次数如下图所示：
ASL=1(4×1+1×2+1×4+2×5)=2.5
8八、（本题8分）
用Kruskal算法构造最小生成树的过程如下图所示：