算法分析与设计 第八次理论作业
一. 单选题（共1题，10分）
-
(单选题, 10分) 关于装载问题，以下叙述不正确的是（）。
A. 装载问题是一个特殊的背包问题
B. 装载问题是一个特殊的0-1背包问题
C. 装载问题可以用回溯法求解
D. 装载问题可以用动态规划法求解正确答案: A:装载问题是一个特殊的背包问题;
二. 填空题（共3题，30分）
-
(填空题, 10分) N皇后问题的解空间树为____。
正确答案： (1) m叉树
-
(填空题, 10分) 用回溯法解图的m着色问题时，使用下面的ok 函数检查当前扩展结点的每一个儿子的可行性。请在空格处填上适当的逻辑值：
private static boolean ok(int k) { //检查颜色可用性 for(int j=1;j<=n;j++) if(a[k][j]&&(x[j]==x[k])) return ____; return ____; }正确答案： (1) false(2) true
-
(填空题, 10分) 根据本课程的学习内容，列举出两种可以用回溯法解决的问题：____和 ____。
正确答案： (1)（装载问题、批处理祖业调度、符号三角形问题、n后问题、0-1背包问题、最大团问题、图的m着色问题、旅行售货员问题、圆排列问题、电路板排列问题、连续邮资问题）
(2)（装载问题、批处理祖业调度、符号三角形问题、n后问题、0-1背包问题、最大团问题、图的m着色问题、旅行售货员问题、圆排列问题、电路板排列问题、连续邮资问题）
三. 判断题（共3题，30分）
-
(判断题, 10分) 用回溯法解题时常遇到的两类典型的解空间树是子集树与排列树。
A. 对
B. 错正确答案: 对
-
(判断题, 10分) 在图的m着色问题中，每条边的两个端点可以着相同的颜色。
A. 对
B. 错正确答案: 错
-
(判断题, 10分) 如果每个信封上最多只允许贴m张邮票，则对应的连续邮资问题的解空间树是一棵完全m叉树。
A. 对
B. 错正确答案: 错
四. 简答题（共1题，30分）
-
(简答题, 30分) 简述回溯法求解问题的一般步骤。
正确答案： 【参考答案】
回溯法解题通常包含3个步骤：
（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。