当前位置:首页 >> 其它课程 >> 《算法设计与分析》复习题参考答案

《算法设计与分析》复习题参考答案


《算法设计与分析》复习题
一、 概念题:请解释下列术语。
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 数据类型 队列 多项式复杂度 满二叉树 NP-难度 算法 SIMD(并行算法) 连通图 抽象数据类型 指数复杂度 递归 完全二叉树 状态空间树 NP-完全的 算法

与过程 有向图与无向图 树 P 类问题 确定的算法 NP 问题

二、填空题
1. 简单递选分类过程中所需进行移动存储的操作次数较少,其最大值为___________。 2. 一组有序的 n 个数,采用逐个查找算法查找一给定的数是否出现在序列中,其算法 复杂性为_____________。 3. 动态规划实际上是研究一类__________________的算法,其应用非常广泛。 4. BFS 算法的中文名称是______________________算法。 5. 一棵树中 定义为该树的高度或深度。 6. 二分检索树要求树中所有结点中的元素满足 。 7. 比较树的结点由称为 和 的两种结点组成。 8. 外结点用一个 结点表示,在二分检索算法中它表示不成功检索的一种情况。 9. 由根到所有内部结点的距离之和称为 ; 由根到所有外部结点的距离之和称 为 . 10.max 和 min 被看成是两个内部函数,它们分别求取两个元素的大者和小者,并认为 每次调用其中的一个函数都只需作 次元素比较。 11.如果用分治策略来设计分类算法,则可使最坏情况时间变为 o(n logn)。这样的算法 称为 。 12. 贪心算法可行的第一个基本要素是 。 13. 当一个问题的最优解包含着它的子问题的最优解时,称此问题具有 性质。 14. 二路归并模式可以用 树来表示。

15. kruskal 算法对于每一个无向连通图 g 产生一棵 。 16.因为如果有环,则可去掉这个环且不增加这条路径的长度 (不含有负长度的环)。如 果 k 是这条最短路径上的一个中间结点,那么—由 i 到 k 和由 k 到 j 的这两条子路径 应分为别是由 i 到 k 和.由 k 到 j 的最短路径。否则,这条由 i 到 j 的路径就不是具 有最小长度的路径。于是, 原理成立。 17.为了把动态规划应用于得到一棵最优二分检索树的问题, 需要把构造这样的一棵树看 成是一系列决策的结果,而且要能列出求取 序列的递推式. 18. 所谓可靠性设计最优化问题是在 的约束下, 如何使系统的可靠性达到最优的 问题。 19.货郎担问题是求取具有 的周游路线问题。

三、程序填空题。
1.对二叉树的先根次序周游算法递归表示为: procedure PREORDER(T) //T 是一棵二元树。T 中每个结点有三个信息段:ICHILD, ,DATA,RCHILD// if T≠0 then call VISIT(T) __________(1)___________ __________(2)___________ endif end PREORDER 2.递归求取最大和最小元素 procedure MAXMIN(i.j. fmax,fmin) //A(1:n)是含有 n 个元素的数组,参数 i,j 是整数,1≤i,j≤n// //该过程把 A(i,j)中的最大和最小元素分别赋给 fmax 和 fmin// integer i,j;global n,A(1:n) case :i=j:fmax?fmin?A(i) :i=j-1:if A(i)<A(j) then fmax?A(j);fmin?A(i) else fmax?A(i);fmin?A(j) endif

? : else: mid? ? ___________(1)______________ ___________(2)______________ fmax?max(gmax,hmax) fmin?min(gmin,hmin) endcase end MAXMIN
(i ? j ) / 2
3.用回溯法求子集和数问题的递归回溯算法 procedure SUMOFSUB<s,k,r) //找 W(1: n)中和数为 M 的所有子集, 进入此过程时 X(1), ?, X(k-1)的值已确定。

s ? ?W ( j ) X ( j )且r ? ?W ( j )
j ?1 j ?k

k ?1

n

。 这些对W(j)按非降次序排列。 假定 W(1)≤M.// global integer M,n; global real W(1:n);global Boolean X(1:n) real r,s;integer k,j

//生成左儿子。注意,由于

Bk ?1 ? true ,因此 s+W(k)≤M//

