二、设单链表中结点的结构为 typedef struct node { //链表结点定义 ElemType data. //数据 struct node * Link. //结点后继指针 } ListNode. (1) 已知指针p所指结点不是尾结点,若在*p之后插入结点*s,则应执行下列哪一个操作? A. s->link = p. p->link = s. B. s->link = p->link. p->link = s. C. s->link = p->link. p = s. D. p->link = s. s->link = p. (2) 非空的循环单链表first的尾结点(由p所指向)满足: A. p->link == NULL. B. p == NULL. C. p->link == first. D. p == first.
五、从供选择的答案中选择与下面有关图的叙述中各括号相匹配的词句,将其编号填入相应的括号内。 (1) 对于一个具有n个结点和e条边的无向图,若采用邻接表表示,则顶点表的大小为( A ),所有边链表中边结点的总数为( B )。 (2) 采用邻接表存储的图的深度优先遍历算法类似于树的( C )。 (3) 采用邻接表存储的图的广度优先遍历算法类似于树的( D )。 (4) 判断有向图是否存在回路,除了可以利用拓扑排序方法外,还可以利用( E )。 供选择的答案 A:① n ② n 1 ③ n-1 ④ n e B:① e/2 ② e ③ 2e ④ n e C~D:① 中根遍历 ② 先根遍历 ③ 后根遍历 ④ 按层次遍历 E:① 求关键路径的方法 ② 求最短路径的Dijkstra方法 ③ 深度优先遍历算法 ④ 广度优先遍历算法
九、下面是求连通网络的最小生成树的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 . } }参考答案 一、(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