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

算法设计与分析试题及答案 441( 按分治策略求解棋盘覆盖问题时，对于如图所示的2×2的特殊棋盘，共需要多少个L型骨 牌;并在棋盘上填写L型骨牌的覆盖情况。 2( 假设有7个物品，给出重量和价值。若这些物品均不能被分割，且背包容量M,140，使用回A B C D E F G 物品 溯方法求解此0-1背包问题。请画出状态空间搜索树。 35 30 50 60 40 10 25 重量 3( 假设有7个物品，它们的重量和价值如下 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 所示。若这些物品均可以被分割，且背包容量M10 40 30 50 35 40 30 价值 ,140，使用贪心算法求解此背包问题。请写出求解策略和求解过程。 W(35,30,50,60,40,10,25)p(10,40,30,50,35,40,30) 4( 在给出的电路板中，阴影部分是已作了封锁标记的方格，请按照队列式分支限界法在图中确定 a到b的最短布线方案，要求布线时只能沿直线或直角进行，在图中标出求得最优解时各方格 情况。 5( 画出字符表的哈夫曼编码对应的二叉树。 ()kAa,()6( 已知，k=1，2，3，4，5，6，r=5，r=10，r=3，r=8，r=5，r=20，r=6，求1234567kijrr*ii，1 矩阵链积A×A×A×A×A×A的最佳求积顺序。 123456 7( 给出城市网络图，售货员要从城市1出发，经过所有城市回到城市1，画出该问题的解空间树， 描述出用优先队列式分支限界法求解时的搜索情况。表示出优先队列、当前扩展结点等的变化 情况。 8( 依据优先队列式分支限界法，求从s点到t点的单源最短路径，画出求得最优解的解空间树。 一、假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M ,150，使用回溯方法求解此背包问题。请写出状态空间搜索树(20分)。 A B C D E F G 物品 35 30 60 50 40 10 25 重量 10 40 30 50 35 40 30 价值 答:按照单位效益从大到小依次排列这7个物品为:FBGDECA。将它们的序号分别记为1,7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得:【排序1分】 ax,11x,01jx,12ax,02ix,13 ax,03x,14x,04 deax,14x,0x,054 hx,1a5ex,0x,065eg x,06x,07bf 1【状态空间搜索树及其计算过程17分， 每个节点1分】 c150115,7a( 4040305035190.625，，，，，,(1,1,1,1,,0,0)408 150115,7b. 4040305030177.5，，，，，,(1,1,1,1,0,,0)6012Q c( 4040305010170，，，，,(1,1,1,1,0,0,1) 150105,3d. 4040303530167.5，，，，，,(1,1,1,0,1,,0)604 150130,1e. 4040503530175，，，，，,(1,1,0,1,1,,0)603 150130,f. 44040503510170.71，，，，，,(1,1,0,1,1,0,)357 g. 40405030160，，，,(1,1,0,1,0,1,0) 150140,2h. 4040353010146.85，，，，，,(1,1,0,0,1,1,)357 150125,5i. 4030503530167.5，，，，，,(1,0,1,1,1,,0)6012 150145,1j. 4030503530157.5，，，，，,(0,1,1,1,1,,0)6012 (1,1,1,1,0,0,1)在Q处获得该问题的最优解为，背包效益为170。即在背包中装入物品F、B、G、1 D、A时达到最大效益，为170，重量为150。【结论2分】 ()kAa,()一、 已知，k=1，2，3，4，5，6，r=5，r=10，r=3，r=12，r=5，r=50，r=6，1234567kijrr*ii，1 求矩阵链积A×A×A×A×A×A的最佳求积顺序。(要求:给出计算步骤)(20分) 123456 答:使用动态规划算法进行求解。 求解矩阵为:【每个矩阵18分】 1 2 3 4 5 6 1 0 150 330 405 1655 2010 2 0 360 330 2430 1950 3 0 180 930 1770 4 0 3000 1860 5 0 1500 6 0 1 2 3 4 5 6 1 0 1 2 2 4 2 2 0 2 2 2 2 3 0 3 4 4 4 0 4 4 5 0 5 6 0 因此，最佳乘积序列为(AA)((AA)(AA))，共执行乘法2010次。【结论2分】 123456 二、 假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容 量M,150，如果使用贪心方法求解此背包问题，请回答:(20分)。 (1) 对各个物品进行排序时，依据的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 都有哪些, (2) 使用上述标准分别对7个物品进行排序，并给出利用各个顺序进行贪心求解时获得解。 (3) 上述解中哪个是最优的, A B C D E F G 物品 35 30 60 50 40 10 25 重量 10 40 30 50 35 40 30 价值 答: (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分)。 beg2 222 13ad2 431 1cfh 答:三、用V表示已经找到最短路径的顶点，V表示与V中某个顶点相邻接且不在V中的顶点;1211E表示加入到最短路径中的边，E为与V中的顶点相邻接且距离最短的路径。【1分】 121 步骤 V V E E 1212 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分】 abdfegh,,,,,,结果:从a到h的最短路径为，权值为18。【1分】 求所有顶点对之间的最短路径可以使用Dijkstra算法，使其起始节点从a循环到h，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。【2分】