X(k)?1 if s+W(k)=M then //子集找到// print (X(j),j?1 to k ) else if s+W(k)+W(k+1)<=M then //B k =yrue// ______________(1)__________________ endif //生成右儿子和计算 B endif
k

的值//

if s+r-W(k)≥M and s+W(k+1)≤M //B k =true// then X(k)?0 _______________(2)_________________ endif end SUMOFSUB 4.用回溯法求 n-皇后问题的所有解 procedure NQUEENS(n) //此过程使用回溯法求出在一个 n*n 棋盘上放置 n 个皇后,使其不能互相攻击 的所有可能位置// integer k,n,X(1:n) X(1)?0;k?1 //k 是当前行;X(k)是当前列// while k>0 do //对所有的行执行以下语句// X(k)?X(k)+1 //移到下一列// while X(k)≤n and not PLACE(k) do //此处能放这个皇后吗// ____________(1)___________ repeat if X(k)≤n //找到一个位置// then if k=n //是一个完整的解吗// then print(X) //是,打印这个数组// else _______(2)_______; _______(3)_______; //转向下一行// endif else _______(4)_______ //回溯// endif repeat end NQUEENS

5. 二分查找算法 procedure binsrch1 (a,n,x,j) //除 n>0 外,其余说明与 binsrch 同// integer low,high,mid,j,n; low?1;high? (1) //high 总比可能的取值大 1// while low< (2) do mid? ?

(low ? high) / 2?

if x<a(mid) //在循环中只比较一次// then (3)

else

(4)

//x≥a(mid)//

endif repeat if x=a(low) then j?low //x 出现// else j?o //x 不出现// endif; end binsrch1

6.求图中每对顶点之间的最短路径。 procedure all—Paths(cost,a, n) //cost(n,n)是 n 结点图的成本邻接矩阵;a(i,j)是结点 vi 到 vj 的最短路径的 成本;cost(i,j)=0,1≤i≤n// integer i,j,k,n;real cost(n,n),a(n,n) for i?1 to n do for j<--1 to n do a(i,j)<--cost(i,j) repeat repeat //将 cost(i,j)复制到 a(i,j)// for k<--1to on do //对最高下标为 k 的结点的路径// for i?-1 to n do //对于所有可能的结点对// for i<--1 to n do a(i,j)<--min{ (1) , (2) } repeat repeat repeat end all—Paths 7. 简单的合并与查找运算
procedureu(i,j) //根为 i 和 j 的两个不相交集合用它们的并来取代// integeri,j Parent(i)<--j; end u proceduref(i) //找包含元素 i 的树的根// integeri,j j<--i; while repeat return(j) ⑴ ⑵ do //若此结点是根,则 Parent(j)<--0// ;

end f

8. 插入分类 procedure insertionsort(a,n) //将 a(1:n)中的元素按非降次序分类,n≥1// a(0)?-∞ //开始时生成一个虚拟值// for j? ⑴ to n do //a(1:j-1)已分类// item?a(j);i? ⑵ while item<a(i) do //0≤i<j// a(i+1)?a(i);i?i-1 repeat a(i+1)?-item repeat end insertionsort 9. 归并分类 procedure mergesort(low, high) //a(low: high)是一个全程数组,它含有 high-low+1≥0 个待分类的元素// integer low, high; if low<high; then mid? ? call call call endif end mergesort 10. 使用链接表归并已分类的集合 procedure merge1 (q,r,p) //q 和 r 是全程数组 link(1:n)中两个表的指针。这两个表可用来获得全程数组 a(1: n)中已分类元素的子集合。 此算法执行后构造出一个由 p 所指示的新表, 利用此表可以得到按非降次序把 a 中元素分好类的元素表, 同时 q 和 r 所指示 的表随之消失。假定 link(0)被定义,且假定表由 0 所结束// global n, a(1:n),link(0:n) local integer i,j,k i?q;j?r;k?0 //新表在 link(0)处开始// while ⑴ and ⑵ do //当两表皆非空时作// if a(i)≤a(j) //找较小的关键字// then link(k)?i;k?i;i?link(i) //加一个新关键字到此表// else ⑶ endif repeat if i=0 then ⑷ else link(k)?i

