严蔚敏-数据结构集合习题 下载本文

四种破坏平衡的情况,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)调整后的次优查找树