1、除第九题外，其他各题每题10分，第九题20分。

　　2、所有试题的答案写在答题纸上。

　　一、判断下列叙述的对错。

　　（1） 线性表的逻辑顺序与物理顺序总是一致的。

　　（2） 线性表的顺序存储表示优于链式存储表示。

　　（3） 线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。

　　（4） 二维数组是其数组元素为线性表的线性表。

　　（5） 每种数据结构都应具备三种基本运算：插入、删除和搜索。

　　T[k>.toVex = I ；

　　T[k++>.weight = G[rt>；

　　} for （ k = 0； k < n-1； k++ ） { //依次求MST的候选边min = MaxInt ；

　　for （ i = k； i < n-1； i++ ） //遍历当前候选边集合if （ T.weight < min ） //选具有最小权值的候选边{ min = T.weight； minpos = i ； } if （ min == MaxInt ） //图不连通， 出错处理{ cerr 《 “Graph is disconnected！” 《 endl； exit（1） ； } e = T[minpos>； T[minpos> = T[k> ； T[k> = e；

　　v = T[k>.toVex；

　　for （ i = k+1； i < n-1； i++ ） //修改候选边集合if （ G[v>[T.toVex> < T.weight ） { T.weight = G[v>[T.toVex>；

　　T.fromVex = v ；

　　} }参考答案

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