參考答案
一、（1）錯（2）錯（3）對（4）錯（5）對
二、（1） B （2） C
三、3
四、h =élog2（n+1）ù-1
五、A.①B.③C.②D.④E.③
六、①出②入③極?、躰-1
⑤是（最小）⑥有⑦無⑧14
七、算法如下
void sort （ DblNode * L ） {
DblNode * s = L->rlink；
file://指針s指向待插入結(jié)點，初始時指向第一個結(jié)點
while （ s ！= NULL ） { file://處理所有結(jié)點
pre = L； p = L->lLink；
file://指針p指向待比較的結(jié)點， pre是p的前驅(qū)指針
while （ p ！= NULL && s->data < p->data ）
file://循lLink鏈尋找結(jié)點*s的插入位置
{ pre = p； p = p->lLink； }
pre->lLink = s； s->lLink = p； s = s->rLink；
file://結(jié)點*s在lLink方向插入到*pre與*p之間
}
八、關(guān)鍵碼的輸入序列{ 55， 31， 11， 37， 46， 73， 63， 02， 07 }
在等概率下查找成功的平均查找長度
在等概率下查找不成功的平均查找長度
九
①T[k>.toVex = i
②min = MaxInt
③minpos = i
④exit（1）
⑤T.fromVex = v