没有合适的资源?快使用搜索试试~ 我知道了~
算法设计考试试题.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 139 浏览量
2022-05-06
22:17:55
上传
评论
收藏 26KB DOC 举报
温馨提示
试读
2页
算法设计考试试题.doc
资源推荐
资源详情
资源评论
1. 判断下描述命题是否正确,若正确,说明理由,否则给出反例。
命题:给定有向图 G=(V,E),若在图中存在一条从顶点 u 到顶点 v 的路,并且在
图 G 的深度优先搜索过程中,有 d[u]<d[v], 则在产生的深度优先森林中,v 是 u 的后代。
2.如果一个有向图 G=(V,E)的任意的两个顶点之间同一方向最多有一条简单的路,则
该图称为单一连通图(singly connected)。试给出一个判断一个有向图是否是单一连通图
的有效算法。并分析其复杂性。
二 。
1, 设 e 是无向赋权连通图 G=(V,E)中权值最小的边,其他边的权值都大于 e, 证明
图 G 的任意一棵最小生成树包含边 e..
2, 对同一个图 G,Kruskal 算法可以返回不同的的最小生成树,这取决于算法中的对
边的排列顺序。给定图 G 和最小生成树 T,应如何对 G 的边进行排序才能使得对输
入图 G,Kruskal 算法恰好返回 T?
3, 给定一连通赋权无向图 G=(V,E,W)和一整数 b,请设计一个线性得时间 O(|E|+|
V|) 算法,判断是否存在生成树,其每条边权值都不超过 b。请说明算法设计思
想并分析时间复杂性。
三.
1, 给定赋权有向图 G=(V,E,W)及源点 s,若图中的某些边权值为负值,且图中
不含有长度为负值的圈,判断 Dijkstra 算法是否能够正确地找出图 G 中由 s 出发的
所有最短路,若能,说明理由,若不能,给出反例。
2, 给定有向图 G=(V,E),如何利用 Floyd-Warshall 算法的输出矩阵判断图中是
否有长度为负值的图。
3, 有人采用贪心策略,设计了一个在连通图中寻找从顶点 start 到顶点 goal 的最短路
算法;
step1: 初始化 path 为 start
step2: 初始化 VisitedVertices 为{start}
step3: if start = goal then return path; 算法结束;else 继续
step4: 搜索权最小的边(start ,v),其中 v 与 start 邻接,并且 v 不在 VisitedVertices
中
step5: 把顶点 v 添加到 path 中
step6:把顶点 v 添加到 VisitedVertices 中
step7:令 start = v, goto step3
试问这个算法一定能找到从顶点 start 到顶点 goal 的最短路吗?如果能,证明该算法的
正确性。否则,举出一个反例。
四 , 给 定 含 有 16 个 字 母 的 源 字 母 的 源 字 母 表 及 每 个 字 母 的 使 用 频 率 :
15,12,12,10,8,7,6,6,5,4,4,4,3,2,1,1,若用含有四个字母的字母表∑=
{a,b,c,d}上的代码字来表示字母表上的字母,使代码的平均代码字长度最短,请用赫
夫曼(Huffman)算法构造一个最优的前缀代码 C,并给出详细过程。
五,请求出下列网络(弧上的容量已经标出)的最大流及最小割,并给出详细过程。
资源评论
老帽爬新坡
- 粉丝: 83
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功