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

按分治策略求解棋盘覆盖问题时，对于如图所示的 24×24 的特殊棋盘，共需要多少个 L 型骨牌；并在棋盘上填写L 型骨牌的覆盖情况。 假设有 7 个物品，给出重量和价值。若这些物品均不能被分割，且背包容量M＝140，使用回溯方法求解此 0-1 背包问题。请画出状态空间有哪些信誉好的足球投注网站树。 假设有 7 个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M ＝140，使用贪心算法求解此背包问题。请写出求解策略和求解过程。 W（35,30,50,60,40,10,25）p（10,40,30,50,35,40,30） 在给出的电路板中，阴影部分是已作了封锁标记的方格，请按照队列式分支限界法在图中确定 a 到 b 的最短布线方案，要求布线时只能沿直线或直角进行，在图中标出求得最优解时各方格情况。 画出字符表的哈夫曼编码对应的二叉树。 已知 A ? (a ( k ) ) ，k=1，2，3，4，5，6，r =5，r =10，r =3，r =8，r =5，r =20，r =6，求 k ij r *r 1 2 3 4 5 6 7 i i?1 A A A A A A A A A A A A 1 2 3 4 5 6 给出城市网络图，售货员要从城市 1 出发，经过所有城市回到城市 1，画出该问题的解空间树， 描述出用优先队列式分支限界法求解时的有哪些信誉好的足球投注网站情况。表示出优先队列、当前扩展结点等的变化 情况。 依据优先队列式分支限界法，求从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 分】 x ? 1 3 a  x ? 1 2 a x ? 1 1 a x ? 0 2 a x ? 0 1 j i x ? 1 4 a  x ? 0 4 x ? 0 3 d e x ? 1 x ? 0 5 b x ? 0 6 c  x ? 1 5 e 4 e x ? 0 5 x ? 0 4 h g x ? 0 7 Q 1 x ? 0 6 f  【状态空间有哪些信誉好的足球投注网站树及其计算过程 17 分， 每个节点 1 分】 a． 40 ? 40 ? 30 ? 50 ? 35? 150 ?115 ? 190.625 40  7 (1,1,1,1, 8  ,0,0) b. 40 ? 40 ? 30 ? 50 ? 30 ? 150 ?115 ? 177.5 60 (1,1,1,1,0, 7  ,0) c． 40 ? 40 ? 30 ? 50 ?10 ? 170 12 (1,1,1,1,0,0,1) d. 40 ? 40 ? 30 ? 35 ? 30 ? 150 ?105 ? 167.5 60 e. 40 ? 40 ? 50 ? 35 ? 30 ? 150 ?130 ? 175 3 (1,1,1,0,1, 4 1  ,0) 60 f. 40 ? 40 ? 50 ? 35 ? 10 ? 150 ? 130 ? 170.71 35 (1,1,0,1,1, ,0) 3 4 (1,1,0,1,1,0, ) 7 g. 40 ? 40 ? 50 ? 30 ? 160 (1,1,0,1,0,1,0) h. 40 ? 40 ? 35 ? 30 ?10 ? 150 ?140 ? 146.85 35 (1,1,0,0,1,1,2) i. 40 ? 30 ? 50 ? 35 ? 30 ? 150 ?125 ? 167.5 60  (1,0,1,1,1, 5 7 ,0) j. 40 ? 30 ? 50 ? 35 ? 30 ? 150 ?145 ? 157.5 60 12 (0,1,1,1,1, 1  ,0) 12 在 Q1 处获得该问题的最优解为(1,1,1,1,0,0,1) ，背包效益为 170。即在背包中装入物品F、B、G、D、A 时达到最大效益，为 170，重量为 150。【结论 2 分】 一、 已知 A ? (a ( k ) ) ，k=1，2，3，4，5，6，r =5，r =10，r =3，r =12，r =5，r =50，r =6， k ij r *r 1 2 3 4 5 6 7 i i?1 求矩阵链积A1×A2×A3×A4×A5×A6 的最佳求积顺序。（要求：给出