(low ? high) / 2?
⑴ ⑵ ⑶

//求这个集合的分割点// //将一个子集合分类// //将另一个子集合分类// //归并两个已分类的子集合//

endif p?link(0) end mergel 11. 作业排序算法的概略描述 procedure greedy-job(d,j,n) //作业按 p1≥p:≥…≥Pn 的次序输入,它们的期限值 d(i)≥1,1≤i≤n,n≥1.j 是在它们的截止期限前完成的作业的集合// j?{1} for ⑴ to n do if j∪{i}所有作业都能在它们的截止期限前完成 then ⑵ endif repeat end greedy—job 12. 生成二元归并树算法 line proceduretree (l,n) //l 是 n 个单结点二元树的表// for i?1 to n-1 do call getnode(t) //用于归并两棵树// lchild (t)<--least(l) //最小的长度/ rchild (t)<--least(l) weight(t)<-⑴ call insert(l,t) repeat ⑵ //留在 l 中的树是归并树" end tree 13. kruskal 算法 line procedure kruskal(e, cost ,n,t ,mincost) //g 有 n 个结点,e 是 g 的边集。cost(u,v)是边(u,v)的成本。t 是最小成本 生成树的边集。mincost 是它的成本" real mincost,cost(1:n,1:n); integer Parent(1:n),t(1:n-1,2),n; 以边成本为元素构造一个 min—堆 Parent?1 //每个结点都在不同的集合中矿 i?mincost?0 while i<n 一 1 and 堆非空 do 从堆中删去最小成本边(u,v)并重新构造堆 j?find(u);k?find(v) if j≠k then ⑴ t(i,1)<—u t(i,2)?v mincost<— ⑵ call union(i,k)

endif repeat if i≠n-1 then print(?no spanning tree?) endif return end kruskal 14. 多段图的向前处理算法 line procedure fgraPh(e,k,n,P) //输入是按段的顺序给结点编号的,有 n 个结点的 k 段图。e 是边集,c(i,j)是边 <i,j>的成本。P(1:k)是最小成本路径// real cost(n),integer d(n 一 1),P(k),r,j,k,n ⑴ for j<--n 一 1 to 1 by 一 1 do //计算 cost(j)// 设 r 是一个这样的结点,<j,r>∈e 且使 c(j,r)+cost(r)取最小值 cost(j)+c(j,r)+cost(r) d(j)?r repeat //找一条最小成本路径// P(1)<一 1;P(k)?n for j<--2 to ⑵ do //找路径上的第斗个结点// P(j)<--d(P(j 一 1)) repeat end fgraPh 15.求最小元的并行算法 procedure mimdmin(a(1),a(2),...,a(n),min) 输入;i={a(1),a(2),…,a<n}} 输出:i 中最小元 min 处理器个数;p if n>p then for each pi:1≤i≤ppardo for j=i+p to n step p do if ⑴ then a(i)?a(j) endif repeat endfor k?p else k?n; endif while k>l do for each pi:1≤i≤[k/2] pardo if a(k-i+1)<a(i) then ⑵

endif endfor k?[k/2] repeat min?a(1) end mimdmin 16.0/1 背包问题的回溯法求解 。 procedurebknaPl(m,n,w,P,fw,fp,x) //m 是背包容量。有 n 种物品,其重量与效益分别存在数组 w(1:n)和 P(1: n)中 sp(i)/w(o≥P(i+1)/w(i+1)。fw 是背包的最后重量,fp 是背包取得 的最大效益。x(1:n)中每个元素取 0 或 1 值。若物品 k 没放人背包,则 x (k);0;否则 x(k)=1// integer n,k,y(1:n),i,x(1:n);real,m,w(1:n),P(1:n),fw,fp,cw,cp; cw?cp?o;k?1;fp?l //cw 是背包当前重量;cp 是背包当前取得的效益值// loop while k≤n and ⑴ ≤m do //将物品、k 放人背包// cw ?cw+w(k);cp?cp+P(k);y(k)?1;k?k+1 repeat if k>n then fp?cp;fw?cw;k?n;x?y //修改解// else ⑵ //超出 m,物品 k 不适合// endif while bound(cp、cw,k,m) ≤fp do //上面置了 fp 后,bound=fp// while k ? 0 and y(k) ? 1 do k?k-1 ,//找最后放人背包的物品// repeat if k=0 then return endif //找最后放人背包的物品// y(k)?0;cw?cw-w(k);cp?cp—P(k) //移掉第 k 项// repeat k?k+1 repeat end bknaPl

