itgle.com

10、子集和问题：给定n个不同的正整数，已知其和大于c，要求找出一个子集使其和等于c。 该问题除解空间树是子集树的回溯法外，还有解空间树是排列树的回溯算法，思考该问题， 从如下选项中找到关于该算法设计的正确的描述。A．当解空间树是排列树时， 搜索时，可以将从根结点到当前扩展结点的路径上的数看成是一个子集。B．剪枝条件:当路径上的数之和＞c时剪枝C．该算法搜索至排列树的叶子结点（即第n层结点）时， 就找到了一个解。D．数据预处理，首先必须将n个数按从小到大排序存放于x[1:n]，这样可以提高该算法的搜索效率

题目

10、子集和问题：给定n个不同的正整数，已知其和大于c，要求找出一个子集使其和等于c。 该问题除解空间树是子集树的回溯法外，还有解空间树是排列树的回溯算法，思考该问题， 从如下选项中找到关于该算法设计的正确的描述。

A．当解空间树是排列树时， 搜索时，可以将从根结点到当前扩展结点的路径上的数看成是一个子集。

B．剪枝条件:当路径上的数之和＞c时剪枝

C．该算法搜索至排列树的叶子结点（即第n层结点）时， 就找到了一个解。

D．数据预处理，首先必须将n个数按从小到大排序存放于x[1:n]，这样可以提高该算法的搜索效率。

相似考题

1.分支限界法与回溯法的相同点是()A.求解目标相同B.搜索方式相同C.对扩展结点的扩展方式相同D.都是一种在问题的解空间树T中搜索问题解的算法

2.回溯法中常见的两类典型的解空间树是子集树和排列树。()此题为判断题(对，错)。

3.回溯法在问题的解空间树中,按扩展结点优先策略,从根结点出发搜索解空间树。()此题为判断题(对，错)。

4.回溯法解旅行售货员问题时的解空间树是子集树。()此题为判断题(对，错)。

