参考答案

    一、(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