数据结构第七章考试题库(含答案)(8)

21．（1）

（2）AFEDBC

22．设邻接表（略）中顶点的邻接点按顶点编号升序排列（V1编号为1）

（1） 广度优先搜索序列：V1V2V3V4V5V6V7V8 （2） 深度优先搜索序列：V1V2V4V8V5V3V6V7

23．（1）略 （2）V1V2V5V3V4V6 (4) V1V2V3V4V5V6

(5)

(3)

(6）见本章五算法设计第6题

24．设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列

(1)ABGFDEC (2)EACFBDG

(3)

25．在有相同权值边时生成不同的MST，在这种情况下，用Prim或Kruskal也会生成不同的MST。

26．无向连通图的生成树包含图中全部n个顶点，以及足以使图连通的n-1条边。而最小生成树则是各边权值之和最小的生成树。从算法中WHILE（所剩边数>=顶点数）来看，循环到边数比顶点数少1（即n-1）停止，这符合n个顶点的连通图的生成树有n-1条边的定义；由于边是按权值从大到小排序，删去的边是权值大的边，结果的生成树必是最小生成树；算法中“若图不再连通，则恢复ei”，含义是必须保留使图连通的边，这就保证了是生成树，否则或者是有回路，或者成了连通分量，均不再是生成树。

27．Prim算法构造最小生成树的步骤如24题所示，为节省篇

幅，这里仅用Kruskal算法，构造最小生成树过程如下：（下图也可选(2,4)代替(3,4),(5,6)代替(1,5)）

28．（1）最小生成树的定义见上面26题

（2）最小生成树有两棵。

（限于篇幅，下面的生成树只给出顶点集合和边集合，边以三元组（Vi,Vj,W）形式），其中W代表权值。

V（G）={1，2，3，4，5} E1(G)={(4，5，2)，（2，5，4），（2，3，5），（1，2，7）}；

E2(G)={(4，5，2），（2，4，4），（2，3，5），

（1，2，7）}

29．V（G）={1，2，3，4，5，6，7}

E（G）={（1，6，4），（1，7，6），（2，3，5），（2，4，8），（2，5，12），（1，2，18）}

30．V（G）={1，2，3，4，5，6，7，8}

E（G）={（3，8，2），（4，7，2），（3，4，3），（5，8，3），

（2，5，4），（6，7，4），（1，2，5）}

注：（或将（3，4，3）换成（7，8，3））

31．设顶点集合为{1，2，3，4，5，6}，

由右边的逻辑图可以看出，在{1，2，3}和{4，5，6}回路中， 各任选两条边，加上（2，4），则可构成9棵不同的最小生成树。 32．（1）邻接矩阵略

（2） Y Closedge Vex Lowcost Vex Lowcost 2 ① 2 3 ① 3 ① 3 4 ② 5 6 7 8 U {1} V-U {2,3,4,5,6,7,8}

五.算法设计题

1. void CreatGraph (AdjList g)

//建立有n个顶点和m 条边的无向图的邻接表存储结构 {int n,m;

scanf(\

for (i =1,i<=n;i++)//输入顶点信息,建立顶点向量 {scanf(&g[i].vertex); g[i].firstarc=null;} for (k=1;k<=m;k++)//输入边信息 {scanf(&v1,&v2);//输入两个顶点

i=GraphLocateVertex (g,v1); j=GraphLocateVertex (g,v2); //顶点定位 p=(ArcNode *)malloc(sizeof(ArcNode));//申请边结点

p->adjvex=j; p->next=g[i].firstarc; g[i].firstarc=p;//将边结点链入 p=(ArcNode *)malloc(sizeof(ArcNode));

p->adjvex=i; p->next=g[j].firstarc; g[j].frstarc=p; }

}//算法CreatGraph结束

2. void CreatAdjList(AdjList g)

//建立有向图的邻接表存储结构 {int n;

scanf(\ for (i=1;i<=n;j++)

{scanf(&g[i].vertex); g[i].firstarc=null;}//输入顶点信息 scanf(&v1,.&v2);

while(v1 && v2)//题目要求两顶点之一为0表示结束 {i=GraphLocateVertex(g2,v1);

p=(ArcNode*)malloc(sizeof(ArcNode));

p->adjvex=j; p->next=g[i].firstarc; g[i].firstarc=p;

scanf(&v1,&v2); } }

