所以，平均查找长度ASL＝1×0.1＋2×0.2＋3×0.4＋4×0.3＝2.9
【27， 9，2】（选自《数据结构题集》9.10，选做题）
可以生成如下二叉排序树的关键字的初始排列有几种？请写出其中的任意5个。
解：30种。任写5个序列如下： （5，4，7，6，2，3，1）； （5，7，4，6，2，3，1）； （5，4，7，2，3，1，6）； （5，7，6，4，2，3，1）； （5，7，6，4，2，1，3）
【28， 5，1】（选自《数据结构题集》9.21，选做题） 在地址空间为0～16的散列区中，对以下关键字序列构造两个哈希表：（Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec） （1）用线性探测开放定址法处理冲突； （2）用链地址法处理。
并分别求这两个哈希表在等概率情况下查找成功和不成功时的平均查找长度。 设哈希函数为H（x）＝「i/2」，其中i为关键字第一个字母在字母表中的序号。 解：（1）用线性探测开放定址法处理冲突
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Apr Aug Dec Feb Jan Mar May June July Sep Oct Nov ASLsucc＝（1×5＋2×3＋4＋5×2＋6）/12=31/12 ASLunsucc＝(5×6/2+9×10/2)/14 = 60/14 （2）用链地址法处理
ASLsucc＝（1×7＋2×4＋3）/ 14 = 18 / 12
ASLunsucc＝（1×7＋2×3＋3×3＋4）/ 14 = 26 / 14
【29， 10，4】（选自《数据结构题集》10.1，必做题）
以关键码序列（503，087，512，061，908，170，897，275，653，426）为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态： （1）直接插入排序；（3）快速排序；（4）堆排序 答：（1）直接插入排序 （503），087，512，061，908，170，897，275，653，426 （087，053），512，061，908，170，897，275，653，426 （087，503，512），061，908，170，897，275，653，426 （061，087，503，512），908，170，897，275，653，426 （061，087，503，512，908），170，897，275，653，426 （061，087，170，503，512，908），897，275，653，426 （061，087，170，503，512，897，908），275，653，426 （061，087，170，275，503，512，897，908），653，426 （061，087，170，275，503，512，653，897，908），426 （061，087，170，275，426，503，512，653，897，908） （3）快速排序
初 始：503，087，512，061，908，170，897，275，653，426 第一趟：426，087，275，061，170，503，897，908，653，512 第二趟：170，087，275，061，426，503，512，653，897，908 第三趟：061，087，170，275，426，503，512，653，897，908 第四趟：061，087，170，275，426，503，512，653，897，908 第五趟：061，087，170，275，426，503，512，653，897，908 （4）堆排序 初 始：（503，087，512，061，908，170，897，275，653，426） 初始堆：（908，653，897，503，426，170，512， 275，061，087） 第一趟：（897，653，512，503，426，170，087， 275，061），908 第二趟：（653，503，512，275，426，170，087， 061），897，908 第三趟：（512，503，170，275，426，061，087），653，897，908 第四趟：（503，426，170，275，087，061），512，653，897，908 第五趟：（426，275，170，061，087），503，512，653，897，908 第六趟：（275，087，170，061），426，503，512，653，897，908 第七趟：（170，087，061），275，426，503，512，653，897，908 第八趟：（087，061），170，275，426，503，512，653，897，908 第九趟：（061），087，170，275，426，503，512，653，897，908
【30， 10，4】（选自《数据结构题集》10.12，必做题） 判别以下序列是否为堆（小顶堆或大顶堆）。如果不是则把它调整为堆。（要求记录交换次数最少）
（1）（100，86，48，73，35，39，42，57，66，21）； （2）（12，70，33，65，24，56，48，92，86，33）； （3）（103，97，56，38，66，23，42，12，30，52，06，20）； （4）（05，56，20，23，40，38，29，61，35，76，28，100）。
解：（1）大顶堆；
（2）否。调整为小顶堆如下：
（12，24，33，65，33，56，48，92，86，70）
（3）大顶堆；
（4）否。调整为小顶堆如下：
（05，23，20，35，28，38，29，61，56，76，40，100）