六、填空题

　　（1） 在用于表示有向图的邻接矩阵中， 对第i行的元素进行累加， 可得到第i 个顶点的（ ① ）度， 而对第j列的元素进行累加， 可得到第j个顶点的（ ② ）度。

　　（2） 一个连通图的生成树是该图的（ ③ ）连通子图。若这个连通图有n个顶点， 则它的生成树有（ ④ ）条边。

　　（3） 给定序列{100， 86， 48， 73， 35， 39， 42， 57， 66， 21}， 按堆结构的定义， 则它一定（ ⑤ ）堆。

　　（4） 在进行直接插入排序时， 其数据比较次数与数据的初始排列（ ⑥ ）关；而在进行直接选择排序时，其数据比较次数与数据的初始排列（ ⑦ ）关。

　　（5） 利用关键码分别为10， 20， 30， 40的四个结点，能构造出（ ⑧ ）种不同的二叉搜索树。

　　七、设带表头结点的双向链表的定义为

　　typedef int ElemType；

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

　　ElemType data； //数据

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

　　DblNode；

　　typedef DblNode * DblList； //双向链表

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

　　八、设有一个关键码的输入序列 { 55， 31， 11， 37， 46， 73， 63， 02， 07 ，（1） 从空树开始构造平衡二叉搜索树， 画出每加入一个新结点时二叉树的形态。若发生不平衡， 指明需做的平衡旋转的类型及平衡旋转的结果。

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

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

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

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

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

　　typedef struct //生成树的边结点

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

　　int weight； //边上的权值

　　TreeEdgeNode；

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

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

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

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

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

　　if （ i ！= rt ） {

　　T[k>.fromVex = rt；

　　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 ；