22秋《算法与数据分析》作业_3

22秋《算法与数据分析》作业_3

在下列算法中有时找不到问题解的是

0.蒙特卡罗算法

1.拉斯维加斯算法

2.舍伍德算法

3.数值概率算法

实现最大子段和利用的算法是

0.分治策略

1.动态规划法

2.贪心法

3.回溯法

以深度优先方式系统搜索问题解的算法称为

0.分支界限算法

1.概率算法

2.贪心算法

3.回溯算法

下面问题哪个不能使用贪心法解决

0.单源最短路径问题

1.N皇后问题

2.最小花费生成树问题

3.背包问题

下列不是动态规划算法基本步骤的是

0.找出最优解的性质

1.构造最优解

2.算出最优解

3.定义最优解

合并排序算法是利用

0.分治策略

1.动态规划法

2.贪心法

3.回溯法

最长公共子序列算法利用的算法是

0.分支界限法

1.动态规划法

2.贪心法

3.回溯法

广度优先是什么的一种搜索方式

0.分支界限法

1.动态规划法

2.贪心法

3.回溯法

下面是贪心算法的基本要素的是

0.重叠子问题

1.构造最优解

2.贪心选择性质

3.定义最优解

下列算法中不能解决0/1背包问题的是

0.贪心法

1.动态规划

2.回溯法

3.分支限界法

P类问题包含在NP类问题中

1.对

2.错

解决0/1背包问题只可以使用动态规划和分支限界法

1.对

2.错

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

1.对

2.错

分支界限法是采用深度优先策略搜索的算法

1.对

2.错

最小耗费优先是分支界限法搜索方式

1.对

2.错

任何可用计算机求解的问题所需的时间都与其规模无关。

1.对

2.错

矩阵连乘问题的算法可由动态规划设计实现

1.对

2.错

以深度优先方式系统搜索问题解的算法称为回溯法。

1.对

2.错

用回溯法解0/1背包问题时，该问题的解空间结构为父集树结构

1.对

2.错

该问题的规模缩小到一定的程度就可以容易地解决符合分治法特征

1.对

2.错

分支限界法是一种只带有系统性搜索算法

1.对

2.错

常见的两种分支限界法为队列式（FIFO）分支限界法与堆栈式分支限界法

1.对

2.错

NP完全问题是P类问题的子集

1.对

2.错

背包问题的贪心算法所需的计算时间为O（nlogn）

1.对

2.错

计算一个算法时间复杂度通常可以计算循环次数、基本操作的频率或计算步。

1.对

2.错