首页 > 考试题库
题目内容 (请给出正确答案)
[主观题]

试修改Prim算法,使之能在邻接表存储结构上实现求图的最小生成森林,并分析其时间复杂度(森林的存储结构为孩子一兄弟链表)。

试修改Prim算法,使之能在邻接表存储结构上实现求图的最小生成森林,并分析其时间复杂度(森林的存储结构为孩子一兄弟链表)。

查看答案
答案
收藏
如果结果不匹配,请 联系老师 获取答案
您可能会需要:
您的账号:,可能还需要:
您的账号:
发送账号密码至手机
发送
安装优题宝APP,拍照搜题省时又省心!
更多“试修改Prim算法,使之能在邻接表存储结构上实现求图的最小生…”相关的问题
第1题
试写一个算法,判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。 假设分别基于下述策略:1)图的深度优先搜索2)图的广度优先搜索。
试写一个算法,判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。 假设分别基于下述策略:1)图的深度优先搜索2)图的广度优先搜索。

点击查看答案
第2题
n个顶点e条边的图采用邻接矩阵存储,深度优先遍历算法的时间复杂度为_______________;若采用邻接表存储时,该算法的时间复杂度为______________ 。

点击查看答案
第3题
试证明,尽管在允许多边等权时,同一割可能同时拥有多条最短跨越边,6.11.5节中Prim算法所采用的贪心迭代策略依然行之有效。

点击查看答案
第4题
假定有一个100×100的稀疏矩阵,其中1%的元素为非零元素,现要求对其非零元素进行散列存储,使之
能够按照元素的行、列值存取矩阵元素(即元素的行、列、值联合为元素的关键码值),试采用除留余数法构造散列函数和线性探査法处理冲突,分别写出建立散列表和搜索散列表的算法.

点击查看答案
第5题
考查某些边的权重不是正数的带权网络。试证明:a)对此类网络仍可以定义最小支撑树——此时,Prim算法是否依然可行?b)若不含负权重环路,则仍可以定义最短路径树——此时,Dijkstra算法是否依然可行?

点击查看答案
第6题
试修改解旅行售货员问题的分支限界法,使得s=n-2的结点不插入优先队列,而是将当前最优排列存储于bestp中.这样修改后,算法在下一个扩展结点满足条件Lcost≥bestc时结束.

点击查看答案
第7题
设用链表表示一个双端队列,要求可在表的两端插入,但限制只能在表的一端删除。试编写基于此结构
的队列的插人(EnQueue)和删除(DlQueue)算法,并给出队列空和队列满的条件。

点击查看答案
第8题
已知线性表中的元素以值递增有序排列,并以单链表作存储结元素(若表中存在这样的元素),同时释
已知线性表中的元素以值递增有序排列,并以单链表作存储结元素(若表中存在这样的元素),同时释

放被删结点空间,并分析你的算法的时间复杂度(注意,mink和maxk是给定的两个参变量,它们的值可以和表中的元素相同,也可以不同)。

点击查看答案
第9题
设已给出图的邻接表表示G1,编写一个算法,将图的邻接表表示G1转换成邻接矩阵表示G2.

点击查看答案
第10题
考查中序遍历迭代式算法的第三个版本(教材131页代码5.18)。试继续改进该算法,使之不仅无需辅助栈,而且也无需辅助标志位。

点击查看答案
退出 登录/注册
发送账号至手机
密码将被重置
获取验证码
发送
温馨提示
该问题答案仅针对搜题卡用户开放,请点击购买搜题卡。
马上购买搜题卡
我已购买搜题卡, 登录账号 继续查看答案
重置密码
确认修改