当前位置:首页 >> 政史地 >>

算法复习提纲


简答题(5*4) 基本概念。如: 动态规划的目标是 决策序列 。 在所有容许选择的决策序列中选取一个会获得问题最优解的 。

二、请给出 Kruskal 最小生成树算法的概要描述,给出算法的计算时间,并模拟该算法画出 下图的最小生成树。

Kruskal 最小生成树的概要描述: T? ? while T 的边少于 n-1 条 do 从 E

中选取一条最小成本的边(v,w) 从 E 中删去(v,w) if (v,w)在 T 中不生成环 then 将(v,w)加到 T else 舍弃(v,w)
第1 / 9页

endif repeat

当且仅当图 G 是不连通的,i≠n-1;此算法的计算时间是О (eloge)

最小生成树:

二、请给出 Prim 最小生成树算法,并分析算法的计算时间,最后模拟该算法画出下图的最小 生成树。

第2 / 9页

Prim 最小生成树算法 procedure PRIM(E,COST,n,T,mincost) //E 是 G 的边集。COST(n,n)是 n 结点图 G 的成本邻接矩阵,矩阵元素 COST(i,j)是一 个正实数,如果不存在边(i,j),则为+∞。计算一棵最小生成树并把它作为一个集合存放到 数组 T(1:n-1,2)中(T(i,1),T(i,2))是最小成本生成树的一条边。最小成本生成树的总成本最后赋 给 mincost// real COST(n,n), mincost integer NEAR(n), n, i, k, l, T(1:n-1,2) (k,l)←具有最小成本的边 mincost←COST(k,l) (T(l,1),T(l,2)) ←(k,l) for i←1 to n do //将 NEAR 置初值// if COST(i,l) < COST(i,k) then NEAR(i)←l else NEAR(i) ←k endif repeat NEAR(k)←NEAR(l)←0 for i←2 to n-1 do //找 T 的其余 n-2 条边// 设 j 是 NEAR(j)≠0 且 COST(j,NEAR(j))最小的下标 (T(i,1),T(i,2))←(j,NEAR(j)) mincost←mincost+COST(j,NEAR(j)) NEAR(j)←0 for k←1 to n do //修改 NEAR// if NEAR(k)≠0 and COST(k,NEAR(k))>COST(k,j) then NEAR(k)←j endif repeat repeat
第3 / 9页

if mincost≥∞ then print(‘no spanning tree’) endif end PRIM

过程 prim 所需要的时间是Θ (n2) 。 最小生成树:

三、1、对下图中给出的树求出先根次序周游序列和中根次序周游序列,并改进中根次序周游 的非递归算法,使得该算法还能统计叶子结点的个数。

第4 / 9页

先根:ABDGHJKECFIM 中根:GDJHKBEACFMI procedure inorder1(T) //使用大小为 m 的栈的一个非递归算法 integer stack(m),i,m,s=0 if T=0 then return endif P?T ; i?0 loop while Lchild(P)≠0 do i?i+1 if i>m then print(‘stack overflow’) stop endif stack(i)?P; p?Lchild(P) repeat loop call visit(P) ifLchild(P)=0 and Rchild(P)=0 s=s+1 endif P?Rchild(P) if P≠0 then exit endif if i=0 then return endif P?stack(i); i?i-1 repeat repeat print(s) end inorder1 2、画出下图的深度(宽度)优先生成树,描述图的深度(宽度)优先检索算法,计算每个结 点的最低深度优先数以及深度优先数,由此判断该图中有哪些关节点。 (共 15 分)

第5 / 9页

6 1

5

4

2

7

3

8

10

9

四、背包问题。 1、已知:n=4,M=28,(p1, p2, p3, p4)=(23,21,14,9),

(w1, w2, w3, w4)=(16,13,10,7),用贪心算法求解该背包问题的最优解(要求过程) ,并改进背
包问题的贪心算法,使得该算法能求出该最优解的效益值。最后证明该策略对 0/1 背包问题 的求解不一定得到最优解。

p1/w1=23/16=1.4375, p2/w2=21/13≈1.6154 p3/w3=14/10=1.4 p4/w4=9/7≈1.2857
第6 / 9页

所以先放入第二个物体,即重量为 13 的物体,因此背包剩余容量为 28-13=15. 其次放入第一个物体,即重量为 16 的物体,因 16>15,故只能放入 15/16。
算法如下: 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,Tp=0; integerI,n X←0 //将解向量初始化为空// cu←M //cu 是背包的剩余容量// for i←1 to n do if W(i) > cu then exit endif X(i) ←1 cu ←cu-W(i) Tp?Tp+P(i) repeat if i≤n then X(i) ←cu/W(i) Tp?Tp+P(i)*X(i) endif print(Tp) end GREEDY-KNAPSACK

