首页 > 其他分享 >25版王道数据结构课后习题详细分析 第六章 图 6.2图的遍历

25版王道数据结构课后习题详细分析 第六章 图 6.2图的遍历

时间:2024-09-02 19:52:55浏览次数:11  
标签:25 优先 遍历 正确 访问 课后 顶点 习题 解析

一、单项选择题

————————————————————

————————————————————

解析:广度优先搜索以起始结点为中心,一层一层地向外层扩展遍历图的顶点,因此无法考虑到边权值,只适合求边权值相等的图的单源最短路径。广度优先搜索相当于树的层序遍历,选项Ⅲ错误。广度优先搜索需要用到队列,深度优先搜索需要用到栈,选项Ⅳ正确。


正确答案:

————————————————————

————————————————————

解析:


正确答案:

————————————————————

————————————————————

解析:DFS(或BFS)可用来计算无向图的连通分量数,因为一次遍历必然会将一个连通图中的所有顶点都访问到,所以计算图的连通分量数正好是DFsTraverse()中DFS被调用的次数。
 


正确答案:

————————————————————

————————————————————

解析:深度优先遍历时,每个顶点表结点和每个边表结点均查找一次。每个顶点递归调用一次。需要借助一个递归工作栈:而广度优先遍历时,也是每个顶卢表结点和每个边敲结点均查找一次,需要借助一个辅助队列。因此,时间复杂度都是O(n +e)。空间复杂度都是O(n)。


正确答案:

————————————————————

————————————————————

解析:在图的广度优先遍历算法中,每个顶点被访问后立即做访问标记并入队。若队列不空,则队首顶点出队,若该顶点的邻接顶点未被访问,则访问之,做访问标记并入队:若被访问过。则跳过,如此反复,直至队空。因此,在广度优先遍历过程中,每个顶点最多入队一次。


正确答案:

————————————————————

————————————————————

解析:采用邻接矩阵表示时,查找一个顶点所有出边的时间复杂度为O(n),共有n个顶点,所以时间复杂度均为O(n^2)。


正确答案:

————————————————————

————————————————————

解析:画出草图后,此类题可以根据边的邻接关系快速排除错误选项。以A为例,在遍历到e之后,应该访问与e邻接但未被访问的结点,(e, c)显然不在边集中。


正确答案:

————————————————————

————————————————————

解析:仅1和4正确。以2为例,遍历到c之后,与c邻接且未被访问的结点为空集,所以应为a的邻接点b或e入栈。以3为例,因为遍历要按栈退回,所以是先b后c,而不能先c后b。


正确答案:

————————————————————

————————————————————

解析:图的深度优先搜索类似于树的先根遍历,即先访问结点,再递归向外层结点遍历,都采用回溯算法。图的广度优先搜索类似于树的层序遍历,即一层一层向外层扩展遍历,都需要采用队列来辅助算法的实现。


正确答案:

————————————————————

————————————————————

解析:DFS序列产生的路径为<1,2>,<2,5>,<5,4>,3,6>;BFS序列产生的路径为<1,2>,<1,4>,2,5>,<3,6>。


正确答案:

————————————————————

————————————————————

解析:画出V和E对应的图G,然后根据搜索算法求解。


正确答案:

————————————————————

————————————————————

解析:利用深度优先遍历可以判断图G中是否存在回路。
对于无向图来说,若深度优先遍历过程中遇到了回边,则必定存在环;对于有向图来说,这条回边可能是指向深度优先森林中另一棵生成树上的顶点的弧;但是,从有向图的某个顶点v出发进行深度优先遍历时,若在DFS(v)结束之前出现一条从顶点u到顶点v的回边,且u在生成树上是v的子孙,则有向图必定存在包含顶点v和顶点u的环。


正确答案:

————————————————————

————————————————————

解析:连通分量是无向图的极大连通子图,其中极大的含义是将依附于连通分量中顶点的所有边都加上,所以连通分量中可能存在回路,这样就不是生成树了。


正确答案:

————————————————————

————————————————————

解析:对于无向图的广度优先搜索生成树,起点到其他顶点的路径是图中对应的最短路径,即所有生成树中树高最小。此外,深度优先总是尽可能“深”地搜索图,因此其路径也尽可能长,所以深度优先生成树的树高总是大于或等于广度优先生成树的树高。


正确答案:

————————————————————

————————————————————

解析:广度优先遍历需要借助队列实现。采用邻接表存储方式对图进行广度优先遍历时,每个顶点均需入队一次(顶点表遍历),所以时间复杂度为O(n),在搜索所有顶点的邻接点的过程中,每条边至少访问一次(出边表遍历),所以时间复杂度为O(e),算法总的时间复杂度为O(n+e)。


正确答案:

————————————————————

————————————————————

解析:只要掌握DFS和 BFS的遍历过程,便能轻易解决。逐个代入,手工模拟,选项D是深度优先遍历,而不是广度优先遍历。


