参考答案

　　一、（1） 错 （2） 错 （3） 对 （4） 错 （5） 对

　　二、（1） B （2） C

　　三、3

　　四、h = élog2（n+1）ù -1

　　五、A. ① B. ③ C. ② D. ④ E. ③

　　六、① 出 ② 入 ③ 极小 ④ n-1

　　⑤ 是（最小） ⑥ 有 ⑦ 无 ⑧ 14

　　七、算法如下

　　void sort （ DblNode * L ） {

　　DblNode * s = L->rlink；

　　//指针s指向待插入结点， 初始时指向第一个结点

　　while （ s ！= NULL ） { //处理所有结点

　　pre = L； p = L->lLink；

　　//指针p指向待比较的结点， pre是p的前驱指针while （ p ！= NULL && s->data < p->data ）

　　//循lLink链寻找结点 *s的插入位置{ pre = p； p = p->lLink； } pre->lLink = s； s->lLink = p； s = s->rLink；

　　//结点 *s在lLink方向插入到 *pre与 *p之间}

　　八、关键码的输入序列 { 55， 31， 11， 37， 46， 73， 63， 02， 07 }

　　在等概率下查找成功的平均查找长度

　　在等概率下查找不成功的平均查找长度

　　九 ① T[k>.toVex = i

　　② min = MaxInt

　　③ minpos = i

　　④ exit（1）

　　⑤ T.fromVex = v