若是 0/1 背包,按此策略求解,则放入重量为 13 的物体后,不能再放入重量为 16 的物体, 可得到其效益为 21,若选取放入质量为 13 和 10 的物体,可得效益为 35,故该策略对 0/1 背 包问题的求解不一定得到最优解。

2、 已知: n=7,M=15, p2, ……, p7)=(10,5,15,7,6,18,3), (w1, w2, …… , w7)=(2,3,5,7,1,4,1), (p1, 用贪心算法求解该背包问题的最优解(要求过程) ,并改进背包问题的贪心算法,使得该算法 能求出该最优解的效益值。将以上数据情况的背包问题记为 I。设 FG(I)是物品按 pi 的非 增次序输入时所产生的解,FO(I)是一个最优解。 求 FO(I)/ FG(I)? 3.生成每个 fi 阶跃点的序偶集合 Si。
第7 / 9页

五、请画出 n=10 情况下二分检索的二元比较树(共 10 分) 。

六、求下图中各对顶点间的最短路径长度(要求过程) ,并写出算法。

procedure ALL-PATHS(COST,A,n) //COST(n,n)是 n 结点图的成本邻接矩阵;A(i,j)是结点 vi 到 vj 的最短路 径的成本;COST(i,i)=0,1≤i≤n//
第8 / 9页

integerI,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) //用 COST(i,j)对 A0 赋初值// repeat repeat for k←1 to n do for i←1 to n do for j←1 to n do A (i,j) ← min{A (i,j) ,A (i,k) + A (k,j)} repeat repeat repeat end ALL-PATHS

六、假设一棵二叉树的中根序列为 DCBGEAHFIJK 和后根序列为 DCEGBFHKJIA,请画出该树, 并简要描述求解过程。

七、单源点最短路径。
第9 / 9页


相关文章:
算法复习提纲
算法复习提纲_工学_高等教育_教育专区。期末算法设计提纲复习递归: 定义、递归算法的效率分析(时间的递推式) 蛮力法: 定义: 蛮力法是一种简单直接的解决问题的方...
2015算法复习提纲
2015算法复习提纲_工学_高等教育_教育专区。2015 算法设计与分析复习提纲题型:一、选择(2*8=16 分) 二、填空(2*10=20 分) 三、简答(4 小题,共 17 分)...
2015算法复习提纲
2015算法复习提纲_教育学_高等教育_教育专区。2015 算法设计与分析复习提纲题型:一、选择(2*8=16 分) 二、填空(2*10=20 分) 三、简答(4 小题,共 17 分...
算法复习提纲
算法复习提纲_其它课程_高中教育_教育专区。第一章 1.计算机解决问题的基本过程 分析问题—设计算法—编写程序—程序运行 2.算法及特征、描述算法的方法 (1)算法就...
计算方法复习提纲
数值计算方法复习提纲 第一章 数值计算中的误差分析 1.了解误差及其主要来源,...了解误差(绝对误差、相对误差)和有效数字的概念及其关系; 及其关系 3.掌握算法...
《算法与程序设计》复习提纲
算法与程序设计》复习提纲_其它课程_高中教育_教育专区。算法算法的表示 1.使用计算机解决问题的一般过程 ——分析问题;寻找解决途径和方法;用计算机进行处理 2...
算法复习提纲
算法复习提纲 隐藏>> 简答题(5*4) 基本概念。如: 动态规划的目标是 决策序列 。 在所有容许选择的决策序列中选取一个会获得问题最优解的 。 二、请给出 Kru...
2013算法复习提纲
2013复习提纲 暂无评价 5页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 2013算法复习提纲 隐藏>> 题型:一、选择...
2015数据结构与算法复习提纲
2015数据结构与算法复习提纲_教育学_高等教育_教育专区。数据结构C语言版的复习资料 数据结构复习提纲第 1 章概述 1、 数据结构的定义。 2、 数据结构的分类:如...
算法与程序设计复习提纲(参考)
算法与程序设计模块 会考知识点汇总 (一)计算机解决问题的基本过程 1.计算机解决问题的基本过程 ⑴能用流程图画出计算机解决问题的基本步骤 Q:计算机解决问题的 4 ...
更多相关标签: