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

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

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

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

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

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

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

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

　　void PrimMST （ AdjMatrix G， MST T， int rt ） {

　　file://从顶点rt出发构造图G的最小生成树T，rt成为树的根结点

　　TreeEdgeNode e； int i， k = 0， min， minpos， v；

　　for （ i = 0； i < n； i++ ） file://初始化最小生成树T

　　if （ i ！= rt ） {

　　T[k>.fromVex = rt；

　　T[k>.toVex = I ；

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

　　}

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

　　min = MaxInt ；

　　for （ i = k； i < n-1； i++ ） file://遍历当前候选边集合

　　if （ T.weight < min ） file://选具有最小权值的候选边

　　{ min = T.weight； minpos = i ； }

　　if （ min == MaxInt ） file://图不连通，出错处理

　　{ 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++ ） file://修改候选边集合

　　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；

　　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