3. void CreatMGraph(AdjMulist g)

//建立有n个顶点e条边的无向图的邻接多重表的存储结构 {int n,e;

scanf(\

for(i=1,i<=n;i++) //建立顶点向量

{ scanf(&g[i].vertex); g[i].firstedge=null;} for(k=1;k<=e;k++) //建立边结点 {scanf(&v1,&v2);

i=GraphLocateVertex(g,v1); j=GraphLocateVertex(g,v2);

p=(ENode *)malloc(sizeof(ENode)); p->ivex=i; p->jvex=j; p->ilink=g[i].firstedge; p->jlink=g[j].firstedge;

g[i].firstedge=p; g[j].firstedge=p; }

}//算法结束

4. void CreatOrthList(OrthList g)

//建立有向图的十字链表存储结构 {int i,j,v; //假定权值为整型 scanf(\

for(i=1,i<=n;i++) //建立顶点向量

{ scanf(&g[i].vertex); g[i].firstin=null; g[i].firstout=null;} scanf(\

while (i && j && v) //当输入i,j,v之一为0时,结束算法运行 {p=(OrArcNode *)malloc(sizeof(OrArcNode)); //申请结点

p->headvex=j; p->tailvex=i; p->weight=v; //弧结点中权值域 p->headlink=g[j].firstin; g[j].firstin=p; p->tailink=g[i].firstout; g[i].firstout=p;

scanf(\

} }算法结束

[算法讨论] 本题已假定输入的i和j是顶点号,否则,顶点的信息要输入,且用顶点定位函数求出顶点在顶点向量中的下标。图建立时，若已知边数（如上面1和2题），可以用for循环；若不知边数，可用while循环（如本题），规定输入特殊数（如本题的零值）时结束运行。本题中数值设为整型，否则应以和数值类型相容的方式输入。 5．void InvertAdjList(AdjList gin,gout）

//将有向图的出度邻接表改为按入度建立的逆邻接表

{for (i=1;i<=n;i++)//设有向图有n个顶点，建逆邻接表的顶点向量。 {gin[i].vertex=gout[i].vertex; gin.firstarc=null; } for (i=1;i<=n;i++) //邻接表转为逆邻接表。 {p=gout[i].firstarc;//取指向邻接表的指针。 while (p!=null) { j=p->adjvex;

s=(ArcNode *)malloc(sizeof(ArcNode));//申请结点空间。 s->adjvex=i; s->next=gin[j].firstarc; gin[j].firstarc=s; p=p->next;//下一个邻接点。 }//while }//for }

6. void AdjListToAdjMatrix(AdjList gl, AdjMatrix gm)

//将图的邻接表表示转换为邻接矩阵表示。

{for (i=1;i<=n;i++) //设图有n个顶点，邻接矩阵初始化。 for (j=1;j<=n;j++) gm[i][j]=0; for (i=1;i<=n;i++)

{p=gl[i].firstarc; //取第一个邻接点。

while (p!=null) {gm[i][p->adjvex]=1;p=p->next; }//下一个邻接点 }//for }//算法结束

7. void AdjMatrixToAdjList( AdjMatrix gm, AdjList gl )

//将图的邻接矩阵表示法转换为邻接表表示法。 {for (i=1;i<=n;i++) //邻接表表头向量初始化。 {scanf(&gl[i].vertex); gl[i].firstarc=null;} for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (gm[i][j]==1)

{p=(ArcNode *)malloc(sizeof(ArcNode)) ;//申请结点空间。

p->adjvex=j;//顶点I的邻接点是j

p->next=gl[i].firstarc; gl[i].firstarc=p; //链入顶点i的邻接点链

表中

}

}//end

[算法讨论] 算法中邻接表中顶点在向量表中的下标与其在邻接矩阵中的行号相同。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构第七章考试题库(含答案)(8)在线全文阅读。