数据结构——图(习题篇)

这篇具有很好参考价值的文章主要介绍了数据结构——图(习题篇)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

本文会挑选图中相关例题进行讲解,并复习相关的知识点
建议先将题做一次,再看题解和答案

题1

设图的邻接矩阵如下所示,各顶点的度依次是( )
A.1,2,1,2
B.2,2,1,1
C.3,4,2,3
D.4,4,2,2

[ 0 1 0 1 0 0 1 1 0 1 0 0 1 0 0 0 ] \left[ \begin{matrix} 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 \end{matrix} \right] 0001101001001100
[分析]
该题考察的是邻接矩阵的特性及有向图、无向图的特性
[方法]
由于该邻接矩阵为非对称矩阵,说明图是有向图。
度为入度与出度之和。各顶点的度是矩阵中此结点对应的行(对应出度)和列(对应入度)的非零元素之和
以节点一为例,该结点对应的行(出度)为2,对应的列(入度)为1,因此该点的度为3,其他以此类推
[答案]C

题2

如果从无向图的一个顶点出发,进行一次深度优先搜索就能访问所有的结点,则该无向图一定()
A.是连通图
B.是强连通图
C.有回路
D.是有向无环图

[分析]
该题考察的是对DFS的理解以及连通图/连通图/完全图/有向无环图的理解
[方法]
连通图:任意两个顶点之间都能够连通,则该无向图成为连通图(连通:图中从一个顶点到达另一顶点,若存在至少一条路径,则称这两个顶点是连通的)
强连通图:在有向图中,若任意两个顶点 Vi 和 Vj,满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通,也就是都含有至少一条通路,则称此有向图为强连通图
有向无环图:有向无环图中每条边都有一个定义的方向,每条边都是从一个顶点到另一个顶点的单方向流。并且有向无环图是非循环的,对于任何顶点来讲,如果沿着通过顶点连接到另一个顶点的边,是无法返回该初始顶点
DFS的思想是假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止
由于强连通图和有向无环图均为有向图,与题意不符,而经过一次DFS就可以访问所有的结点(因为在连通图中至少存在一条路径使两个顶点联通,即可相互访问,而连通图是没有回路的,因此排除C)
[答案]A

题3

下列关于 AOE网的叙述中,不正确的是 ()
A.关键活动不按期完成就会影响整个工程的完成时间
B.任何一个关键活动提前完成,那么整个工程将会提前完成
C.所有的关键活动提前完成,那么整个工程将会提前完成
D.某些关键活动提前完成,那么整个工程将会提前完成

[分析]
考察的是对AOE网的理解,特别是关键活动和关键路径的理解
[方法]
AOE网:AOE网是用边表示活动,用顶点表示事件(活动的完成)。边是带权的,表示活动需要的时间,对入度为0的点称为工程的开始点,对出度为0的点成为工程的结束点
以下哪个命题是正确的? a. 对于带权无向图g = (v, e),m是g的最小生成树,则m中任意,数据结构,图论
AOE网中,从开始点到结束点最长的路径称为关键路径,在关键路径上的活动称为关键活动。
答案A,关键路径长度代表整个工期的最短完成时间,关键活动延期完成,必将导致关键路径长度增加,即整个工期的最短完成时间增加,因此正确
答案B,网中的关键路径不唯一。对于有几条关键路径的网来说,单单提高一条关键路径上关键活动的速度,是不能缩短整个工程工期的,而必须同时提高几条关键路径上活动的速度,因此错误
通过对A,B的讲解,也可以说明所有的关键活动提前完成,那么整个工程将会提前完成,某些关键活动(交汇点)提前完成,工程能提前完成
[答案]B

题4

