如果解空间树中，从根结点到叶结点的最长路径的长度为h（n)，则回溯法所需的计算空间通常为O（h（n))。显式地存储整个解空间则需要O（2^h（n))或O（h（n)!)内存空间。

题目

如果解空间树中，从根结点到叶结点的最长路径的长度为h（n)，则回溯法所需的计算空间通常为O（h（n))。显式地存储整个解空间则需要O（2^h（n))或O（h（n)!)内存空间。

相似考题

1.对n个记录的文件进行归并排序，所需要的辅助存储空间为A．O（1）B．O（n）C．O（log2n）D．O（n2）

2.在对n个元素的序列进行排序时,堆排序所需要的附加存储空间是()A、O(log2n)B、O(1)C、O(n)D、O(nlog2n)

3.设平衡的二叉排序树(AVL树)的结点个数为n，则其平均检索长度为A．O(1)B．O(10g2n)C．O(n)D．O(nlog2n)

4.（15）对 n 个记录的文件进行起泡排序，所需要的辅助存储空间为A）O(1)B）O(log2n)C）O(n)D）O(n2)

更多“如果解空间树中，从根结点到叶结点的最长路径的长度为h（n)，则回溯法所需的计算空间通常为O（h（n))。显式地存储整个解空间则需要O（2^h（n))或O（h（n)!)内存空间。”相关问题

  • 第1题：

    n个记录的文件进行快速排序，所需要的辅助存储空间为( )。

    A．O(1)

    B．O(log2n)

    C．O(n)

    D．O(n2)


    正确答案：B
    解析：快速排序的思想是不断对待排序的元素按指定的元素进行划分，然后对两部分再进行划分……。在划分过程中，用到递归算法，其递归算法平均深度为约为 log2n，所以其空间复杂度为O(log2n)。

  • 第2题：

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

    A．O(1)

    B．O(log2n)

    C．O(n)

    D．O(n log2n)


    正确答案：B
    解析：平衡二叉树又称AVL树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1，若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。因为AVL树上任何结点韵左右子树的深度之差都不超过1，则可以证明它的深度和log2n是同数量级的(N为结点个数)。因此，它的平均查找长度也和log2n同数量级。

  • 第3题：

    设平衡的二叉排序树(AVL树）的结点个数为n,则其平均检索长度为

    A．O

    B．O(log2n)

    C．O(n)

    D．O(nlog2n)


    正确答案：B
    解析：平衡二叉树又称AVL树,它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1,若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度,则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。因为AVL树上任何结点的左右子树的深度之差都不超过1,则可以证明它的深度和log2n是同数量级的(N为结点个数）。因此,它的平均查找长度也和log2n同数量级。

  • 第4题：

    设二叉排序树中有n个结点，则二叉排序树的平均查找长度为()。

    A.O(1)

    B.O(log2n)

    C.O(n)

    D.(n2)


    正确答案：B

  • 第5题：

    对n个记录的文件进行起泡排序，所需要的辅助存储空间为

    A．O(1)

    B．O(log2n)

    C．O(n)

    D．O(n2)


    正确答案：A
    解析：本题考查起泡排序的概念。起泡排序是将排序的记录顺次两两比较，若为逆序则进行交换。不管对多少个记录的文件进行起泡排序，所需要的辅助存储空间都为 O(1)。正确答案为选项A。

  • 第6题：

    对n个记录的文件进行归并排序，所需要的辅助存储空间为_______。

    A．O(1)

    B．0(n)

    C．O(1og2n)

    D．0(n2)


    正确答案：B
    解析：对n个记录的文件进行归并排序，所需要的辅助存储空间为O(n)，因为归并排序的实现过程需要用两个包含n个记录的数组，每趟归并需将所有记录从一个数组移至另一数组中。

  • 第7题：

    对n个记录的文件进行归并排序,所需要的辅助存储空间为

    A．O

    B．O(n)

    C．O(log2n)

    D．O(n2)


    正确答案：B
    解析：对n个记录的文件进行归并排序,所需要的辅助存储空间为O(n)。A)选项为起泡排序、简单选择排序、插入排序所需要的辅助存储空间。

  • 第8题：

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


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

  • 第9题：

    设串长为n，模式串长为m，则KMP算法所需的附加空间为（）。

    • A、O（m）
    • B、O（n）
    • C、O（m*n）
    • D、O（nlog2m）

    正确答案:A

  • 第10题：

    以下关于渐进记号的性质是正确的有：（）

    • A、f（n）=Θ（g（n）），g（n）=Θ（h（n））→f（n）=Θ（h（n））
    • B、f（n）=O（g（n）），g（n）=O（h（n））→h（n）=O（f（n））
    • C、O（f（n））+O（g（n））=O（min{f（n），g（n）}）
    • D、f（n）=O（g（n））→g（n）=O（f（n））

    正确答案:A

  • 第11题：

    单选题
    蛋白质的基本组成元素是（　　）。
    A

    C、H、O、N、S

    B

    C、H、O、N、F

    C

    C、H、O、N、P

    D

    C、H、O、N、S、Na

    E

    C、H、O、N、S、Zn


    正确答案： B
    解析：
    蛋白质主要由碳、氢、氧、氮、硫等元素组成，蛋白质元素组成的一个重要特点就是各种蛋白质中含氮量比较接近，平均为16%，生物组织中含氮物以蛋白质为主，因此通过测定生物样品中氮的含量可计算出样品中蛋白质的大致含量。

  • 第12题：

    单选题
    以下关于渐进记号的性质是正确的有：（）
    A

    f（n）=Θ（g（n）），g（n）=Θ（h（n））→f（n）=Θ（h（n））

    B

    f（n）=O（g（n）），g（n）=O（h（n））→h（n）=O（f（n））

    C

    O（f（n））+O（g（n））=O（min{f（n），g（n）}）

    D

    f（n）=O（g（n））→g（n）=O（f（n））


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

  • 第13题：

    生物体中含量最高的四种元素为()

    A、O,C,N,P

    B、O,C,H,P

    C、C,H,N,P

    D、O,C,H,N


    参考答案D

  • 第14题：

    对n个记录的文件进行起泡排序，所需要的输助存储空间为( )。

    A．O(1)

    B．O(1og2n)

    C．O(n)

    D．O(n2)


    正确答案：A
    解析：下表给出了主要排序方法的性能比较：

    根据上表，对n个记录的文件进行起泡排序，所需要的辅助存储空间为O(1)。

  • 第15题：

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

    A．O(1)

    B．O(log2n)

    C．O(n)

    D．O(nlog2n)


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

  • 第16题：

    设平衡的二叉排序树(AVL树)的结点个数为n，则其平均查找长度的数量级为________。

    A．O(1)

    B．O(log2n)

    C．O(n)

    D．O(nlog2n)


    正确答案：B
    解析：平衡二叉树又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。因为AVL树上任何结点的左右子树的深度之差都不超过1，则可以证明它的深度和logN是同数量级的(N为结点个数)。由此，它的平均查找长度也和logN同数量级。

  • 第17题：

    对n个记录的文件进行归并排序，所需要的辅助存储空间为

    A．O(1)

    B．O(n)

    C．O(log2n)

    D．0(n2)


    正确答案：B
    解析：对n个记录的文件进行归并排序，所需要的辅助存储空间为O(n)，因为归并排序的实现过程需要两个包含n个记录的数组，每趟归并需将所有记录从一个数组移到另一数组中。本题的答案为B。

  • 第18题：

    对n个记录的序列进行快速排序，所需的辅助存储空间为( )。

    A．O(1)

    B．O(log2n)

    C．O(n)

    D．O(n2)


    正确答案：B
    解析：快速排序对待排序序列的划分大约为log2n次，而快速排序是通过递归算法来完成的，递归深度大约为log2n，因此所需的辅助存储空间为O(log2n)。

  • 第19题：

    对n个记录的文件进行快速排序，所需要的辅助存储空间为（ ）。

    A）O(nlog2n)

    B）O(n)

    C）O(1og2n)

    D）O(n2)


    正确答案：A

  • 第20题：

    设有以下三个函数：f（n）=2In4+n2+1000，g（n）=15n4+500n3，h（n）=500n3.5+nlogn请判断以下断言正确与否： （1）f（n）是O（g（n）） （2）h（n）是O（f（n）） （3）g（n）是O（h（n）） （4）h（n）是O（n3.5） （5）h（n）是O（nlogn）


    正确答案: （1）对
    （2）错
    （3）错
    （4）对
    （5）错

  • 第21题：

    对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（）。

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

    正确答案:C

  • 第22题：

    H2C2O4·2H2O和KHC2O4·H2C2O4·2H2O两种物质分别和NaOH作用时，△n（H2C2O4·2H2O）：△n（NaOH）=（）；△n（NaOH）：△n（KHC2O4·H2C2O4·2H2O）=（）。


    正确答案:1:2；3:1

  • 第23题：

    问答题
    设有以下三个函数：f（n）=2In4+n2+1000，g（n）=15n4+500n3，h（n）=500n3.5+nlogn请判断以下断言正确与否： （1）f（n）是O（g（n）） （2）h（n）是O（f（n）） （3）g（n）是O（h（n）） （4）h（n）是O（n3.5） （5）h（n）是O（nlogn）

    正确答案： （1）对
    （2）错
    （3）错
    （4）对
    （5）错
    解析： 暂无解析

  • 第24题：

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

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

相关内容