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

1、1 .按分治策略求解棋盘覆盖问题时，对于如图所示的24X 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. 在给出的电路板中，阴影部分是已作了封锁标记的方格，请按照队列式分支限

2、界法在图中确定a到b的最短布线方案，要求布线时只能沿直线或直角进行，在图中标出求得最优解时各方格 情况。5. 画出字符表的哈夫曼编码对应的二叉树。6. 已知 A(aij(k)ri*ri 1, k=1,2,3, 4,5,6,r1=5,r2=10,3=3,r4=8,r5=5,r6=20,7=6,求矩阵链积A1X A2 X A3X A4X A5X A6的最佳求积顺序。7. 给出城市网络图，售货员要从城市1出发，经过所有城市回到城市 1，画出该问题的解空间树，描述出用优先队列式分支限界法求解时的搜索情况。表示出优先队列、当前扩展结点等的变化情况。8. 依据优先队列式分支限界法，求从s点到t点的单源最短

3、路径，画出求得最优解的解空间树。一、假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M=150,使用回溯方法求解此背包问题。请写出状态空间搜索树(20分)。物品ABCDEFG重量35306050401025价值10403050354030答：按照单位效益从大到小依次排列这 7个物品为：FBGDECA。将它们的序号分别记为 17。 则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】x5X7X6【状态空间搜索树及其计算过程17分,已知 A(aij(k)ri*ri,，k=1，2，3，4，5，6，r1=5，r2=10，3=3，4=12,

4、r5=5, r6=50，7=6,每个节点1分】a.40403050354040305030404030501040403035304040503530 -40150 115b.60c.150 105d.60150 130e.404050170150115190.625 (1,1,1,1,7,0,0)8wm1,1,1,1,0,®(1,1,1,1,0,0,1)167.5(1,1,1,0,1,3,0)4f.g.40h.40601751(1,1,0,1,13,0)335 10竺旦35170.71(1,1,0,1,1,0,y)40 50 30 16040 35 30 10 150 140351

5、46.85(1,1,0,1,0,1,0)(1,1,0,0,1,1,2)150 125ui. 40 30 50 35 30-167.5 (1 0 1 1 1-5 0)''''12，60150 145“j. 40 30 50 35 30 157.5(0, 1,1,1, 1 丄,0)1260在Q1处获得该问题的最优解为(1,1,1,1,0,0,1)，背包效益为170。即在背包中装入物品F、B、G、D、A时达到最大效益，为 170，重量为150。【结论2分】求矩阵链积 AiX A2X A3X A4X A5X A6的最佳求积顺序。(要求：给出计算步骤)(20分) 答：使用

6、动态规划算法进行求解。 求解矩阵为：【每个矩阵18分】12345610150330405165520102036033024301950301809301770403000186050150060123456101224220222230344404450560因此，最佳乘积序列为(A1A2) (A3A4)( A5A6),共执行乘法2010次。【结论2分】二、 假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M = 150,如果使用贪心方法求解此背包问题，请回答：(20分)。(1) 对各个物品进行排序时，依据的标准都有哪些？(2) 使用上述标准分别对 7个物品进行

7、排序，并给出利用各个顺序进行贪心求解时获得解。(3) 上述解中哪个是最优的？物品ABCDEFG重量35306050401025价值10403050354030答：(1) 标准：重量、价值和单位价值。【3分，每个1分】(2) 使用重量从小到大：FGBAEDC。得到贪心解为：FGBAE全部放入，而 D放入20%，得到价值为165。【5分】使用价值从大到小：DFBEGCA，得到贪心解为：DFBE全部放入，而 G放入80%，得到价值为：189。【5分】使用单位价值从大到小：FBGDECA，得到贪心解为：FBGD全部放入，而 E放入87.5%，得到价值为190.625。【5分】对于下图使用Dijkstr

8、a算法求由顶点a到其他各个顶点的最短路径。并给出求各个顶点对(3)显然使用单位价值作为标准得到的是最优解。【2分】之间的最短路径的算法思想。(20分)。E1表示加入到最短路径中的边，E2为与V1中的顶点相邻接且距离最短的路径。【1分】步骤V1V2E1E21.abab2.a,bdabbd3.a,b,dc,fab,bddc,df4.a,b,d,cfab,bddf5.a,b,c,d,feab,bd,dc,dffe6.a,b,c,d,e,fgab,bd,dc,df,feeg7.a,b,c,d,e,f,ghab,bd,dc,df,fe,eggh8.a,b,c,d,e,f,g,h ab,bd,de,df,fe,eg,gh【以上每步2分】结果:从a到h的最短路径为a b d f eg h，权值为18。【1分】