数据结构讨论小课堂和习题解答(8)

1 3 4 图7.25 2 1 5 7 9 6 2 8 3 6 4 4 4 图7.26 2 5

答：（1）假设指定从v1出发，用普里姆方法画出最小生成树的过程：

（2）用克鲁斯卡尔方法画出最小生成树的过程：

10. 修改PRIM算法，使之能在邻接链表存储结构上实现求图的最小生成树，并

分析其时间复杂度。 答;

#define MAX 100

typedef struct ArcNode {

int adjvex; /*该弧所指向的顶点的位置 */ struct ArcNode *nextarc; /*指向下一条弧的指针 */

int info; /*该弧相关信息的指针 */ }ArcNode;

typedef struct VNode {

char data; /*顶点信息 */

ArcNode *firstarc; /*指向第一条依附该顶点的弧的指针 */ }VNode,AdjList[MAX];

typedef struct{ AdjList vertices;

int vexnum,arcnum; /*图的当前顶点数和弧数 */ }ALGraph;

void Prim(ALGraph G,int k,CSTree &T)

/*从顶点k出发,构造邻接表结构的有向图G的最小生成森林T,用孩子兄弟链表存储*/ {

for(j=0;j

closedge[j]={k,Max_int};

for(p=G.vertices[j].firstarc;p;p=p->nextarc) if(p->adjvex==k) closedge[j].lowcost=p->cost; }/*if*/

closedge[k].lowcost=0; for(i=1;i

k=minimum(closedge);

if(closedge[k].lowcost

Addto_Forest(T,closedge[k].adjvex,k); /*把这条边加入生成森林中*/ closedge[k].lowcost=0;

for(p=G.vertices[k].firstarc;p;p=p->nextarc) if(p->costadjvex].lowcost)

closedge[p->adjvex]={k,p->cost}; }//if

else Forest_Prim(G,k); /*对另外一个连通分量执行算法*/ }/*for*/

}/*Forest_Prim */

void Addto_Forest(CSTree &T,int i,int j)/*把边(i,j)添加到孩子兄弟链表表示的树T中*/ {

p=Locate(T,i); /*找到结点i对应的指针p,过程略*/ q=(CSTNode*)malloc(sizeof(CSTNode)); q->data=j;

if(!p) /*起始顶点不属于森林中已有的任何一棵树*/ {

p=(CSTNode*)malloc(sizeof(CSTNode)); p->data=i;

for(r=T;r->nextsib;r=r->nextsib); r->nextsib=p; p->firstchild=q;

} /*作为新树插入到最右侧*/

else if(!p->firstchild) /*双亲还没有孩子*/ p->firstchild=q; /*作为双亲的第一个孩子*/ else /*双亲已经有了孩子*/ {

for(r=p->firstchild;r->nextsib;r=r->nextsib);

r->nextsib=q; /*作为双亲最后一个孩子的兄弟*/ }

}/*Addto_Forest */

main()

{ ...

T=(CSTNode*)malloc(sizeof(CSTNode)); /*建立树根*/ T->data=1;

Forest_Prim(G,1,T); ...

}/*main*/

分析:这个算法是在Prim算法的基础上添加了非连通图支持和孩子兄弟链表构建

模块而得到的,其时间复杂度为O(n^2).

11. 求出图7.27从顶点v1到其它各顶点之间的最短路径。绘制图表解题。 答:

dist path dist path dist path V2 20 V1 20 V1 20 V1 V3 5 V1 V4 ∞ V1 ∞ V1 19 V6 V5 ∞ V1 ∞ V1 25 V6 V6 ∞ V1 15 v3 S V1 V1,v3 V1,v3, v6 V-S V2, v3,v4, v5, v6 V2, v4,v5, v6 v2, v4, v5 v2, v5 v5 shortpath v3 V6 v4 v2 v5 dist 20 25 V1,v3, v6,v4 path V1 V6 dist 25 V1,v3, path V6 v6,v4,v2 dist V1,v3, path v6,v4,v2, v5

12. 写出图7.28的三种可能的拓朴排序结果。 答:

5,2,1,3,4,6,7,8 5,2,4,3,1,7,6,8 7,5,2,1,3,4,6,8

5 10 4 6 5 4 30 10 图7.27 10 2 2 4 3 20 1 5 5 4 图7.28 1 2 3 8 7 6

讨论小课堂8

[参考内容]

1．若二叉排序树中的一个结点存在两个孩子，那么它的中序后继结点是否有左孩子？它的中序前驱结点是否有右孩子？

【参考答案】：若p是给定的二叉排序树中的某个结点，且p有左、右孩子。按照中序遍历的思想，先中序遍历p的左子树，再访问根结点p，最后遍历p的右子树。左子树最后访问的结点x为p的前驱结点，x一定没有右子树，

否者x不是左子树上中序遍历中最后访问的结点。因而，p的前驱结点x没有右孩子。同理，p的中序后继结点x没有左孩子。

2．若将关键字1，2，3，┅，2k-1依次插入到一棵初始为空的AVL中，能证明结果树是完全平衡的吗？

【参考答案】：所谓“完全平衡”是指所有叶子结点处于树的同一层次上，并在该层是满的。

第一步，当k=1时，21-1=1，AVL树只有一个结点，它既是根又是叶子并处在第0层，根据二叉树性质，应具有20=1个结点。因此，满足完全平衡要求。 第二步，设k=n，插入关键码1，2，3，┅，2n-1到AVL树中，恰好每一层(层次号码是i=0，1，2，3，┅，n-1)有2i个结点，根据二叉树性质，每一层达到最多结点个数，满足完全平衡要求。则当k=n+1时，插入关键码为1，2，3，┅，2n-1，2n，┅，2n+1-1，总共增加了从2n到2n+1-1的2n+1-1-2n+1=2n个关键码，使得AVL树在新增的第n层具有2n个结点，达到该层最多结点个数，因此，满足完全平衡要求。

由上可的，能证明它是完全平衡的。

3．假设有关键码A、B、C和D，按照不同的输入顺序，共可能组成多少不同的二叉排序树？AVL树有几种？完全二叉树有几种？请画出其中高度较小的6种。

【参考答案】：本题的含义是：给定中序序列1，2，3，4，有几种不同的二叉排序树，这是树的计数问题。设中序遍历序列中元素数为n，则二叉树的数目为1(n?1)n?C2n，这里n=4，故有14种。

AVL树有4种。 完全二叉树有1种。

6种高度较小的二叉排序树如下所示。

A B B C A C A D B D D C C B D A D B A B A C D C

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构讨论小课堂和习题解答(8)在线全文阅读。