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

七、设带表头结点的双向链表的定义为
　　typedef int ElemType；

　　typedef struct dnode { file://双向链表结点定义

　　ElemType data； file://数据

　　struct dnode * lLink， * rLink； file://结点前驱与后继指针

　　DblNode；

　　typedef DblNode * DblList； file://双向链表

　　试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的右链域rLink中，并利用左链域lLink把所有结点按照其值从小到大的顺序连接起来。

　　八、设有一个关键码的输入序列{ 55， 31， 11， 37， 46， 73， 63， 02， 07 ，

　　（1）从空树开始构造平衡二叉搜索树，画出每加入一个新结点时二叉树的形态。若发生不平衡，指明需做的平衡旋转的类型及平衡旋转的结果。

　　（2）计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度和查找不成功的平均查找长度。

　　九、下面是求连通网络的最小生成树的Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。

　　const int MaxInt = INT_MAX； file://INT_MAX的值在中

　　const int n = 6； file://图的顶点数，应由用户定义

　　typedef int AdjMatrix[n>[n>； file://用二维数组作为邻接矩阵表示

　　typedef struct file://生成树的边结点

　　int fromVex， toVex； file://边的起点与终点

　　int weight； file://边上的权值

　　TreeEdgeNode；

　　typedef TreeEdgeNode MST[n-1>； file://最小生成树定义

　　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 ；