九、（本题9分）
先由先序序列的第一个结点确定二叉树的根结点，再由根结点在中序序列中左侧部分为左子树结点，在右侧部分为右子树结点，再由先序序列的第一个结点确定根结点的左右孩子结点，由类似的方法可确定其他结点，如下图所示。
十、（本题15分）
可按先遍历右子树，遍历根结点，再遍历左子树进行中序遍历，这样可实现由大到小遍历一棵二叉排序树。
具体算法实现如下：
// 文件路径名:exam4\\alg.h #include \ // 二叉排序树类
template
void InOrderHelp(BinTreeNode
// 操作结果: 从大到小输出以r为根的二叉排序树中所有的关键字值小于key的元素值 { if (r != NULL) { // 非空二叉排序树 InOrderHelp(r->rightChild, key); // 遍历右子树 if(r->data < key) cout << r->data << \ \ // 输出根结点 else return; InOrderHelp(r->leftChild, key); // 遍历左子树 } }
template
void InOrder(const BinarySortTree
}
// 调用辅助函数实现从大到小输出二叉排序树中所有的关键字值不小于key的元素值
模拟试题（五）
一、单项选择题（每小题 2 分，共20分） （1）队列的特点是（ ）。
A）先进后出 B）先进先出 C）任意位置进出 D）前面都不正确 （2）有n个记录的文件，如关键字位数为d，基数为r，则基数排序共要进行（ ）遍分配与收集。
A）n B）d C）r D）n - d
（3）在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（ ）。
A）都不相同 B）完全相同 C）先序和中序相同，而与后序不同 D）中序和后序相同，而与先序不同 （4）限定在一端加入和删除元素的线性表称为（ ）。
A）双向链表 B）单向链表 C）栈 D）队列
（5）若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（ ）。
A）起泡排序 B）插入排序 C）选择排序 D）二路归并排序 （6）设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是（ ）。
A）m-n-1 B）n+1 C）m-n+1 D）m-n （7）对于具有n个顶点的强连有向图，其弧条数的最小值为（ ）。
A）n+1 B）n C）n-1 D）n-2 （8）下面关于广义表的叙述中，不正确的是（ ）。
A）广义表可以是一个多层次的结构 B）广义表至少有一个元素 C）广义表可以被其他广义表所共享 D）广义表可以是一个递归表
（9）设二叉树根结点的层次为0，一棵深度（高度）为k的满二叉树和同样深度完全二叉树各有f个结点和c个结点，下列关系式不正确的是（ ）。
A）f>=c B）c>f C）f=2k+1-1 D）c>2k-1
（10）设一棵二叉树中没有度为1的结点，已知叶子结点数为n，此树的结点数为（ ）。
A）2n+2 B）2n+1 C）2n D）2n-1 二、（每小题4分，共8分）
写出下列中缀表达式的后缀形式：
（1）3X/(Y-2)+1 （2）2+X*(Y+3) 三、（每小题4分，共8分） 试对如下图中的二叉树画出其：
（1）顺序存储表示；
（2）二叉链表存储表示的示意图。 四、（每小题4分，共8分）
判断以下序列是否是小根堆? 如果不是，将它调整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 }
（2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 五、（本题8分）
已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7};
E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各条边。
六、（每小题2分，共8分）
设有12个数据25,40,33,47,12,66,72,87,94,22,5,58，它们存储在散列表中，利用线性探测再散列处理冲突，取散列函数为H(key)=key % 13。
（1）顺次将各个数据散列到表中，并同时列出各元素的比较次数。 （2）计算查找成功的平均查找次数。 七、（第1小题2分，第2、3小题每小题3分，本题8分） 对于如下图所示的图G，邻接点按从小到大的次序。
（1）图G有几个连通分量？
（2）按深度优先搜索所得的树是什么？
（3）按深度优先搜索所得的顶点序列是什么？ 八、（本题8分） 已知一棵树边为：
{
试画出这棵树，并回答下列问题： （1）哪个是根结点？ （2）哪些是叶子结点？ （3）树的深度是多少？ 九、（本题9分）
给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18)。写出用下列算法从小到大排序时第一趟结束时的序列。
（1）希尔排序（第一趟排序的增量为5） （2）快速排序（选第一个记录为枢轴） 十、（本题15分）
编写复制一棵二叉树的非递归算法。
模拟试题（五）参考答案
一、单项选择题（每小题 2 分，共20分） （1）B （2）B （3）B （4）C （6）D （7）B （8）B （9）B 二、（每小题4分，共8分）
（1）3 X * Y 2 - / 1 + （2）2 X Y 3 + * + 三、（每小题4分，共8分）
（1）二叉树的顺序存储表示如下所示：
0 1 1 2 2 3 3 4 4 5 6 5 7 6 8 9 7 10 11 12 （5）B （10）D
13 8 14 15 16 17 18 9 （2）二叉树的二叉链表存储表示的示意图如下图所示：
四、（每小题4分，共8分）
（1）不是小根堆。调整为：{12,24,33,65,33,56,48,92,86,70} （2）是小根堆。 五、（本题8分）