算法分析与设计第五章测试_智慧树知到答案2021年

第五章 回溯法：本章主要讲授回溯法的基本思想，学习如何使用回溯法求解马的遍历问题、N皇后问题、图的m着色问题和0-1背包问题等经典问题，学习求解算法的设计、分析与实现。5.1回溯法基本思想:学习回溯法的定义、应用步骤、剪枝函数、解空间树、关键要素、搜索框架和主要用途。
5.2回溯法之马的遍历问题:学习马的遍历问题的描述以及如何使用回溯法求解该问题，包括算法的设计与实现。
5.3回溯法之N皇后问题:学习N皇后问题的描述以及如何使用回溯法求解该问题，包括算法的设计与实现。
5.4回溯法之图的m着色问题:学习图的m着色问题的描述以及如何使用回溯法求解该问题，包括算法的设计实现和分析。
5.5回溯法之0-1背包问题（上）:学习使用回溯法求解0-1背包问题的算法设计和实现。
5.6回溯法之0-1背包问题（下）:学习使用回溯法求解0-1背包问题的算法改进和分析。

[多选题]回溯法中的剪枝函数包括( )。
静态函数
虚函数
约束函数
递归函数
随机数生成函数
限界函数
答案：约束函数
限界函数
[单选题]回溯法采用的搜索策略是( )。
广度优先搜索
层次搜索
启发式搜索
深度优先搜索[判断题]回溯法的主要用途包括求问题的所有解、求问题的最优解和求问题的任一解。
对
错[多选题]马的遍历问题能否有可行解，与( )有关。
马的初始位置
马的遍历深度
棋盘大小
马的遍历顺序[多选题]在N皇后问题中，需要将棋盘当做一个二维数组来分析，对于该二维数组，以下说法正确的是( )。
对于任意一条左斜线上的两个点，它们的横坐标和纵坐标相减的值相同。
对于任意一条右斜线上的两个点，它们的横坐标和纵坐标相加的值相同。
对于任意一条左斜线上的两个点，它们的横坐标和纵坐标相加的值相同。
对于任意一条右斜线上的两个点，它们的横坐标和纵坐标相减的值相同。[判断题]四皇后问题一共有2个可行解，八皇后问题一共有76个可行解。
错
对[单选题]用m种颜色给n个顶点着色、且使一条边的两个顶点颜色不同，则对应的解空间树是一棵( )。
高为m的m叉树
高为n的m叉树
高为m的n叉树
高为n的n叉树[单选题]任何一张地图只用( )种颜色就能使具有共同边界的国家着上不同的颜色。
4
6
3
2[判断题]使用回溯法求解0-1背包问题时，计算右子树上界的方法是通过贪心策略求得上界，即将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包，此时得到的价值就是右子树中解的上界。
对
错[多选题]关于使用回溯法求解0-1背包问题，以下说法正确的是( )。
使用约束函数剪去不合理的左子树（装该物品）。
使用限界函数剪去得不到更优解的左子树（装该物品）。
使用约束函数剪去不合理的右子树（不装该物品）。
使用限界函数剪去得不到更优解的右子树（不装该物品）。