23湖南大学计算机考研图相关例题解析(湖南大学信息与计算科学)

2024-01-13 15:49:03 考研全程辅导 12

[摘要]

点击上方蓝字关注我们！晚风学长：（1）初试总分排名前五成绩考入湖大信息科学与工程学院。（2）有着丰富的辅导经验，在校期间辅导过考本院的学生，所带8名学生全部进入复试，最终7人被本院录取，1人选择调剂外校，所带专业学生成绩...

点击上方蓝字关注我们！

晚风学长：

（1）初试总分排名前五成绩考入湖大信息科学与工程学院。（2）有着丰富的辅导经验，在校期间辅导过考本院的学生，所带8名学生全部进入复试，最终7人被本院录取，1人选择调剂外校，所带专业学生成绩均超过120。（3）了解学院的考研动态和招生情况，熟悉考试大纲，在校期间精心研究历年真题，熟悉湖大出题风格，对湖南大学数据结构专业课出题风格与考点预测有独到见解。

童鞋们好，我是你们的晚风学长，本期是我们今年第四次公众号知识分享！上期主要为大家分享了树及二叉树的知识，下面我将为大家带来最近课程知识点的部分复习。

如果大家目前专业课学习有任何问题，欢迎大家扫描文末二维码进群跟我们一起讨论交流，我也会在群里给大家定期直播答疑哦！加入我们课程的同学也可以私聊我咨询考研相关问题。当然文章中只能分享部分内容，如果大家想跟着我一起做题冲刺专业课高分，可以参考文末课程安排咨询我们，现在冲刺名额有限，期待大家加入我们的课程，一起拼搏冲湖大！

本期重要例题：

1. 图g是一个非连通图，共有28条边，则该图至少有多少个顶点？

答：由于g是一个非连通图，在边数固定时，顶点数最少的情况是该图由两个连通分量构成，且其中之一只含一个顶点（没有边），另一个为完全无向图。设该完全无向图的顶点数为n，其边数为n(n-1)/2，即n(n-1)/2=28，得n=8。所以，这样的非连通图至少有1+8=9个顶点。

2. 有一个如图所示的有向图，给出其所有的强连通分量。

答：图中顶点0、1、2构成一个环，这个环一定是某个强连通分量的一部分。再考察顶点3、4，它们到这个环中的顶点都有双向路径，所以将顶点3、4加入。考察顶点5、6，它们各自构成一个强连通分量。该有向图的强连通分量有3个，如图所示。

3. 对于稠密图和稀疏图，采用邻接矩阵和邻接表哪个更好些？

答：邻接矩阵适合于稠密图，因为邻接矩阵占用的存储空间与边数无关。邻接表适合于稀疏图，因为邻接表占用的存储空间与边数有关。

4. 对n个顶点的无向图和有向图（均为不带权图），采用邻接矩阵和邻接表表示时，如何求解以下问题：

（1）图中有多少条边？

（2）任意两个顶点i和j是否有边相连？

（3）任意一个顶点的度是多少？

答：（1）对于邻接矩阵表示的无向图，图的边数等于邻接矩阵数组中为1的元素个数除以2；对于邻接表表示的无向图，图中的边数等于边结点的个数除以2。
对于邻接矩阵表示的有向图，图中的边数等于邻接矩阵数组中为1的元素个数；对于邻接表表示的有向图，图中的边数等于边结点的个数。
（2）对于邻接矩阵g表示的无向图，邻接矩阵数组元素g.edges[i][j]为1表示它们有边相连，否则为无边相连。对于邻接矩阵g表示的有向图，邻接矩阵数组元素g.edges[i][j]为1表示从顶点i到顶点j有边，g.edges[j][i]为1表示从顶点j到顶点i有边。对于邻接表g表示的无向图，若从头结点g->adjlist[i]的单链表中找到编号为j的边表结点，表示它们有边相连；否则为无边相连。对于邻接表g表示的有向图，若从头结点g->adjlist[i]的单链表中找到编号为j的边表结点，表示从顶点i到顶点j有边。若从头结点g->adjlist[j]的单链表中找到编号为i的边表结点，表示从顶点j到顶点i有边。
（3）对于邻接矩阵表示的无向图，顶点i的度等于第i行中元素为1的个数；对于邻接矩阵表示的有向图，顶点i的出度等于第i行中元素为1的个数，入度等于第i列中元素为1的个数，顶点i度等于它们之和。对于邻接表g表示的无向图，顶点i的度等于g->adjlist[i]为头结点的单链表中边表结点个数。对于邻接表g表示的有向图，顶点i的出度等于g->adjlist[i]为头结点的单链表中边表结点的个数；入度需要遍历所有的边结点，若g->adjlist[j]为头结点的单链表中存在编号为i的边结点，则顶点i的入度增1，顶点i的度等于入度和出度之和。

5.对于如图所示的一个无向图g，给出以顶点0作为初始点的所有的深度优先遍历序列和广度优先遍历序列。

答：无向图g的所有的深度优先遍历序列如下：

0 1 4 5 2 3

0 1 5 4 2 3

0 1 4 5 3 2

0 1 5 4 3 2

0 2 1 4 5 3

0 2 1 5 4 3

0 2 3 1 4 5

0 2 3 1 5 4

0 3 1 4 5 2

0 3 1 5 4 2

0 3 2 1 4 5

0 3 2 1 5 4

无向图g所有的广度优先遍历序列如下：

0 1 2 3 4 5

0 1 2 3 5 4

0 1 3 2 4 5

0 1 3 2 5 4

0 2 1 3 4 5

0 2 1 3 5 4

0 2 3 1 4 5

0 2 3 1 5 4

0 3 1 2 4 5

0 3 1 2 5 4

0 3 2 1 4 5

0 3 2 1 5 4

6.对于如图所示的带权无向图，给出利用prim算法（从顶点0开始构造）和 kruskal算法构造出的最小生成树的结果，要求结果按构造边的顺序列出。

答：利用普里姆算法从顶点0出发构造的最小生成树为：{(0，1)，(0，3)，(1， 2)，(2，5)，(5，4)}。利用克鲁斯卡尔算法构造出的最小生成树为：{(0， 1)，(0，3)，(1，2)，(5，4)，(2，5)}

7. 对于一个顶点个数大于4的带权无向图，回答以下问题：

（1）该图的最小生成树一定是唯一的吗？如何所有边的权都不相同，那么其最小生成树一定是唯一的吗？

（2）如果该图的最小生成树不是唯一的，那么调用prim算法和kruskal算法构造出的最小生成树一定相同吗？

（3）如果图中有且仅有两条权最小的边，它们一定出现在该图的所有的最小生成树中吗？简要说明回答的理由。

（4）如果图中有且仅有3条权最小的边，它们一定出现在该图的所有的最小生成树中吗？简要说明回答的理由。

答：（1）该图的最小生成树不一定是唯一的。如何所有边的权都不相同，那么其最小生成树一定是唯一的。

（2）若该图的最小生成树不是唯一的，那么调用prim算法和kruskal算法构造出的最小生成树不一定相同。

（3）如果图中有且仅有两条权最小的边，它们一定会出现在该图的所有的最小生成树中。因为在采用kruskal算法构造最小生成树时，首先选择这两条权最小的边加入，不会出现回路（严格的证明可以采用反证法）。

（4）如果图中有且仅有3条权最小的边，它们不一定出现在该图的所有的最小生成树中。因为在采用kruskal算法构造最小生成树时，选择这3条权最小的边加入时，有可能出现回路。例如，如图所示的带权无向图，有3条边的权均为1，它们一定不会同时都出现在其任何最小生成树中。

kai

开

课