（6）则该二叉树结点的前序遍历的序列为（ ）。 A）E、G、F、A、C、D、B C）E、A、C、B、D、G、F （7）该二叉树有（ ）个叶子。 A）3
B）2 C）5 D）4
B）E、A、C、B、D、G、F
D）E、G、A、C、D、F、B
（8）该二叉树的按层遍历的序列为（ ）。 A）E、G、F、A、C、D、B C）E、A、G、C、F、B、D
B）E、A、G、C、F、B、D D）E、G、A、C、D、F、B
（9）下面的二叉树中，（ C ）不是完全二叉树。
（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分）
设有一个输入数据的序列是{ 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分）
请说明对一棵二叉树进行前序、中序和后序遍历，其叶结点的相对次序是否会发生改变？为什么？
七、（本题9分）
已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。 先序序列：ABCDEFGHIJ 中序序列：CBEDAGHFJI
八、（本题15分）
已知二叉排序树采用二叉链表存储结构，根结点的指针为T，请写出递归算法，从小到大输出该二叉排序树中所有关键字值≥K的结点的关键字的值。
【答案】==================================
一、单项选择题（每小题 2 分，共20分） （1）B （2）C （3）A （4）B （6）C （7）A 二、（本题8分） 如下图所示：
（8）C
（9）C
（5）B （10）B
三、（本题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分）
二叉树任两个中叶结点必在某结点的左/右子树中，三种遍历方法对左右子树的遍历都是按左子树在前、右子树在后的顺序进行遍历的。所以在三种遍历序列中叶结点的相对次序是不会发生改变的。 七、（本题9分）
先由先序序列的第一个结点确定二叉树的根结点，再由根结点在中序序列中左侧部分为左子树结点，在右侧部分为右子树结点，再由先序序列的第一个结点确定根结点的左右孩子结点，由类似的方法可确定其他结点，如下图所示。
八、（本题15分）
由于二叉排序树是中序有序的，因此对二叉排序树采用中序遍历依次输出大于等于K的结点即可。
C语言版测试程序见exam4\\10c，具体算当如下：
void DisplayKey(BiTree T,KeyType K) // { }
{
}
DisplayKey(T->lchild,K); if(T->data.key>=K)
cout<
//输出右子树 //输出左子树
if(T)
从小到大输出该二叉排序树中所有关键字值≥K的结点的关键字的值
DisplayKey(T->rchild,K);
试题五
一、单项选择题（每小题 2 分，共20分）
（1）队列的特点是（ ）。 A）先进后出
（2）有n个记录的文件，如关键字位数为d，基数为r，则基数排序共要进行（ ）遍分配与收集。 A）n
B）d
C）r
D）n - d
（3）在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（ ）。 A）都不相同
B）完全相同
D）中序和后序相同，而与先序不同
C）先序和中序相同，而与后序不同
B）先进先出
C）任意位置进出
D）前面都不正确
（4）限定在一端加入和删除元素的线性表称为（ ）。 A）双向链表 B）单向链表 C）栈 D）队列 （5）快速排序执行一遍之后，已经到位的元素个数是（ ）。 A）1
（6）设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是（ ）。 A）m-n-1
（7）设有198个初始归并段，如采用K-路平衡归并三遍完成排序，则K值最大为（ ）。
B）n+1
C）m-n+1
D）m-n
B）3
nC）4
nD）2