习题解答
图8-21 二叉查找树示例
答：1）删除关键字为15的记录后，该树的形态如图(a)或(b)所示，(a)是用待删结点的直接前驱（或左子树根结点）取代所得，而(b)则是用待删结点的直接后继（或右子树根结点）取代所得；（2）插入关键字为20的记录后，该树的形态如图(c)所示。
3．设散列函数为h(key)=key % 11，散列表长为11（索引地址为0~10）。给定： SUN，MON，TUE，WED，THU，FRI，SAT
取单词第1个字母在英语字母表中的序号为关键字值（比如S的关键字值为19），采用链地址法解决散列地址冲突。请画出对应的散列表。 答：对应的散列表如下。
4．有关键字序列：36、27、68、33、97、40、81、24、23、90、32、14，散列表长为13，采用的散列函数为：h(key)=key，使用开放地址法的线性探测解决冲突。请完成下面散列表的填写（比如，第1个插入的是36，它的散列地址为10，由于没有发生冲突，所以比较一次就存放在了地址为10的位置），求出其平均查找长度ASL。
- 36 -
习题解答
答：最终的散列表如图所示。其平均查找长度ASL为： ASL（线性探测）=（2+1+2+1+2+5+1+1+3+1+1+3）/12=1.92
5．已知由12个关键字组成的序列： Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec
（1）按照所给顺序构造一棵初始为空的二叉查找树，画出最终形成的二叉查找树，求在等概率下查找成功的平均查找长度。
（2）若对关键字序列按照字母递增的顺序排列成有序表，求在等概率下这棵二叉查找树查找成功的平均查找长度。 答：（1）最终形成的二叉查找树如下图所示，其平均查找长度为： ASL=（1+2*2+3*3+3*4+2*5+6）/12=42/12=3.5
- 37 -
习题解答
（2）这时成为只有右子树的单支树，其平均查找长度为： ASL=（1+2+3+4+5+6+7+8+9+10+11+12）/12=78/12=6.5 6．已知由12个关键字组成的序列： Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec 散列表长为13（地址为0~12），散列函数为：h(key)=i/2，其中i为关键字中第1个字母在字母表里的序号。 （1）用线性探测法解决冲突，给出所构造的散列表以及查找成功的平均查找长度。 （2）用链地址法解决冲突，给出所构造的散列表以及查找成功的平均查找长度。
答：（1）用线性探测法解决冲突时，插入地址及比较次数如下：
h(Jan)=10/2=5，比较1次插入；h(Feb)=6/2=3，比较1次插入；
h(Mar)=13/2=6，比较1次插入；h(Apr)=1/2=3，比较1次插入； h(May)=13/2=6，比较2次插入；h(Jun)=10/2=5，比较4次插入； h(Jul)=10/2=5，比较5次插入；h(Aug)=1/2=0，比较2次插入； h(Sep)=19/2=9，比较2次插入；h(Oct)=15/2=7，比较5次插入； h(Nov)=14/2=7，比较6次插入；h(Dec)=4/2=2，比较1次插入。 所以，构造的散列表如图所示。
平均查找长度为： ASL=（1+1+1+1+2+4+5+2+2+5+6+1）/12=31/12≈2.6 （2）用链地址法解决冲突时，构造的散列表如图所示。
平均查找长度为： ASL=（1+2+1+1+1+2+3+1+2+1+2+1）/12=18/12=1.5
第9章习题解答
一、填空
1．一次筛选的目的，就是将不满足堆性质的完全二叉树 根 结点，调整到其适当的位置上，以便构成一个新堆。 2．若经过某种排序之后，那些有相同关键字值的记录间的相对位置保持不变，那么称这种排序方法是 稳定 的。 3．有待排关键字序列：54、38、96、23、18、73、61、46、88，采用直接插入排序算
- 38 -
习题解答
法。在进行到寻找第7个关键字61的插入位置时，需要做 3 次比较。
（注意：在进行到寻找第7个关键字61的插入位置时，前面的6个关键字已经排好了序：18、23、38、54、73、96。由于比较是从后往前进行的，所以在与96、73、54比较后，就能够确定60的插入位置了） 4． 选择 排序方法是从未排序的序列中挑选出元素，然后将其依次放入排好序的序列的一端。 5． 快速 排序方法是通过适当的位置交换，把序列中的元素一次性地放到了它的最终位置上。 6．有待排序的关键字序列：54、38、96、23、15、72、60、45、83，对这样的一个特定的序列进行冒泡排序。整个排序过程需进行 5 趟扫描，才能完成排序任务。 （注意：第4趟已经排好，第5趟时由于判断没有交换而结束排序） 7．对关键字序列22、86、19、49、12、30、65、35、18做一趟排序后，得到的结果是18、12、19、22、49、30、65、35、86。因此，可以认为采用的排序方法是 快速排序 。 8．一个堆中所有非叶结点的关键字值都 小于或等于 其左、右孩子的关键字值。
二、选择 1．在下面给出的各种排序算法中，只有 A 是稳定排序算法。 A．冒泡排序 B．快速排序 C．直接选择排序 D．堆排序 2．在下面给出的各种排序算法中，只有 B 不是稳定排序算法。 A．冒泡排序 B．快速排序 C．直接插入排序 D．折半插入排序 3．在给出的四棵二叉树中，只有 C 满足一个堆的条件。
4．已知无序的待排关键字序列为：46、79、56、38、40、84。利用堆排序方法创建的初始堆应该是 B A．38，56，40，79，46，84 B．38，40，56，79，46，84
C．38，40，46，56，79，84 D．38，46，40，56，79，84
5．对关键字序列：46、79、56、38、40、84采用快速排序方法。若以46为枢轴，那么一次划分后的结果应该是 D 。 A．38，40，46，79，56，84 B．38，40，46，84，56，79
C．40，38，46，79，84，56 D．40，38，46，56，79，84
6．从待排序序列中依次取出元素与已排好序的序列里的元素进行比较，并存放到已排序序列的正确位置上，这种排序方法是 A 。 A．直接插入排序 B．交换排序 C．冒泡排序 D．选择排序 7．当两个元素出现逆序时就交换它们的位置，这种排序方法是 C 。 A．直接插入排序 B．冒泡排序 C．交换排序 D．选择排序 8．具有24个记录的待排序列，采用冒泡排序时，最少需要进行的比较次数是 B 。 A．1 B．23 C．24 D．512 9．用某种排序方法对序列：24、84、21、47、16、28、66、35、20进行排序，序列的变化情况为： 24，84，21，47，16，28，66，35，20
- 39 -
习题解答
20，16，21，24，47，28，66，35，84 16，20，21，24，35，28，47，66，84 16，20，21，24，28，35，47，66，84 那么，这里采用的排序方法是 C 。 A．直接插入排序 B．冒泡排序 C．快速排序 D．选择排序
三、问答
1．在直接插入排序算法中，什么条件保证了该算法的稳定性？ 答：在该算法中，可能停止while循环的一个条件是“temp.key>=Ar[j].key”，正是它保证了直接插入排序算法的稳定性。比如在例9-2里，由于比较到第2个76大于、等于第1个76，所以while循环就结束了，不再往后移动比较范围内的记录。因此，第2个76肯定在第1个76的后面，不会跑到它的前面去。如果将while循环改为： while ((temp.key>=Ar[j].key) && (j>=1)) 那么，它就不会保证直接插入排序算法是稳定的了。 2．在冒泡排序算法里，是什么条件保证它的稳定性？ 答：冒泡排序是一种稳定排序算法，主要是因为算法里每趟扫描时的判定条件设定为： Ar[j].key>Ar[j+1].key，它保证了原先在前面的记录，排序后仍然排在前面，不会改变它们之间的相对顺序。如果把大于号改为大于等于，那么算法就不是稳定的了。 3．试问内排序与外排序有什么区别？ 答：内、外排序虽然都是排序，但由于排序过程中所使用存储器的不同，而被分为内排序和外排序。所谓“内排序”，是指待排记录序列全部存放在内存，整个排序过程都在内存里完成；所谓“外排序”，是指内存中容纳不下所有待排记录序列，排序过程中需要不断地与外存进行数据交换。 4．有两个关键字序列：3、10、12、22、36、18、28、40和5、8、11、15、23、20、32、7。试问谁是堆，谁不是堆？把不是堆的序列通过筛选将它调整为一个堆。 答：依照序列的顺序，画出对应的完全二叉树如(a)和(b)所示。可以看出，(a)是一个堆，(b)则不是，因为结点7破坏了堆的性质。为此，先将7和15对换，如图(c)所示；然后再将7和8对换，如图(d)所示。这时，序列2就被调整为是一个堆了。
5．有以下四个待排关键字序列： 19，23，3，15，7，21，28 23，21，28，15，19，3，7 19，7，15，28，23，21，3 3，7，15，19，21，23，28 对它们采用快速排序方法进行排序，试问哪一种情况速度最慢？ 答：在最后一种情况时，序列已经排好序，因此对它的排序速度最慢。
四、应用
1．将冒泡排序算法修改成记录关键字由大到小递减排列。 答：已知有n个记录的无序序列，存放在一个一维数组Ar里。对它进行递减的冒泡排序，并最后得到排序结果。算法名为Bub_Sort1()，参数为Ar，n。
- 40 -