当前位置： 文档下载 > 所有分类 > 自然科学 > 数学 > 算法设计与分析试题1算法设计与分析试题
一、
对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。
解：用V1表示已经找到最短路径的顶点，V2表示与V1中某个顶点相邻接且不在
V1中的顶点；E1表示加入到最短路径中的边，E2为与V1中的顶点相邻接且距离最
短的路径。【1分】
步骤 V1 V2 E1 E2 1. {a} {b} {} {ab} 2. {a,b} {d} {ab} {bd} 3. {a,b,d} {c,f} {ab,bd} {dc,df} 4. {a,b,d,c} {f} {ab,bd} {df} 5. {a,b,c,d,f} {e} {ab,bd,dc,df} {fe} 6. {a,b,c,d,e,f} {g} {ab,bd,dc,df,fe} {eg} 7. {a,b,c,d,e,f,g} {h} {ab,bd,dc,df,fe,eg} {gh}
8. {a,b,c,d,e,f,g,h} {} {ab,bd,de,df,fe,eg,gh} {} 【以上
每步2分】 结果：从a到h的最短路径为a b d f e g h，权值为18。【1分】 求所有顶点对之间的最短路径可以使用Dijkstra算法，使其起始节点从a循环到h，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。【2分】
二、
假设有7个物品，它们的重量和价值如下表所示。若这些物品
均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树。
算法设计与分析习题答案1-6章_理学_高等教育_教育专区 暂无评价0人阅读0次下载举报文档 算法设计与分析习题答案1-6章_理学_高等教育_教育专区。习题 1 1....
(1)用计算机求解问题的步骤: 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、 程序调试 8、结果整理文档编制 (2)...
算法设计与分析考试题及答案_IT/计算机_专业资料。算法试题及答案一、填空题(20 分) 填空题 1.一个算法就是一个有穷规则的集合, 其中之规则规定了解决某一特 ...
2009.1算法设计与分析课程期末试卷-A卷(含答案)_理学_高等教育_教育专区。华南农业大学算法设计与分析期末考试试卷华南农业大学期末考试试卷(A 卷) 2008 学年第一...
性质 。 重叠子问题 三、算法设计题(27 分) 1、 分)写出欧几里得迭代算法(注意是迭代算法) (7 int Gcd(int m,int n) { If(m==0)return n; If(n==...
( n ) D、 O (1) 第九组算法设计与分析考试试题 组成员:0982030 古明冬 0982054 吴昊 0982035 许文龙 0982032 王勇 0982044 储斌斌 时间:2012/5/11 0:...
2013计算机算法设计与分析期终考试复习题(1)_工学_高等教育_教育专区。V 计算机算法设计与分析复习题一、填空题 1、 一个算法复杂性的高低体现在计算机运行该算法所...
华南农业大学期末考试试卷(A 卷) 2007 学年第一学期考试类型: (开卷) 学号 题号 得分 评阅人 一 姓名 二 考试科目:考试时间: 算法分析与设计 120 分钟 年级...
算法设计与分析期末试卷一.选择题(15*2 分) 1.下列不属于一个好的算法应具有的特性的是(C) A.正确性 B.简明性 C 无限性 D 最优性 2.矩阵连乘问题的...
算法设计与分析复习题_IT/计算机_专业资料。算法设计与分析复习题算法设计与分析复习题 1、 一个算法应有哪些主要特征? 又穷性,确定性,可行性,0 个或多个输入,...
热门文档