四.问答题
1. 算法的重要的 5 个特征是什么? 2. 什么是动态规划? 3.回溯程序的 4 种因素是什么? 4.请解释贪心法的基本思想,并用贪心法解决如下背包问题。 背包问题:n=3, M=30, (p1,p2,p3) = (20,14,25), (w1,w2,w3)=(20,15,15) 5.请解释动态规划的基本思想,并写出用动态规划解决 0/1 背包问题所采用的递推方 程式。 6. 请解释动态规划的基本思想, 并写出用动态规划解决多段图问题所采用的递推方程

式。 7.请解释回溯法的基本思想,并写出用回溯法解决子集和数问题的状态空间树。 8.已知如下定义的数据结构,请画出它的逻辑示意图,并说明它是何种类型的数据结 构。 DS = <D,R,OP> D = { 1, 2, 3, 4, 5, 6} R = { <1,2>, <1,3>, <2,3>, <3,6>, <3,5>, <5,4>, <6,2>, <4,3>, <5,6> } 9.若将数据序列 D={1,2,3}输入堆栈,请给出所有可能的堆栈输出。 10. 已知如下多段图, 请用动态规划方法的向后处理法写出求解此问题的递推公式并完 成对各结点的计算。

V1

V2
2
2 9 7 4

V3
6
2 7 4 3 6

V4
9
5 4

V5

3

2

s

1

3

7 4
11 11 1 5 6

10

12 t

2

5

8 5
8

11

11. 请用 Prim 方法求下图所示的最小生成树。 (请写出该方法的基本思想和主要中间过 程) 。
1 10 2 40 5 55 20 6 15 50 35 3

30 45 4 25

12. 最佳原理的基本思想是什么? 13. 利用分枝定界法求解流动推销员问题。设给定 5 个城市的距离矩阵为

? 14 14 ?
D =

1 25 9 9

16 2 2 9 ? 6 3 9 6 ?
= ( dij ) 5×5

1 16 2

25 ? 2 3

《算法设计与分析》复习题参考答案
二、 概念题:请解释下列术语。
1.数据元素的集合。 2.队列是一个线性表,限制为只能在固定的一端进行插入,在固定的另一端进行删除。 3.对于算法 a,如果存在一多项式 p(),使得对 a 的每个大小为 n 的输入,a 的计算时 间为 o(p(n)),则称 a 具有多项式复杂度 4.二叉树的层数 i 与该层上的结点数 n 的关系为: n(i)= 2 。 5.如果可满足性约化为一个问题 L,则称该问题为 NP-难度的。 6.算法就是一组有穷的规则,它规定了解决某一特定类型问题的一系列运算。 。 7.多数据单指令流 8.若图的任意两个节点间均存在路径可达,则称该图为连通图。 9. 是指一个数学模型以及定义在该模型上的一组操作。 10.算法的复杂度只能用指数函数对其限界。 11.函数或过程直接或间接调用它自己。 12.和高度相同的满二叉树的每个对应的顶点编号相同的树 13.由所有可行状态所构成的树。 14.如果 L 时 NP 难度的且 L∈ NP,则称问题 L 是 NP-完全的。 15.算法是一个步骤的序列,满足:有穷性、可行性、确定性、输入、输出;过程不需 要满足由穷性。 16.有向图的每条边有起点与终点之分,且用箭头指向边的终点。无向图的边无起点和 终点之分,边无箭头。 17.树(tree)是一个或多个结点的有限集合, ,它使得:①有一个特别指定的称作根(root) 的结点;②剩下的结点被分成 m≥0 个不相交的集合 tl,?,tm,这些集合的每一 个都是一棵树,并称 t1,?,tm 为这根的子树(subtree)。 18.P 是所有可在多项式时间内用确定算法求解的判定问题的集合。 19.运算结果是唯一确定的算法 20. nP 是所有可在多项式时间内用不确定算法求解的判定问题的集合
i

