参考答案 
一、(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