正确答案:

————————————————————

————————————————————

解析:


正确答案:

————————————————————

————————————————————

解析:按深度优先遍历的策略进行遍历。对于A:先访问V,然后访问与V邻接且未被访问的任意一个顶点(满足的有V,V和Vx),此时访问V,然后从V出发,访问与V邻接且未被访问的任意一个顶点(满足的只有V),然后从V出发,访问与V邻接且未被访问的任意一个顶点(满足的只有V),然后从V出发,访问与巧邻接且未被访问的任意一个顶点(满足的只有Vz),结束遍历。B和C的分析方法与A相同。对于D,首先访问V,然后从环出发,访问与邻接且未被访问的任意一个顶点(满足的有 V,7和V),然后从V出发,访问与V邻接且未被访问的任意一个顶点(满足的只有Vs),按规则本应该访问V,但D却访问了V,错误。

二、综合应用题

————————————————————

————————————————————

解答:

————————————————————

————————————————————

解答:

标签:25,优先,遍历,正确,访问,课后,顶点,习题,解析
From: https://blog.csdn.net/2406_86301373/article/details/141825745

相关文章

  • Mysql基础练习题 610.判断三角形 (力扣)
    题目:对每三个线段报告它们是否可以形成一个三角形题目连接:https://leetcode.cn/problems/triangle-judgement/description/建表插入数据:CreatetableIfNotExistsTriangle(xint,yint,zint)TruncatetableTriangleinsertintoTriangle(x,y,z)values('13'......
  • 算法练习题09:滑动窗口最大值(队列、双端队列)
    classSolution{publicint[]maxSlidingWindow(int[]nums,intk){if(nums==null||nums.length==0){returnnewint[0];}intn=nums.length;int[]result=newint[n-k+1];Deque<Integer&......
  • 【2025考研英语高分写作:20大必备范文】经典范文001 辞职信 P33
    Directions:        TwomonthsagoyougotajobasaneditorforthemagazineDesign&Fashions.Butnowyoufindthattheworkisnotwhatyouexpected.Youdecidetoquit.Writealettertoyourboss,Mr.Wang,tellinghimyourdecision,stating......
  • 【2025】基于javaweb的企业仓储库存管理系统(源码+文档+调试+售后)
    该项目含有源码、文档、PPT、图文修改教程、配套开发软件、软件安装教程、项目发布教程、相关文档模板等学习内容。目录一、项目介绍:二、文档学习资料:三、模块截图:四、开发技术与运行环境:五、代码展示:六、数据库表截图:该项目含有源码、文档、PPT、图文修改教程......
  • 2025毕业设计选题|基于Python实现地方美食导游平台
    作者主页:编程千纸鹤作者简介:Java领域优质创作者、CSDN博客专家、CSDN内容合伙人、掘金特邀作者、阿里云博客专家、51CTO特邀作者、多年架构师设计经验、多年校企合作经验,被多个学校常年聘为校外企业导师,指导学生毕业设计并参与学生毕业答辩指导,有较为丰富的相关经验。期待......
  • Affinity Photo 2.5.3.2516 x64 (照片编辑) 授权版
    AffinityPhoto是全球数百万创意和摄影专业人士的首选。这款备受赞誉的图像编辑软件拥有令人难以置信的速度、功能和精度,可以满足您编辑和修饰照片、创建多图层构图、精美的栅格绘图等一切需要。该版本已授权,可以免费使用。软件截图:使用说明:1、将压缩文件解压到某固定位......
  • 2025毕业设计选题|基于Python实现地方美食导游平台
    作者主页:编程千纸鹤作者简介:Java领域优质创作者、CSDN博客专家、CSDN内容合伙人、掘金特邀作者、阿里云博客专家、51CTO特邀作者、多年架构师设计经验、多年校企合作经验,被多个学校常年聘为校外企业导师,指导学生毕业设计并参与学生毕业答辩指导,有较为丰富的相关经验。期待与......
  • 【2025】基于springboot的高校学生食堂点餐系统(源码+文档+调试+答疑)
    ......
  • 春秋云镜CVE-2022-28525(ED01-CMS v20180505 存在任意文件上传漏洞)
    1:访问靶机发现是登录界面2:尝试使用弱口令爆破(明文传输)3:添加pyload并选择攻击类型字典我们随便选择的,实际情况需要实际定义爆破成功,用户名:admin密码:admin登录成功4:找到如图模块,上传图片马上传成功(上传时需要抓包改上传类型)5:使用蚁剑连接,拿到flag......
  • C程序设计语言(第2版·新版)练习题1-18
    练习1-18 编写一个程序,删除每个输入行末尾的空格及制表符,并删除完全是空格的行。#include<stdio.h>#defineMAXLINE1000intgetline(chars[],intlim);intremove_tail(chars[]);intmain(intargc,char*argv[]){(void)argc;(void)argv;......