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

《算法设计与分析试题及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、1．按分治策略求解棋盘覆盖问题时，对于如图所示的24×24的特殊棋盘，共需要多少个L型骨牌；并在棋盘上填写L型骨牌的覆盖情况。物品ABCDEFG重量35305060401025价值104030503540302．假设有7个物品，给出重量和价值。若这些物品均不能被分割，且背包容量M＝140，使用回溯方法求解此0-1背包问题。请画出状态空间搜索树。3．假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M＝140，使用贪心算法求解此背包问题。请写出求解策略和求解过程。W（35,30,50,60,40,10,25）p（10,40,3

2、0,50,35,40,30）4．在给出的电路板中，阴影部分是已作了封锁标记的方格，请按照队列式分支限界法在图中确定a到b的最短布线方案，要求布线时只能沿直线或直角进行，在图中标出求得最优解时各方格情况。5．画出字符表的哈夫曼编码对应的二叉树。6．已知，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，画出该问题的解空间树，描述出用优先队列式分支限界法求解时的搜索情况。表示出优先

3、队列、当前扩展结点等的变化情况。8．依据优先队列式分支限界法，求从s点到t点的单源最短路径，画出求得最优解的解空间树。一、假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树（20分）。物品ABCDEFG重量35306050401025价值10403050354030答：按照单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】【状态空间搜索树及其计算过程

4、17分，每个节点1分】a．b.c．d.e.f.g.h.i.j.在Q1处获得该问题的最优解为，背包效益为170。即在背包中装入物品F、B、G、D、A时达到最大效益，为170，重量为150。【结论2分】一、已知，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分】12345610150330405165520102036033024301950301809

5、301770403000186050150060123456101224220222230344404450560因此，最佳乘积序列为（A1A2）（（A3A4）（A5A6）），共执行乘法2010次。【结论2分】二、假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M＝150，如果使用贪心方法求解此背包问题，请回答：（20分）。（1）对各个物品进行排序时，依据的标准都有哪些？（2）使用上述标准分别对7个物品进行排序，并给出利用各个顺序进行贪心求解时获得解。（3）上述解中哪个是最优的？物品ABCDEFG重量35306050401

6、025价值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分】（3）显然使用单位价值作为标准得到的是最优解。【2分】一、对于下图使用Dijkstra算法求由顶点a到其他各个顶点

7、的最短路径。并给出求各个顶点对之间的最短路径的算法思想。（20分）。答：三、用V1表示已经找到最短路径的顶点，V2表示与V1中某个顶点相邻接且不在V1中的顶点；E1表示加入到最短路径中的边，E2为与V1中的顶点相邻接且距离最短的路径。【1分】步骤V1V2E1E21.{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

8、,fe}{eg}7.{a,b,c,d,e,f,g}{h}{ab,bd,dc,df,fe,eg}