由（1）（2）及pj?n可知由1,2,…,n可通过一个栈得到序列p1,p2,…,pn。由数学归纳法可知本题结论成立。
四、（本题8分）
【解答】由弗洛伊德（Floyd）算法进行求解，具体步骤如下：
D(?1)?0129?3??0129?3??1206????1206?15?????(0)??9604??，D??960412?； ??????406??406???????3??60???3151260??D(1)?0129?3??0129133??1206?15??12061015?????(2)??960412?，D??960412?； ??????4061310406???????3151260???3151260???0129133??012993??12061015??12061015?????(4)??960412?，D??960410?。 ????1310406910406???????3151060???3151060??D(3)设乡镇vi到其他各乡镇的最远距离为max_disdance(vi)，则有：max_disdance(v1)=12，
max_disdance(v2)=15，max_disdance(v3)=10，max_disdance(v4)=10，max_disdance(v5)=15，所以可知消防站应建在v3或v4乡镇，才能使离消防站最远的乡镇到消防站的路程最短。
五、（本题8分）
【解答】对n用归纳法证明。当n＝1时，有N1=F3-l=2-l=1到。当n=2时，有N2=F4-1=3-1=2。设n 当n=k+1，对于一个k+l层深度的平衡二叉树而言，其左右子树都是平衡的。结点数为最少的极端情况，故左右子树中的结点数是不相等的，设其中一个是k层深度的二叉平衡树，另一个是k-l层深度的二叉平衡树。所以有： Nk+1=1+Nk+Nk-1==1+(Fk+2-1)+(Fk+1-1)= Fk+2+Fk+1-1= Fk+3 -1 当n=k+1时成立，由此可知深度为n都等式都成立。 六、（本题8分） 【解答】n个结点的平衡二叉树的最大高度为h?log(5(n?1))?2，设表示高度1?52需xbit，则有关系式：2≥h＞2，所以有： ??x??log2h???log2(log1?5(5(n?1))?2)? 2??1?5h?2)（2）设深度为h的平衡二叉树的最少关键字数为nh，则有公式：n?2?1，h5(8 本题中8bit的计数器共可以表示2=256层，即高度为256，从而可知最少有 1?5258()2n??1个关键字。 5七、（本题8分） 【解答】 xx-1 （1）线性探测再散列的哈希表查找成功的平均查找长度为：Snl?解得α≤4／5，也就是12/m≤4／5， 所以m≥15，可取m=15。 （2）散列函数可取为H(key)=key % 13 （3）散列表如表7-4所示。 散列表 0 1 40 2 66 3 94 4 5 5 6 58 7 33 8 47 9 72 10 87 11 22 11(1?)≤3，21??12 25 13 12 14 （4）12个数据 {25，40，33，47，12，66，72，87，94，22，5，58｝的比较次数分 别是：1，1，1，1，2，2，3，2，1，3，1，1。 可知查找成功的平均查找次数=(1+1+1+1+2+2+3+2+1+3+1+1)/12=1.25 八、（本题8分） 【解答】有n个叶子结点的带权路径长度最短的二叉树称哈夫曼树，同理，存在有n个叶子结点的带权路径长度最短的三叉、四叉、……、k叉树，也称为哈夫曼树。如叶子结点数目不足以构成正则的k叉树（树中只有度为k或0的结点），即不满足(n-l)MOD(k-l)=0，k-(n-1)MOD(k-1)-1。需要添加权为0的结点，添加权为0的结点的个数为：添加的位置应该是距离根结点的最远处。 所构造出的哈夫曼树如下图所示： 其中，每个字母的编码长度等于叶子结点的路径长度，电文的总长度为 ?wl=191。 iii?1n 注释：对于正则的k叉树，设叶结点数为n，度为k的结点数为nk，结点总数为m, 则有m-1=knk，m=nk+n，两式相减可得n-1=(k-1)nk，即(n-l)MOD(k-l)=0；如n与k不满足此关系，n加上k-(n-1)MOD(k-1)-1后，n’= n+(k-(n-1)MOD(k-1)-1)，这时： (n’-l)MOD(k-l)=(n+(k-(n-1)MOD(k-1)-1)-l)MOD(k-l) =((n-1)+(k-1)-(n-1)MOD(k-1))MOD(k-l) =((n-1)-(n-1)MOD(k-1))MOD(k-l) =0。 现有12个初始归并段，其记录数分别为｛30,44,8,6,3,20,60,18,9,62,68,85｝，采用3-路平衡归并，画出最佳归并树。 九、（本题9分） 【解答】设该树中结点总数为N，叶子结点个数为N0，则有： N??Ni i?0m （1） N?1??iNi i?1mm （2） 由（2）-（1）再经过移项可得：N0?1??(i?1)N ii?1十、（本题15分） 【解答】 对于排列的解空间可构造一个虚拟的解空间树，比如n=5，k=3时的解空间树如下图所示，可采用对此树进行先序遍历方式进行遍历，并用递归法进行递归输出从n个数中挑选 k个进行排列所得序列。 具体算法实现如下： // 文件路径名:exam7\\alg.h template void Arrage(ElemType a[],int k,int n, int outlen=0) // 操作结果: 回溯法输出排列序列，a[0..k-1]为k个数的排列序列outlen为当前所求排列 // 序列的长度，其中outlen=k时的排列序列为所求；n为list数组长度 { if (k < 0 || k >= n) return; // 此时无排列 int i; // 临时变量 if (outlen == k + 1) { // 得到一个排列 for (i = 0; i < k; i++) { // 输出一个排列 cout << a[i]; // 输出a[i] } cout << \ \ // 用空格分隔不同排列 } else { // 对解空间进行前序遍历，a[outlen..n]有多个排列，递归的生成排列 for (i = outlen; i < n; i++) { // 处理a[i] Swap(a[outlen+1], a[i]); // 交换a[outlen+1]与a[i] Arrage(a, k, n, outlen + 1); // 对序列长度outlen+1递归 Swap(a[outlen+1], a[i]); // 交换a[outlen+1]与a[i] } } } *模拟试题（八） 注：本套试题选作