itgle.com

回溯法中，如果解空间树是排列树，所给问题的规模为n时，遍历排列树需 O（n! ) 计算时间.

题目

回溯法中，如果解空间树是排列树，所给问题的规模为n时，遍历排列树需 O（n! ) 计算时间.

相似考题

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

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

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

4.旅行售货员问题的解空间树是排列树结构。()此题为判断题(对，错)。

更多“回溯法中，如果解空间树是排列树，所给问题的规模为n时，遍历排列树需 O（n! ) 计算时间.”相关问题

  • 第1题：

    在具有n个结点的二叉树中，如果各结点值互不相同，但前序遍历序列与中序遍历序列相同，则该二叉树的深度为(根结点在第1层)()。

    A.n

    B.n/2+1

    C.n+1

    D.n-1


    正确答案：A

  • 第2题：

    对n个结点的二叉树进行遍历，错误的说法是( )。

    A．不同遍历方法的时间复杂度一样

    B．用中序遍历的方式时间复杂度为O(n)

    C．后序遍历的空间复杂度为O(n)

    D．遍历的时间复杂度和空间复杂度都为O(n2)


    正确答案：D
    解析：遍历二叉树的算法中的基本操作是访问结点，不论按哪种次序进行遍历，对含n个结点的二叉树，时间复杂度都为O(n)，所需的辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n，则空间复杂度也为O(n)。

  • 第3题：

    以下关于二叉排序树(或二叉查找树、二叉搜索树)的叙述中，正确的是( )

    A.对二叉排序树进行先序、中序和后序遍历，都得到结点关键字的有序序列

    B.含有N个结点的二叉排序树高度为【log2n】+1

    C.从根到任意二个叶子结点的路径上，结点的关键字呈现有序排列的特点

    D.从左到右排列同层次的结点，’其关键字呈现有序排列的特点


    正确答案：D

  • 第4题：

    回溯法搜索状态空间树是按照（）的顺序。

    • A、中序遍历
    • B、广度优先遍历
    • C、深度优先遍历
    • D、层次优先遍历

    正确答案:C

  • 第5题：

    二叉树__（1）__。在完全二叉树中，若一个结点没有__（2）__，则它必定是叶结点。每棵树都能唯一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子树是N在原树里对应结点的__（3）__，而N的右子树是它在原树里对应结点的__（4）__。二叉排序树的平均检索长度为__（5）__。 空白（5）处应选择（）

    • A、O（n2）
    • B、O（n）
    • C、O（log2n）
    • D、O（nlog2n）

    正确答案:C

  • 第6题：

    从二叉搜索树中查找一个元素时，其时间复杂度大致为（）

    • A、O（n）
    • B、O（1）
    • C、O（log2n）
    • D、O（n2）

    正确答案:C

  • 第7题：

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

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

    正确答案:B

  • 第8题：

    对于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂度为O（log2n）。


    正确答案:错误

  • 第9题：

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

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

    正确答案:D

  • 第10题：

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

    广度优先

    B

    活结点优先

    C

    扩展结点优先

    D

    深度优先


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

  • 第11题：

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

    回溯法

    B

    分支限界法

    C

    回溯法和分支限界法

    D

    回溯法求解子集树问题


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

  • 第12题：

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

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

  • 第13题：

    递归式的先序遍历一个n节点，深度为d的二叉树，则需要栈空间的大小为()

    A.O(logn)

    B.O(nlogn)

    C.O(n)

    D.O(d)


    正确答案：D

  • 第14题：

    设平衡的---X排序树(AVL树)的结点个数为n，则其平均检索长度为

    A．O(1)

    B．O(log2n)

    C．O(n)

    D．O(nlog2n)


    正确答案：B
    解析：平衡的二叉排序树是对二叉排序树的一种平衡化处理。结点的平衡因子定义为其右于树高度减去左予树高度，若任意结点的平衡因子均取值-1，或0，或1，则此二叉排序树为平衡的二叉排序树(AVL)。平衡二叉树的检索方法与一般的二叉树完全一样，其优点是总能保持检索长度为O(1og2n)。

  • 第15题：

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

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

    正确答案:A

  • 第16题：

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

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

    正确答案:D

  • 第17题：

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


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

  • 第18题：

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

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

    正确答案:B

  • 第19题：

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


    正确答案:回溯；mn；m

  • 第20题：

    对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（n）。


    正确答案:正确

  • 第21题：

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

    有序树

    B

    子集树

    C

    排列树

    D

    无序树


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

  • 第22题：

    单选题
    某二叉树为单枝树（即非叶子节点只有一个孩子节点）且具有n个节点（n>1）则该二叉树（）。
    A

    共有n层，每层有一个节点

    B

    共有log2n层，相邻两层的节点数正好相差一倍

    C

    先序遍历序列与中序遍历序列相同

    D

    后序遍历序列与中序遍历序列相同


    正确答案： D
    解析： 题考查数据结构中二叉树的基本概念和运算。 若二叉树为单枝树，那么n个节点就分布在n层上。遍历序列则与遍历方法和二叉树的形态有关。例如，对于三个节点的单枝二叉树(A、B、C的层次依次增高)，其形态可为： [*] 考查它们的先序、中序和后序遍历序列，先序遍历序列都为A、B、C，而中序和后序遍历序列则有所不同。

  • 第23题：

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

    子集树

    B

    排列树

    C

    深度优先生成树

    D

    广度优先生成树


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

  • 第24题：

    单选题
    回溯法搜索状态空间树是按照（）的顺序。
    A

    中序遍历

    B

    广度优先遍历

    C

    深度优先遍历

    D

    层次优先遍历


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

相关内容