《算法分析与设计》是软件工程专业的学科基础课程，也是学科专业核心课程。本课程主要介绍算法设计与分析的基本方法、实践案例、拓展研究。想了解算法、应用算法和研究算法的同学，欢迎来到我们这门课的课堂，你会大有收获！
西北工业大学算法分析与设计(2023暑假班)练习题答案
开课机构：西北工业大学 教师团队：罗建超 总点击数：
贪心算法
- 贪心法每一步选择采取的是一种____的做法
- 贪心选择的性质通常可以通过归纳法证明，一般通过对算法步数归纳或通过对____归纳来证明…
- 动态规划通常采用自底向上的方式求解各个子问题，而贪心算法通常采用____进行…
- 贪心法对于满足____和最优子结构性质的问题能够保障最优解
- 贪心法对于所有的问题都能保障最优解
- 活动安排问题可以通过早完成的先开始贪心的方式得到问题最优解
- 活动安排问题可以通过占用时间少先开始贪心的方式得到问题最优解
- 活动安排问题可以通过早到早开始贪心的方式得到问题最优解
- 活动安排问题可以通过贪心法得到问题最优解
- Kruskal算法的最坏复杂度是O(elog(e))
- Prim算法的最坏复杂度是O(n^2)
- Prim算法一定比Kruskal算法效率低
- Prim算法一定比Kruskal算法效率高
- 权值最小的边一定在某个最小生成树当中
- 与某个节点相关的权值最小的边一定在某个最小生成树当中
- 最小生成树问题可以用prim和____求解
- 最小生成树问题可以用____和____求解
回溯法
- 使用回溯法时，如果变量不满足多米诺性质，可以通过____和变量替换解决。…
- 回溯法搜索解空间树主要以深度优先搜索方式为主。
- 回溯法避免无效的搜索策略有____和约束函数
- 回溯法总能找到问题的最优解
- 回溯法的基本思想是，当一条路走到尽头时，____一步或若干步，从另外一个状态出发…
- 回溯法也叫____
- 回溯法是问题的通用解法
- 解向量需要满足____和____才能称为解
- 两类典型的解空间树分别为____,____
- 只有满足____性质，才能用回溯法求解
- 回溯法结点的状态有3种分别是白结点____,____
- n皇后问题迭代求解回退到上一行时需要从上次探索的下一个位置开始…
- n皇后问题迭代求解向下探索时需要从下一行的首个位置开始
- n皇后问题的解向量（x1, x2, …,xn）需要满足的显示约有xi = 1,2,…n
- n皇后问题的解向量（x1, x2, …,xn）需要满足以下的隐式约束有 Axi不等于xk B|i-j|不等于|xi-xj| C…
- 判断一个高精度数是否能够被整除可以通过计算高精度的数值保存到大整数变量中然后取余…
- 高精度数可以通过数组保存
- n个城市的货郎担问题的解向量（x1, x2, …,xn）需要满足以下的隐式约束有 Axi到xi+1有边 Bxn到x1有…
- n个城市的货郎担问题的解空间规模是n^(n-1)
- n个城市的货郎担问题的解空间规模是 A（n-1）! Bn^2 Cn^n Dn^(n-1)
- 01背包问题的解空间属于子集树
- 货郎担问题的解空间属于子集树
- 货郎担问题的解空间属于 A子集树 B排列树
- 01背包问题的解空间属于 A子集树 B排列树
分支限界法
- 对于求最大值的优化问题，如果节点v的上界UB(v)小于等于当前最好界cBest，则节点v可以加入黑名单，不再…
- 对于求最大值的优化问题，如果根节点的上界等于下界，则直接结束，输出对应于下界的解即可…
- 对于求最小值的优化问题，如果根节点的上界等于下界，则直接结束，输出对应于上界的解即可…
- 对于求最小值的优化问题，如果节点v的下界LB(v)大于等于当前最好界cBest，则节点v可以加入黑名单，不再…
- 如果所有叶子节点的最小效益值____LB(v)，则LB(v)为节点v的下确界
- 如果所有叶子节点的最小效益值等于LB(v)，则LB(v)为节点v的____
- 下界越大越好
- 上界越大越好
- 如果所有叶子节点的最大效益值____UB(v)，则UB(v)为节点v的上确界
- 最大优先队列采用____实现，最小优先队列采用____实现
- 分支限界算法中常见的两种分支搜索法或选择节点方式为（）。 AFIFO B优先队列式 CFIFO D随机选择…
- 分支限界算法的结束条件是找到所需的解或活节点列表为____。
- 在分支限界法中，每个活结点只有____次机会成为扩展结点（填阿拉伯数字）…
- 分支限界法主要以深度优先的方式搜索解空间树
- 批作业调度问题的结点需要包含的信息有 A下界 B层 C作业调度方案
- 作业调度问题的上界可以用贪心法求得
- 货郎担问题的上界可以用贪心法求得
- 用优先队列实现装载问题，每个活节点必需要记录哪些信息 A上界 B层 C父节点 D是否为左儿子…
- 用FIFO实现不需要给出装载方案的装载问题，每个活节点必需要记录哪些信息 A当前载重 B当前层数 C…
遗传算法
- 遗传算法中解的好坏用____来评价
- 遗传算法要实现全局收敛，必须要有____操作来防止最优解遗失
- 轮盘赌算子的思想是个体被选中的概率与其适应度值大小成____
- 轮盘赌算子又称为____算子，它的思想是个体被选中的概率与其适应度值大小成正比…
- 适应度函数的设计标准是：适应度函数值____，解的质量越好
- 适应度函数的设计标准是：适应度函数值越小，解的质量越好
- 把基因型变成表现型的过程叫____，把表现成变成基因型的过程叫____
- 0到4的闭区间，求解结果精确到6位小数，至少需要____位二进制编码
- 基本遗传算法使用____或者____串进行编码
- 遗传算法的组成包括____、____、遗传算子、运行参数
- 遗传算法得到新解的方式是遗传算子，遗传算子包括____、____和____。
- 遗传算法是借鉴生物界____和____机制的随机化搜索算法