itgle.com

下列关于旅行商（TSP）问题的遍历算法和贪心算法的叙述中，错误的是_____。A．遍历算法和贪心算法求得的解一定相同；贪心算法较快，遍历算法较慢B．遍历算法和贪心算法求得的解一定相同；遍历算法较快，贪心算法较慢C．贪心算法求得近似解，但速度较快；遍历算法求得精确解，速度较慢D．贪心算法求得精确解，但速度较快，遍历算法求得近似解，速度较慢

题目

下列关于旅行商（TSP）问题的遍历算法和贪心算法的叙述中，错误的是_____。

A．遍历算法和贪心算法求得的解一定相同；贪心算法较快，遍历算法较慢

B．遍历算法和贪心算法求得的解一定相同；遍历算法较快，贪心算法较慢

C．贪心算法求得近似解，但速度较快；遍历算法求得精确解，速度较慢

D．贪心算法求得精确解，但速度较快，遍历算法求得近似解，速度较慢

相似考题

1.矩阵连乘问题的算法可由什么设计实现()A.分支界限算法B.动态规划算法C.贪心算法D.回溯算法

2.下列有关图的遍历说法中，不正确的是()A.图的遍历必须用递归实现B.基本遍历算法两种：深度遍历和广度遍历C.有向图和无向图都可以进行遍历操作D.图的遍历算法可以执行在有回路的图上

3.背包问题贪心算法的时间复杂性。

4.以深度优先方式系统搜索问题解的算法称为()A.分支界限算法B.概率算法C.贪心算法D.回溯算法

