四种破坏平衡的情况，a,b,c是结点指针，虚线部分是在失去平衡前的图中未画出部分，该部分若存在，则在调整后应按虚线指出的连接。其它，如LL型，a指针所指结点可能有右子树，c指针所指结点可能有左右子树，这些在调整后均不受影响，故没画出。 57．

58．LR型旋转

59．

（1）ASLsuss =（1*1+2*2+3*3+4*3+5*2+6*1）/12=42/12 （2）ASLsuss =（1*1+2*2+4*3+5*4）/12=37/12 （3）ASLsuss =（1*1+2*2+4*3+4*4+5*1）/12=38/12 60．

61．

说明：在（3）后，先删除结点CAN并未破坏平衡，在删AQU后破坏了平衡，根结点CAP的平衡因子为-2。需作何种调整，要看CAP右子树PIS的平衡因子，若该平衡因子是1，则作RL型调整；若为-1，则作RR型调整；若为0，则RR和RL均可，为简单计，选RR型。当然，在PIS平衡因子为零后，还可继续往下分析。

62． 63．（1）

（2）最坏情况下，对该树的插入、删除和依次输出的时间复杂性分别是O(h)，O(nlog2h)和O(n)。

64．按索引顺序查找分块组织数据。N个区间分块有序，区间（块）内无序，将块内最大关键字置于块内最后一个位置，即向量下标为ik-1，其中i=1，2，?，N-1，k为每区间的长度（最后一个区间的最大关键字置于向量最后一个位置）。查找时，若N较小，可用顺序查找，依次将x与r[ik-1]*key进行比较，找到合适块后在块内顺序查找；若N很大，也可用折半查找，以确定x所在块，在块内顺序查找。 65．37/12

66．线性表应顺序存储且数据有序。

67．监视哨的作用是免去查找过程中每次都要检测整个表是否查找完毕，提高了查找效率。

68．表长为n，每块大小取n时，平均查找长度取最小值n+1。若n=255，则每块长度为16。

69．表长2000，分成45块，每块的理想长度为45（最后一块长20）。若每块长25，则平均查找长度为ASL=(80+1)/2+(25+1)/2=53.5（顺序查找确定块），或ASL=19（折半查找确定块）。

70．将n个元素对称比较，即第一个元素与最后一个元素比较，第二个元素与倒数第二个元素比较，??，比较中的小者放前半部，大者放后半部，用了?n/2?次比较。再在前后两部分中分别简单选择最小和最大元素，各用?n/2?-1次比较。总共用了3*?n/2?-2次比较。 71．在有序表A[1..14]中，比较到A[4]时，已查找元素依次是A[7]，A[3]，A[5]。 72．（1）图中结点中的数字为元素在有序表中的下标

1/21/2

（2）插入排序中，用折半查找确定待插入元素位置，比直接插入排序减少了比较次数，但数据移动次数没有改变，排序的时间复杂度也未改变。

（3）折半查找的平均查找长度是((n+1)/n)log2(n+1)-1≈log(n+1)-1。本例ASL=79/21。 73．根据次优查找树的定义，首先取第i个记录（l≤i≤h）构造根结点，使

△Pj=|-| 取最小值。

关键字 black blue green purple red white yellow 权值 0.10 0.08 0.12 0.05 0.20 0.25 0.20 j 1 2 3 4 5 6 7 SWj 0.1 0.18 0.30 0.35 0.55 0.80 1.00 △Pj 0.9 0.72 0.52 0.35 0.10 0.35 0.80 （根） ↑i

△Pj 0.25 0.07 0.13 0.30 0.20 0.25 ↑i ↑i △Pj 0.05 0.12 ↑i

red blue black white white yellow green black blue red green yellow purple

purple

73题（1）次优查找树 73题（2）调整后的次优查找树