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

很好的复习资料!

1． 按分治策略求解棋盘覆盖问题时，对于如图所示的24×24的特殊棋盘，共需要多少个L型骨

牌；并在棋盘上填写L型骨牌的覆盖情况。

2． 假设有7个物品，给出重量和价值。若这些物品均不能被分割，且背包容量M＝140，使用回

溯方法求解此0-1背包问题。请画出状态空间搜索树。

3． 假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M

＝140，使用贪心算法求解此背包问题。请写出求解策略和求解过程。 W（35,30,50,60,40,10,25）p（10,40,30,50,35,40,30）

4． 在给出的电路板中，阴影部分是已作了封锁标记的方格，请按照队列式分支限界法在图中确定

a到b的最短布线方案，要求布线时只能沿直线或直角进行，在图中标出求得最优解时各方格情况。

5． 画出字符表的哈夫曼编码对应的二叉树。

6． 已知Ak (aij(k))ri*ri 1，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=8，r5=5，r6=20，r7=6，求

矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序。

7． 给出城市网络图，售货员要从城市1出发，经过所有城市回到城市1，画出该问题的解空间树，

描述出用优先队列式分支限界法求解时的搜索情况。表示出优先队列、当前扩展结点等的变化情况。

8． 依据优先队列式分支限界法，求从s点到t点的单源最短路径，画出求得最优解的解空间树。

一、假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M

＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树（20分）。

答：按照单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】

很好的复习资料!

x5 x6 x7 每个节点1分】

17分，

a．40 40 30 50 35 150 115 190.625 (1,1,1,1,7,0,0)

40

8

b. 40 40 30 50 30 150 115 177.5(1,1,1,1,0,7,0)

60

12

c．40 40 30 50 10 170

60

(1,1,1,1,0,0,1)

4

d. 40 40 30 35 30 150 105 167.5 (1,1,1,0,1,3,0) e. 40 40 50 35 30 150 130 175

60

1

(1,1,0,1,1,,0)

3

4 (1,1,0,1,1,0,)7

f. 40 40 50 35 10 150 130 170.71

35

g. 40 40 50 30 160

(1,1,0,1,0,1,0)

h. 40 40 35 30 10 150 140 146.85 (1,1,0,0,1,1,2)

357i.40 30 50 35 30 150 125 167.5(1,0,1,1,1,5,0) 6012j. 40 30 50 35 30

150 145

157.5(0,1,1,1,1,1,0) 6012

在Q1处获得该问题的最优解为(1,1,1,1,0,0,1)，背包效益为170。即在背包中装入物品F、B、G、D、A时达到最大效益，为170，重量为150。【结论2分】

很好的复习资料!

一、

已知Ak (aij(k))ri*ri 1，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，

求矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序。（要求：给出计算步骤）（20分）

答：使用动态规划算法进行求解。 求解矩阵为：【每个矩阵18分】

因此，最佳乘积序列为（A1A2）（（A3A4）（A5A6）），共执行乘法2010次。【结论2分】 二、

假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容

量M＝150，如果使用贪心方法求解此背包问题，请回答：（20分）。

（1） 对各个物品进行排序时，依据的标准都有哪些？

（2） 使用上述标准分别对7个物品进行排序，并给出利用各个顺序进行贪心求解时获得解。 （3） 上述解中哪个是最优的？

很好的复习资料!

答：

（1）标准：重量、价值和单位价值。【3分，每个1分】

（2）使用重量从小到大：FGBAEDC。得到贪心解为：FGBAE全部放入，而D放入20%，得到价值为165。【5分】

使用价值从大到小：DFBEGCA，得到贪心解为：DFBE全部放入，而G放入80%，得到价值为：189。【5分】

使用单位价值从大到小：FBGDECA，得到贪心解为：FBGD全部放入，而E放入87.5%，得到价值为190.625。【5分】

（3）显然使用单位价值作为标准得到的是最优解。【2分】 三、

对于下图使用Dijkstra算法求由顶点a到其他各个顶点的最短路径。并给出求各个顶点对

之间的最短路径的算法思想。（20分）。

答：三、用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分】