二、填空题
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. n O ( n ) 最优化问题 宽度优先搜索 结点的最大级数 互异 内结点和外结点 方形 内部路径长度、外部路径长度 一次 归并分类算法

12. 13. 14. 15. 16. 17. 18. 19.

贪心选择性质 最优子结构 二元归并 最小成本生成树 最优性 最优决策 可容许最大成本 c 最小成本

三、程序填空题。
1. 2. 3.
4. call PREORDER(LCHILD(T)) call PREORDER(RCHILD(T)) call MAXMIN(i,mid,gmax,gmin) call MAXMIN(mid+1,j,hmax,hmin) call SUMOFSUB (S+w(K),K+1,r-W(k)) call SUMOFSUB(s,k+1,r—W(k)) X(k)+X(k)+1 k <- k+1; X(k) <- 0 k?k-1 (1)n+1 (2) high-1 (3) high?mid (4)low?mid (1) a(i,j) (2)a(i,k)+a(k,j) (1) Parent(i)>0 (2) j<--Parent(j) (1) 2 (2) j-1 (1) mergesort(low,mid) (2) mergesort(mid+1,high) (3) merge(low,mid,high) (1) i≠0 (2) j≠0 (3) link(k)?j;k?j;j?link(j) (4) llnk(k)?j (1) i?2 (2) j?j∪ {i} (1) weight(lchild(t))+weight(rchild(t)) (2) return(least(l)) (1)i?i+1 (2) mincost + cost(u,v) (1) cost(n)<--0 (2) k 一 1 (1)a(j)<a(i) (2)a(i)?a(k-i+1) (1)cw+w(k) (2)y(k)?0

5. 6. 7.
8.

9. 10. 11. 12. 13. 14. 15. 16.

四.问答题
1. 答: 1).确定性 算法的每一种运算必须要有确切的定义, 即每一种运算应该执行何种动作必须是相 当清楚的、无二义性的。在算法中不允许有诸如“计算 5/0”或“将 6 或 7 与 x 相加”之类的运算,因为前者的结果是什么不清楚,而后者对于两种可能的运算应 做哪一种也不知道。 2).能行性 一个算法是能行的指的是算法中有待实现的运算都是基本的运算,每种运算至少 在原理上能由人用纸和笔在有限的时间内完成。整数算术运算是能行运算的一个 例子,而实数算术运算则不是能行的,因为某些实数值只能由无限长的十进制数

展开式来表示,像这样的两个数相加就违背能行性这一特性。 3).输入 一个算法有 0 个或多个输入,这些输入是在算法开始之前给出的量,这些输入取 自特定的对象集合。 4).输出 一个算法产生一个或多个输出,这些输出是同输入有某种特定关系的量。 5).有穷性 一个算法总是在执行了有穷步的运算之后终止。 2. 答: 在实际生活中,有这么一类问题,它们的活动过程可以分为若干个阶段,而且 在任一阶段后的行为都仅依赖于 i 阶段的过程状态,而与 i 阶段之前的过程如何达 到这种状态的方式无关,这样的过程就构成一个多阶段决策过程。在 50 年代,贝尔 曼(richard bellman)等人根据这类问题的多阶段决策的特性,提出了解决这类问题 的“最优性原理”,从而创建了最优化问题的一种新的算法设计方法——动态规划。 在多阶段决策过程的每一阶段,都可能有多种可供选择的决策,但必须从中选 取一种决策。一旦各个阶段的决策选定之后,就构成了解决这一问题的一个决策序 列。决策序列不同,所导致的问题的结果也不同。动态规划的目标就是要在所有容 许选择的决策序列中选取一个会获得问题最优解的决策序列,即最优决策序列。 显然,用枚举的方法从所有可能的决策序列中选取最优决策序列是一种最笨拙 的方法。贝尔曼认为,利用最优性原理(Principle of optimality)以及所获得的递 推关系式去求取最优决策序列可以使枚举量急剧下降。这个原理指出,过程的最优 决策序列具有如下性质:无论过程的初始状态和初始决策是什么,其余的决策都必 须相对手初始决策所产生的状态构成一个最优决策序列。如果所求解问题的最优性 原理成立,则说明用动态规划方法有可能解决该问题。而解决问题的关键在于获取 各阶段间的递推关系式 3.答: 分治法的基本思想为: (1) 分解问题为若干子问题; (2) 对子问题求解; (3) 组合各自问题的解。 快速排序过程为: procedure PARTITION(m,p) //在 A(m),A(m+1),?,A(p-1)中的元素按如下方式重新排列: 如果最初 t=A(m),则在重排完成之后,对于 m 和 p-1 之间 的某个 q,有 A(q)=t,并使得对于 m≤k<q,有 A(k)≤t,而 对于 q<k<p,有 A(k)≥t 退出过程时,p 带着划分元素所在的下标位置, 即 q 的值返回。// integer m,p,i; global A(m:p-1) v = A(m); i=m //A(m)是划分元素// 1oop loop i=i+1 until A(i)≥v repeat //i 由左向右移// loop p=p-1 until A(p)≤v repeat //p 由右向左移// if i<p then call INTERCHANGE(A(i),A(p)) //A(i)和 A(p)换位// else exit

endif repeat A(m)=A(p);A(p)=v //划分元素在位置 p// end PARTITION procedure QUICKSORT(p,q) //将全程数组 A(1:n)中的元素 A(p),?,A(q)按递增的方式分类。认为 A(n +1) 已被定义,且大于或等于 A(p:q)的所有元素;即 A(n+1)=+∞// integer p,q;global n,A(1:n) if p<q then j=q+1 call PARTITION(p,j) call QUICKSORT(p,j-1) //j 是划分元素的位置// call QUICKSORT(j+1,q) endif end QUICKSORT 4.答: 贪心法的基本思想为: (1)分析问题,求出最优化评价标准; (2)按评价标准排序; (3)从序列中顺序取元素; (4)若该元素符合要求,则放入结果表中;否则,删除它。 背包算法为: procedure GREEDY-KNAPSACK(P,W,M,X,n) //P(1:n)和 W(1:n)分别含有按 P(i)/W(i) ≥ P(i+1)/W(i+1)排序的 n 件 物品的效益值和重量。M 是背包的容量大小,而 x(1:n)是解向量// real P(1:n),W(1:n),X(1:n),M,cu; integer i,n; X = 0 //将解向量初始化为零// cu = M //cu 是背包剩余容量// for i=1 to n do if W(i)>cu then exit endif Xi = 1 cu = cu-W(i) repeat if i≤n then X(i)= cu/W(i) endif end GREEDY-KNAPSACK 5.答: 动态规划的基本思想为: (1)确定初始条件; (2)计算第一次结果; (3)用上一次的结果计算本次的结果; (4)若递推到了最终结果,则算法结束;否则,转(3) 。 0/1 背包问题的递推公式为:

g( X ) ? max{ g j?1 ( X ), g j?1 ( X ? w j?1 ) ? p j?1}
6.答:

动态规划的基本思想为: (1)确定初始条件; (2)计算第一次结果; (3)用上一次的结果计算本次的结果; (4)若递推到了最终结果,则算法结束;否则,转(3) 。 多段图的递推公式为:

COST (i, j ) ? min {c(i, j ) ? COST (i ? 1, l )}
l?vi ?1 ( j ,l )? E

7.答: 回溯法的基本思想为: (1)分析问题,确定该问题的解空间及显示条件与隐式条件; (2)确定求解问题的状态空间树; (3)对该状态空间树按深度优先方法进行搜索; (4)对搜索的每一步,检查该状态是否为目标状态; (5)若为目标状态,则算法结束; (6)若不满足隐式条件,则回到上一层; (7)选择下一个孩子结点继续搜索;若无下一个孩子可搜索,则回到上一层继续; (8)若回到了最高层的上一层,则无解,算法结束。 子集和数问题的状态空间树为: (x1,x2,x3,x4) :每次所选元素的序列数。
1

x1=1
2

x1=2
3

x1=3
4

x1=4
5

x2=2
6

x2=3 x2=4
7 8

x2=3
9

x2=4
10

x2=4
11

x3=3
12

x3=4
13

x3=4
14