更多“下列关于旅行商（TSP）问题的遍历算法和贪心算法的叙述中，错误的是_____。”相关问题

  • 第1题：

    若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的( )。

    A．前序遍历算法

    B．层次遍历算法

    C．后序遍历算法

    D．中序遍历算法


    正确答案：D
    解析：在存储结点信息的同时，附加两个分别指向该结点最左孩子和右邻兄弟的指针域，即可得树的孩子兄弟链表表示。这种存储结构的最大优点是：它和二叉树的二叉链表表示完全一样。可利用二叉树的算法来实现对树的操作。其后序遍历对应二叉树的中序遍历；中序遍历对应二叉树的后序遍历；前遍历对应二叉树的前序遍历。

  • 第2题：

    （）是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。


    正确答案:贪心选择性质

  • 第3题：

    对于0－1背包问题和背包问题的解法，下面（）答案解释正确。

    • A、0－1背包问题和背包问题都可用贪心算法求解
    • B、0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解
    • C、0－1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解
    • D、因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解

    正确答案:C

  • 第4题：

    关于算法的下列说法中，错误的是（）。

    • A、算法是解决问题的方法和步骤
    • B、算法的步骤必须是有限的
    • C、算法就是解题的算式
    • D、算法必须是可以实现的

    正确答案:C

  • 第5题：

    蒙特卡罗算法是（）的一种。

    • A、分支界限算法
    • B、概率算法
    • C、贪心算法
    • D、回溯算法

    正确答案:B

  • 第6题：

    一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（）。

    • A、重叠子问题
    • B、最优子结构性质
    • C、贪心选择性质
    • D、定义最优解

    正确答案:B

  • 第7题：

    贪心算法算法的基本要素是（）、（）。


    正确答案:最优子结构；贪心选择

  • 第8题：

    下列选项中关于算法的理解描述错误的是（）。

    • A、算法是程序设计的灵魂
    • B、程序=数据结构+算法
    • C、算法就是解决问题的方法和步骤
    • D、算法是关于数学中数字的运算与计算机处理无关

    正确答案:D

  • 第9题：

    填空题
    问题的（）是该问题可用动态规划算法或贪心算法求解的关键特征。

    正确答案： 最优子结构性质
    解析： 暂无解析

  • 第10题：

    单选题
    矩阵连乘问题的算法可由（）设计实现。
    A

    分支界限算法

    B

    动态规划算法

    C

    贪心算法

    D

    回溯算法


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

  • 第11题：

    单选题
    关于算法下列叙述错误的是（）。
    A

    用自然语言表达算法可能产生二义性

    B

    用流程图表达算法不直观

    C

    解决同一问题的算法可能有多个

    D

    算法就是描述解决问题的一系列的步骤和方法


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

  • 第12题：

    问答题
    请叙述动态规划算法与贪心算法的异同。

    正确答案： 共同点：
    都需要最优子结构性质，
    都用来求有优化问题。
    不同点：
    动态规划：每一步作一个选择—依赖于子问题的解。
    贪心方法：每一步作一个选择—不依赖于子问题的解。
    动态规划方法的条件：子问题的重叠性质。
    可用贪心方法的条件：最优子结构性质；贪心选择性质。
    动态规划：自底向上求解；
    贪心方法：自顶向下求解。
    可用贪心法时，动态规划方法可能不适用；
    可用动态规划方法时，贪心法可能不适用。
    解析： 暂无解析

  • 第13题：

    求最短路径常用的算法有()。

    A.Prim算法和Kruskal算法
    B.深度优先遍历算法和广度优先遍历算法
    C.Dijkstra算法和Floyd算法
    D.拓扑排序算法

    答案：C
    解析：
    A项是最小生成树的算法，B项是图的遍历算法，D项中的回溯法是求解递归过程的一种重要方法。

  • 第14题：

    请叙述动态规划算法与贪心算法的异同。


    正确答案: 共同点：
    都需要最优子结构性质，
    都用来求有优化问题。
    不同点：
    动态规划：每一步作一个选择—依赖于子问题的解。
    贪心方法：每一步作一个选择—不依赖于子问题的解。
    动态规划方法的条件：子问题的重叠性质。
    可用贪心方法的条件：最优子结构性质；贪心选择性质。
    动态规划：自底向上求解；
    贪心方法：自顶向下求解。
    可用贪心法时，动态规划方法可能不适用；
    可用动态规划方法时，贪心法可能不适用。

  • 第15题：

    用贪心算法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间。


    正确答案: 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。
    具体算法可描述如下：
    void Knapsack（int n，float M，float v[]，float w[]，float x[]）
    {Sort（n，v，w）；
    int i；
    for（i=1；i<=n；i++） x[i]=0；
    float c=M；
    for（i=1；i<=n；i++）
    {if（w[i]>c） break；
    x[i]=1；
    c-=w[i]；
    }
    if（i<=n）x[i]=c/w[i]；
    }

  • 第16题：

    问题的（）是该问题可用动态规划算法或贪心算法求解的关键特征。


    正确答案:最优子结构性质

  • 第17题：

    矩阵连乘问题的算法可由（）设计实现。

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

    正确答案:B

  • 第18题：

    （）是贪心算法与动态规划算法的共同点。

    • A、重叠子问题
    • B、构造最优解
    • C、贪心选择性质
    • D、最优子结构性质

    正确答案:D

  • 第19题：

    关于算法下列叙述错误的是（）。

    • A、用自然语言表达算法可能产生二义性
    • B、用流程图表达算法不直观
    • C、解决同一问题的算法可能有多个
    • D、算法就是描述解决问题的一系列的步骤和方法

    正确答案:B

  • 第20题：

    单选题
    一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（）。
    A

    重叠子问题

    B

    最优子结构性质

    C

    贪心选择性质

    D

    定义最优解


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

  • 第21题：

    问答题
    用贪心算法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间。

    正确答案： 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。
    具体算法可描述如下：
    void Knapsack（int n，float M，float v[]，float w[]，float x[]）
    {Sort（n，v，w）；
    int i；
    for（i=1；i<=n；i++） x[i]=0；
    float c=M；
    for（i=1；i<=n；i++）
    {if（w[i]>c） break；
    x[i]=1；
    c-=w[i]；
    }
    if（i<=n）x[i]=c/w[i]；
    }
    解析： 暂无解析

  • 第22题：

    单选题
    下列选项中关于算法的理解描述错误的是（）。
    A

    算法是程序设计的灵魂

    B

    程序=数据结构+算法

    C

    算法就是解决问题的方法和步骤

    D

    算法是关于数学中数字的运算与计算机处理无关


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

  • 第23题：

    单选题
    （）是贪心算法与动态规划算法的共同点。
    A

    重叠子问题

    B

    构造最优解

    C

    贪心选择性质

    D

    最优子结构性质


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

  • 第24题：

    单选题
    关于算法的下列说法中，错误的是（）。
    A

    算法是解决问题的方法和步骤

    B

    算法的步骤必须是有限的

    C

    算法就是解题的算式

    D

    算法必须是可以实现的


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

相关内容