很好的复习资料!
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分】
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库算法设计与分析试题及答案在线全文阅读。
相关推荐：