网友您好， 请在下方输入框内输入要搜索的题目：
题目内容
（请给出正确答案）
10、子集和问题：给定n个不同的正整数，已知其和大于c，要求找出一个子集使其和等于c。 该问题除解空间树是子集树的回溯法外，还有解空间树是排列树的回溯算法，思考该问题， 从如下选项中找到关于该算法设计的正确的描述。
A．当解空间树是排列树时， 搜索时，可以将从根结点到当前扩展结点的路径上的数看成是一个子集。
B．剪枝条件:当路径上的数之和＞c时剪枝
C．该算法搜索至排列树的叶子结点（即第n层结点）时， 就找到了一个解。
D．数据预处理，首先必须将n个数按从小到大排序存放于x[1:n]，这样可以提高该算法的搜索效率。
参考答案和解析
当解空间树是排列树时， 搜索时， 可以将从根结点到当前扩展结点的路径上的数看成是一个子集。;剪枝条件 : 当路径上的数之和 ＞c 时剪枝
更多 “10、子集和问题：给定n个不同的正整数，已知其和大于c，要求找出一个子集使其和等于c。 该问题除解空间树是子集树的回溯法外，还有解空间树是排列树的回溯算法，思考该问题， 从如下选项中找到关于该算法设计的正确的描述。A．当解空间树是排列树时， 搜索时，可以将从根结点到当前扩展结点的路径上的数看成是一个子集。B．剪枝条件:当路径上的数之和＞c时剪枝C．该算法搜索至排列树的叶子结点（即第n层结点）时， 就找到了一个解。D．数据预处理，首先必须将n个数按从小到大排序存放于x[1:n]，这样可以提高该算法的搜索效率。” 相关考题
考题
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法，Prim算法从一 个顶点开始，每次从剩余的顶点加入一个顶点，该顶点与当前生成树中的顶占的连边权重 最小，直到得到最小生成树开始，Kruscal算法从权重最小的边开始，每次从不在当前的生成树顶点之间的边中选择权重最小的边加入，直到得到一颗最小生成树，这两个算法都采用了（ ）设计策略，且（ ）。A.分治 B.贪心 C.动态规划 D.回溯 A.若网较稠密，则Prim算法更好 B.两个算法得到的最小生成树是一样的 C.Prim算法比Kruscal算法效率更高 D.Kruscal算法比Prim算法效率更高
考题
【问题 1】（8 分）用回溯法求解此 0-1 背包问题，请填充下面伪代码中（1）～（4）处空缺。回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点已经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND( v,w,k,W )函数，其中 v、w、k 和 W分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该结点无需再扩展。下面给出 0-1背包问题的回溯算法伪代码。函数参数说明如下:W：背包容量；n：物品个数；w：重量数组；v：价值数组；fw：获得最大价值时背包的重量；fp：背包获得的最大价值；X：问题的最优解。变量说明如下：cw：当前的背包重量；cp：当前获得的价值；k：当前考虑的物品编号；Y：当前已获得的部分解。
考题
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法，Prim算法从一个顶点开始，每次从剩余的顶点中加入一个顶点，该顶点与当前的生成树中的顶点的连边权重最小，直到得到一颗最小生成树；Kruscal算法从权重最小的边开始，每次从不在当前的生成树顶点中选择权重最小的边加入，直到得到一颗最小生成树，这两个算法都采用了（64）设计策略，且（65）。
A.分治
B.贪心
C.动态规划
D.回溯
考题
下面关于问题树分析的描述中，哪一个选项是错误的？（）A、问题树是MECE方法的一个重要应用B、问题树分析需按层次以一个中心展开C、问题树分解需完全穷尽问题诊断的所有描述和内容D、问题树可以进行相互关联的网状分析或展开
考题
用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h（n），则回溯法所需的计算空间通常为（）
考题
关于回溯搜索法的介绍，下面（）是不正确描述。A、回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解B、回溯法是一种既带系统性又带有跳跃性的搜索算法C、回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯D、回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径
考题
数据结构里，关于树的概念说法正确的是（）A、树可以为空树B、树的定义具有递归性C、树中若存在根结点，则有且只能有一个。D、树的结点若大于2个，则除了根结点，其余结点分为m个互不相交的子集，每个子集也是一颗树
考题
单选题关于回溯搜索法的介绍，下面（）是不正确描述。A
回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解B
回溯法是一种既带系统性又带有跳跃性的搜索算法C
回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯D
回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径
考题
填空题用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h（n），则回溯法所需的计算空间通常为（）
考题
单选题下面关于问题树分析的描述中，哪一个选项是错误的？（）A
问题树是MECE方法的一个重要应用B
问题树分析需按层次以一个中心展开C
问题树分解需完全穷尽问题诊断的所有描述和内容D
问题树可以进行相互关联的网状分析或展开
考题
多选题数据结构里，关于树的概念说法正确的是（）A树可以为空树B树的定义具有递归性C树中若存在根结点，则有且只能有一个。D树的结点若大于2个，则除了根结点，其余结点分为m个互不相交的子集，每个子集也是一颗树
热门标签
最新试卷