x3=4
15

x4=4
16

8.答: 该结构定义了一个有向图,其逻辑结构图为:

1 2 3 5 6 9.答: 有 5 种可能,结果为:3,2,1 2,3,1 1,2,3 1,3,2 2,1,3 10.答: 解:用向后处理法可得:BCOST(i,j)=min{BCOST(i-1,1)+c(1,j)} 1∈Vi-1 <l,j>∈E 各结点的计算如下: BCOST(3,6)=min{BCOST(2,2)+4,BCOST(2,3)+2}=9 BCOST(3,7)=11 BCOST(3,8)=10 BCOST(4,9)=min{BCOST(3,6)+6,BCOST(3,7)+4}=15 BCOST(4,10)=min{BCOST(3,6)+5,BCOST(3,7)+3,BCOST(3,8)+5}=14 BCOST(4,11)=16 BCOST(5,12)=min{13(30ST(4,9)+4,BCOST(4,10)+2,BCOST(4,11)+5)=16 11. 答: 基本思想: —条边一条边地构造这棵树。 根据某种量度标准来选择将要计入的 下一条边。 最简单的量度标准是选择使得迄今为止所计入的那些边的成本的和有最 小增量的那条边。有两种可能,的方法来解释这一量度标准,第一种方法使得迄今 所选择的边的集合 A 构成一棵树, 将要计人到 A 中的下一条边(u, v)是一条不在 A 中且使得 A∪{(u,v)}也是一棵树的最小成本的边。 12. 答: 不论初始状态和初始决策如何,其余的决策必须按照第一个决策所造成的状 态构成最优策略 13. 答: 最优解为 1→3→4→2→5→1 总费用为 19 单位。 4

更多课程资料请到大学课程网 www.0206.cc 学习


更多相关文档:

算法设计与分析考试题及答案

算法设计与分析考试题及答案_理学_高等教育_教育专区。觉得蛮好 1.一个算法就是一个有穷规则的集合, 其中之规则规定了解决某一特 殊类型问题的一系列运算,此外...

算法设计与分析复习题目及答案

算法设计与分析复习题目答案_IT认证_资格考试/认证_教育专区。一。选择题 1、二分搜索算法是利用( A、分治策略 B、动态规划法 A )实现的算法。 C、贪心法 ...

算法设计与分析复习题目及答案

算法设计与分析复习题目答案_工学_高等教育_教育专区。山东科技大学 一。选择题 1、二分搜索算法是利用( A、分治策略 B、动态规划法 A )实现的算法。 C、...

算法设计与分析——复习题

算法设计与分析——复习题_工学_高等教育_教育专区 暂无评价|0人阅读|0次下载...(nlogn) 假定序列的每个元素被选为参考元素的可能性相等 A(1)=A(0)=0 2 ...

算法设计与分析考试复习题

算法设计与分析考试复习题_工学_高等教育_教育专区。...《算法设计与分析》复习... 6页 1下载券喜欢...算法分析期末试题答案... 47页 免费 算法设计与...

算法设计与分析复习题目及答案

算法设计与分析复习题目答案_工学_高等教育_教育...六、算法设计题(本题 15 分) 分别用贪心算法、...《算法设计与分析》复习... 6页 1下载券 算法设计...

5.《算法设计与分析》试题库

5.《算法设计与分析》试题库_理学_高等教育_教育...23.请写出 prim 算法的基本思想。 参考答案:1. ...《算法设计与分析》复习... 暂无评价 9页 免费 ...

算法设计与分析试卷及答案

n log 7 8 3 年 学期期末考试 《算法设计与分析》试题 C 答案 3. 划分的...算法设计与分析复习题目... 30页 免费 算法设计与分析试卷(A)及... 6页 ...

算法设计与分析复习题

算法设计与分析复习题_工学_高等教育_教育专区。研究生算法复习题算法...一个问题划分成一系列独立的子问题,分别处理后将结果组合以 得到原问题的答案。...

算法设计与分析复习题最终版

算法设计与分析复习题最终版_信息与通信_工程科技_专业资料。一、填空题: 1、 算法就是一组有穷的___,它们规定了解决某一特定类型问题的一系列运 算。 2、 ...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com