《数据结构》应用题练习
1、将下图所示的森林转换成二叉树。

2、已知一棵二叉树的中序序列和后序序列分别如下
先序序列：A B D E C F H K G
中序序列：B E D A H F K C G
请完成：（1）画出该二叉树（2分）；
（2）写出该二叉树的后序序列（2分）。

3、对于一组给定的权值W=｛4,18,6,22,10,15｝,请完成：
（1）建立相应的哈夫曼树；
（2）计算其WPL值。

4、如下所示的有向图，回答下面问题：
（1）该图是强连通的吗？若不是，给出强连通分量。

（2）请给出图的邻接矩阵
（3）请给出图的邻接表和逆邻接表。

(4) 计算各点的入度和出度
5、下图是一个带权无向图，要求：
（1）画出以V1为初始顶点、按Prim算法构造最小生成树的过程；
（2）求出最小生成树的总代价；
（3）Prim算法求最小生成树适用于什么情形？
6下图是一个带权无向图，要求：
（1）画出以V1为初始顶点、按克鲁斯卡尔算法构造最小生成树的过程；
（2）求出最小生成树的总代价；
（3）克鲁斯卡尔算法求最小生成树适用于什么情形？
7、设有一组初始记录关键字为(10, 2, 26, 4, 18, 24, 21, 15, 8,)
要求：
（1）构造一棵二叉排序树并给出构造过程。

（2）查找关键字2需要和哪些结点进行比较？
（3）等概率查找下的ASL是多少？
8、已知哈希函数为H(key)=key%11，哈希表长度为13，用平方探测再散列的方法处理冲突。

表中已依次存放了关键字为33、23、32、54和42的5个记录：
（1）现将关键字65填入哈希表，确定其存储地址（要求写出每一步的哈希地址计算表达式）。

（2）若查找关键字65的记录，需依次与哪些关键字进行比较？
（3）为确保查找正确，如果删除关键字为54的记录应作何处理？
9关键码集为{47，7，29，11，16，92，22，8，3}，散列表表长为m=11，散列函数为H(key)=key mod 11 ，线性探测法处理冲突。

（1）生成哈希表
（2）计算查找成功的ASL
（3）计算查找不成功的ASL
10、对关键字序列{49,38,65,97,76,13,27,49----，55,04 }进行快速排序（希尔排序）。

（1）请写出一趟快速排序结果。

（2）快速排序在什么情况下性能最好？什么情况下性能最差？
（3）快速排序是否稳定？并说明理由。

11、对关键字序列{49,38,65,97,76,13,27,49----，55,04 }进行希尔排序。

（1）请写出一趟快速排序结果。

（2）快速排序在什么情况下性能最好？什么情况下性能最差？
（3）快速排序是否稳定？并说明理由。