已知有向图 G=(V,E),其中 V={V1,V2,V3,V4,Vs,V6,V7},E={V1,V2>,<V1,V3>,<V1,V4><V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>,G的拓扑序列是( )。
A.V1,V3,V4,V6,V2,V5,V7
B.V1,V3,V2,V6,V4,V5,V7
C.V1,V3,V4,V5,V2,V6,V7
D.V1,V2,V5,V3,V4,V6,V7

[分析]
该题考察的是根据有向图构造拓扑序列,主要通过排除法做此类题
[方法]
图的拓扑序必须要满足以下两点:
1.每个顶点只出现一次。
2.对于图中的任何一条边,起点必须在终点之前。

按照上图V和E的关系可以画出如下有向图G
以下哪个命题是正确的? a. 对于带权无向图g = (v, e),m是g的最小生成树,则m中任意,数据结构,图论
对B选项V6在V4前,因此排除;对C选项,V5在V2前,因此排除;对D选项,V5在V3前,因此排除
[答案]A

题5

设有无向图G=(V, E)和G’=(V’, E’),若G’是G的生成树,则下列不正确的是()
a.G’为G的连通分量
b.G’为G的无环子图
c.G’为G的极小连通子图且V’ = V
A、a和b
B、只有c
C、b和c
D、只有a

[分析]
考察的是对生成树的理解
[方法]
生成树的定义为:如果连通图G的一个子图是一棵包含G的所有顶点的树,则该子图称为G的生成树,图的生成树不唯一。从不同的顶点出发进行遍历,可以得到不同的生成树。边的个数应为顶点个数减一
以下哪个命题是正确的? a. 对于带权无向图g = (v, e),m是g的最小生成树,则m中任意,数据结构,图论

连通图中的生成树必须满足以下 2 个条件:
1.包含连通图中所有的顶点;
2.任意两顶点之间有且仅有一条通路;

因为极大连通子图简称连通分量,生成树是极小连通子图。故a不对,c对。
生成树无环,故b对
[答案]D

题6

对于有n个点、e条边的连通图用Prim算法最小生成的时间树复杂度为_________,利用 Kruskal算法最小生成的时间复杂度为_________
[分析]
考察的是对Prim算法和Kruskal算法运用的理解
[方法]
对Prim算法,是采用贪心算法的思想。对于包含 N 个顶点的连通网,普里姆算法每次从连通网中找出一个权值最小的边,以迭代方式重复N-1次,由N-1条权值最小的边组成的生成树就是最小生成树
对Kruskal算法,是将连通网中所有的边按照权值大小做升序排序,从权值最小的边开始选择,只要此边不和已选择的边一起构成环路,就可以选择它组成最小生成树。对于N个顶点的连通网,挑选出N-1条符合条件的边,这些边组成的生成树就是最小生成树
因这里算时间复杂度有一定麻烦,大家可以先记住答案,有空可以看看具体的算法流程去理解时间复杂度的问题
结论是:Prim算法采用的是邻接矩阵作为存储结构,更适合于稠密图的最小生成树,复杂度为O(n^2),Kruskal算法采用的是边集数组作为存储结构,更适合于稀疏图的最小生成树,复杂度为O(elog2e)
[答案] O(n^2)     O(elog2e)

题7

在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为()
A.e     B.2e     C.n^2-e     D.n^2-2e

[分析]
考察的是对无向图和邻接矩阵的理解
[方法]
对无向图而言,邻接矩阵一定是对称的,而且主对角线一定为零,副对角线不一定为0,用邻接矩阵来表示一个具有n个顶点的有向图时需要n^2个单元来存储邻接矩阵,由于对称的特性,药达到对称的标准,则e条边在邻接矩阵的表现是2e(1条边在邻接矩阵的表现为两个位置非0),因此1元素个数为2e,零元素个数为n ^2-2e
用下图简单的图来表示:
以下哪个命题是正确的? a. 对于带权无向图g = (v, e),m是g的最小生成树,则m中任意,数据结构,图论
因为无向图的特性,如果V1和V2有连接,在邻接矩阵上(1,2)和(2,1)均为1,因此e条边对应的1元素的个数是2e,因此零元素个数为n ^2-2e
[答案]D

题8

(判)一个有向图的邻接表和逆邻接表中的结点个数一定相等
[分析]
考察的是对邻接表和逆邻接表的理解
[方法]
邻接表是指每个单链表的第一个结点存放有关顶点的信息,把这一结点看成链表的表头,其余结点存放有关边的信息,反应的是顶点出度的情况,而逆邻接表反应的是顶点的入度情况
因此邻接表和逆邻接表的区别仅在于入边和出边,只是调整方向,而节点个数是相等的
[答案]√

题9

(判)对于带权无向图 G = (V, E),M 是 G 的最小生成树,则 M 中任意两点 V1 到 V2 的路径一定是它们之间的最短路径。
[分析]
考察的是对最小生成树的理解
[方法]
由于图的所有生成树中具有边上的权值之和最小的树称为图的最小生成树,但最小生成树的总权最小,不是其中的某一条任意路径最小,因此V1和V2的路径不一定是最小的
[答案]×

题10

用Dijkstra算法是通过求________________________的次序来得到最短路径的
[分析]
考察的是对Dijkstra算法的理解
[方法]
Dijkstra算法是一种类似于贪心的算法
步骤如下:图为G={V,E}
1.初始时令 S={V0},T=V-S={其余顶点},T中顶点对应的距离值
若存在<V0,Vi>,d(V0,Vi)为<V0,Vi>弧上的权值
若不存在<V0,Vi>,d(V0,Vi)为∞
2.从T中选取一个与S中顶点有关联边且权值最小的顶点W,加入到S中
3.对其余T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的距离值缩短,则修改此距离值
[答案]
求某一顶点到其余各顶点间的最短路径是按路径长度递增文章来源地址https://www.toymoban.com/news/detail-804209.html

到了这里,关于数据结构——图(习题篇)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构习题24/12/24

    这道题目可以考虑,如果前缀是一样的长度,那么只需要两个链表同时向后检索,直到找到一样的元素为止。所以应该先找到两个链表的长度,然后将较长的一个链表的多出来的前缀部分删掉,也就不去看这一部分。因为后缀都是一样的,所以长度的差异只可能来自前缀。

    2024年02月04日
    浏览(44)
  • 【数据结构】——图的相关习题

    1、具有n个顶点的有向完全图有()条弧边。 A、n(n-1)/2 B、n(n-1) C、n(n+1)/2 D、n(n+1) 解析: (B) 若一个有向图中,若每个顶点都有互相相反的两条弧连接,则称为有向完全图,在一个含有n个顶点的有向完全图中,共有 n(n-1) 条弧。 例如,含有4个顶点的有向完全图

    2024年02月05日
    浏览(50)
  • 【数据结构】第二章课后练习题——线性结构

    1、线性表是 一个有限序列,可以为空 2、链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素,则采用 单循环链表 存储方式最节省运算时间 3、若某线性表中最常用的操作实在最后一个元素之后插入一个元素和删除第一个元素,则采用 仅有尾结点的

    2024年02月07日
    浏览(59)
  • 【数据结构】——栈、队列的相关习题

    1、栈和队列都是()。 A、顺序存储的线性结构 B、链式存储的非线性结构 C、限制存取点的线性结构 D、限制存取点的非线性结构 解析: (C) 栈 是一种只允许在一端进行插入或删除操作的线性表,它是一种特殊的线性表,它与队列具有相同的逻辑结构,都属于 线性结构

    2024年02月12日
    浏览(39)
  • 【数据结构】——排序算法的相关习题

    1、直接插入排序 1、对n个元素进行直接插入排序,需要进行()趟处理。 A、n B、n+1 C、n-1 D、2n 解析: (C) 直接插入排序是将要排序的序列按照的大小插入至已排好序的子序列中,一直进行直到整个序列有序,所以对n个元素进行直接插入排序,一共插入元素n-1次,

    2024年02月03日
    浏览(45)
  • 王道数据结构精选习题及解析

    暴力法的时间复杂度为O(n²) 不要忽略有序性 思路:因为是有序的顺序表,所以重复的元素一定是连在一起的。那我们就使用两个指针,一个指针指向当前不重复有序表的最后一个元素,另一个会从头到尾遍历整个有序表,称为工作指针。 我们让工作指针往后移,如果与当

    2024年02月10日
    浏览(48)
  • 数据结构复习题(包含答案)

    1、研究数据结构就是研究( D  )。 A. 数据的逻辑结构                      B. 数据的存储结构    C. 数据的逻辑结构和存储结构    D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是(  A )。 A. 空间复杂度和时间复杂度         B. 正

    2024年02月09日
    浏览(38)
  • [数据结构习题]栈——中心对称链

    👉 知识点导航 💎:【数据结构】栈和队列 👉[王道数据结构]习题导航💎: p a g e 70.4 page70.4 p a g e 70.4 本节为栈和链表综合练习题 题目描述: 🎇 思路:前段进栈 🔱 思路分析: 要判断一个带头结点的单链表是否中心对称,即链表的前半部分和后半部分互为逆序关系,因

    2024年02月07日
    浏览(38)
  • 数据结构与算法系列之习题练习

    💗 💗 博客:小怡同学 💗 💗 个人简介:编程小萌新 💗 💗 如果博客对大家有用的话,请点赞关注再收藏 🌞 括号匹配问题。 用队列实现栈。 用栈实现队列。 设计循环队列。 有效的括号 //用栈来实现 //左括号进栈 右括号出栈并销毁如果不匹配则return //设置两个队列,入栈

    2024年02月11日
    浏览(47)
  • 【数据结构】“单链表”的练习题

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 :阿然成长日记 👈点击可跳转 📆 个人专栏: 🔹数据结构与算法🔹C语言进阶 🚩 不能则学,不知则问,耻于问人,决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 题目要求: 给你单链

    2024年02月14日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包