04年工硕数据结构试题及答案3

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

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

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

　　pre = L； p = L->lLink；

　　file://指针p指向待比较的结点， pre是p的前驱指针

　　while （ p ！= NULL && s->data < p->data ）

　　file://循lLink链寻找结点*s的插入位置

　　{ pre = p； p = p->lLink； }

　　pre->lLink = s； s->lLink = p； s = s->rLink；

　　file://结点*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