更多“10、子集和问题：给定n个不同的正整数，已知其和大于c，要求找出一个子集使其和等于c。 该问题除解空间树是子集树的回溯法外，还有解空间树是排列树的回溯算法，思考该问题， 从如下选项中找到关于该算法设计的正确的描述。”相关问题

  • 第1题：

    Prim算法和Kruscal算法都是无向连通网的最小生成树的算法，Prim算法从一 个顶点开始，每次从剩余的顶点加入一个顶点，该顶点与当前生成树中的顶占的连边权重 最小，直到得到最小生成树开始，Kruscal算法从权重最小的边开始，每次从不在当前的生成树顶点之间的边中选择权重最小的边加入，直到得到一颗最小生成树，这两个算法都采用了（ ）设计策略，且（ ）。

    A.分治 B.贪心 C.动态规划 D.回溯 A.若网较稠密，则Prim算法更好 B.两个算法得到的最小生成树是一样的 C.Prim算法比Kruscal算法效率更高 D.Kruscal算法比Prim算法效率更高


    正确答案：B,A

  • 第2题：

    Prim算法和Kruscal算法都是无向连通网的最小生成树的算法，Prim算法从一个顶点开始，每次从剩余的顶点中加入一个顶点，该顶点与当前的生成树中的顶点的连边权重最小，直到得到一颗最小生成树；Kruscal算法从权重最小的边开始，每次从不在当前的生成树顶点中选择权重最小的边加入，直到得到一颗最小生成树，这两个算法都采用了（64）设计策略，且（65）。

    A.分治
    B.贪心
    C.动态规划
    D.回溯

    答案：B
    解析：
    Prim算法和Kruscal算法都是基于贪心算法的应用。Prim算法的时间复杂度为O(n2)，与图中边数无关，该算法适合于稠密图。Kruskal算法的时间复杂度只和边有关系，为O(elog2e)，由于Kruskal算法只与边有关，因此适合求稀疏图的最小生成树。

  • 第3题：

    回溯法中常见的两类典型的解空间树是什么？并简述其定义。


    正确答案: 回溯法中常见的两类典型的解空间树是子集树和排列树。
    当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。这类子集树通常有2n个叶结点，遍历子集树需O（2n）计算时间。
    当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O（n!）计算时间。

  • 第4题：

    下面关于问题树分析的描述中，哪一个选项是错误的？（）

    • A、问题树是MECE方法的一个重要应用
    • B、问题树分析需按层次以一个中心展开
    • C、问题树分解需完全穷尽问题诊断的所有描述和内容
    • D、问题树可以进行相互关联的网状分析或展开

    正确答案:D

  • 第5题：

    用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h（n），则回溯法所需的计算空间通常为（）


    正确答案:O(h(n))

  • 第6题：

    在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（）

    • A、回溯法
    • B、分支限界法
    • C、回溯法和分支限界法
    • D、回溯法求解子集树问题

    正确答案:B

  • 第7题：

    图的m着色问题可用（）法求解，其解空间树中叶子结点个数是（），解空间树中每个内结点的孩子数是（）。


    正确答案:回溯；mn；m

  • 第8题：

    回溯法在问题的解空间树中，按（）策略，从根结点出发搜索解空间树。

    • A、广度优先
    • B、活结点优先
    • C、扩展结点优先
    • D、深度优先

    正确答案:D

  • 第9题：

    单选题
    回溯法在问题的解空间树中，按（）策略，从根结点出发搜索解空间树。
    A

    广度优先

    B

    活结点优先

    C

    扩展结点优先

    D

    深度优先


    正确答案： D
    解析： 暂无解析

  • 第10题：

    单选题
    在对问题的解空间树进行搜索的方法中，一个活结点有多次机会成为活结点的是（）
    A

    回溯法

    B

    分支限界法

    C

    回溯法和分支限界法

    D

    动态规划


    正确答案： B
    解析： 暂无解析

  • 第11题：

    单选题
    回溯法解旅行售货员问题时的解空间树是（）。
    A

    子集树

    B

    排列树

    C

    深度优先生成树

    D

    广度优先生成树


    正确答案： B
    解析： 暂无解析

  • 第12题：

    单选题
    下面关于问题树分析的描述中，哪一个选项是错误的？（）
    A

    问题树是MECE方法的一个重要应用

    B

    问题树分析需按层次以一个中心展开

    C

    问题树分解需完全穷尽问题诊断的所有描述和内容

    D

    问题树可以进行相互关联的网状分析或展开


    正确答案： B
    解析： 暂无解析

  • 第13题：

    【问题 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：当前已获得的部分解。


    正确答案：
    （1）k←1或其等价形式（2）cw←cw+w[k]或其等价形式（3）k←k–1或其等价形式（4）k←k+l或其等价形式

  • 第14题：

    在对问题的解空间树进行搜索的方法中，一个活结点有多次机会成为活结点的是（）

    • A、回溯法
    • B、分支限界法
    • C、回溯法和分支限界法
    • D、动态规划

    正确答案:A

  • 第15题：

    回溯算法和分支限界法的问题的解空间树不会是（）

    • A、有序树
    • B、子集树
    • C、排列树
    • D、无序树

    正确答案:D

  • 第16题：

    回溯法的算法框架按照问题的解空间一般分为（）算法框架与（）算法框架。


    正确答案:子集树；排列树

  • 第17题：

    回溯法解旅行售货员问题时的解空间树是（）。

    • A、子集树
    • B、排列树
    • C、深度优先生成树
    • D、广度优先生成树

    正确答案:B

  • 第18题：

    关于回溯搜索法的介绍，下面（）是不正确描述。

    • A、回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解
    • B、回溯法是一种既带系统性又带有跳跃性的搜索算法
    • C、回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯
    • D、回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径

    正确答案:D

  • 第19题：

    数据结构里，关于树的概念说法正确的是（）

    • A、树可以为空树
    • B、树的定义具有递归性
    • C、树中若存在根结点，则有且只能有一个。
    • D、树的结点若大于2个，则除了根结点，其余结点分为m个互不相交的子集，每个子集也是一颗树

    正确答案:A,B,C,D

  • 第20题：

    单选题
    回溯算法和分支限界法的问题的解空间树不会是（）
    A

    有序树

    B

    子集树

    C

    排列树

    D

    无序树


    正确答案： D
    解析： 暂无解析

  • 第21题：

    单选题
    关于回溯搜索法的介绍，下面（）是不正确描述。
    A

    回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解

    B

    回溯法是一种既带系统性又带有跳跃性的搜索算法

    C

    回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯

    D

    回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径


    正确答案： D
    解析： 暂无解析

  • 第22题：

    单选题
    在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（）
    A

    回溯法

    B

    分支限界法

    C

    回溯法和分支限界法

    D

    回溯法求解子集树问题


    正确答案： D
    解析： 暂无解析

  • 第23题：

    填空题
    用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h（n），则回溯法所需的计算空间通常为（）

    正确答案： O(h(n))
    解析： 暂无解析

  • 第24题：

    多选题
    数据结构里，关于树的概念说法正确的是（）
    A

    树可以为空树

    B

    树的定义具有递归性

    C

    树中若存在根结点，则有且只能有一个。

    D

    树的结点若大于2个，则除了根结点，其余结点分为m个互不相交的子集，每个子集也是一颗树


    正确答案： A,C
    解析： 暂无解析

相关内容