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

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

采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为

0.O（n2n）

1.O（nlogn）

2.O（2n）

3.O（n）

优先队列式分支限界法选取扩展结点的原则是

0.先进先出

1.后进先出

2.结点的优先级

3.随机

下面关于NP问题说法正确的是

0.NP问题都是不可能解决的问题

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

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

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

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

0.重叠子问题

1.构造最优解

2.贪心选择性质

3.最优子结构性质

0-1背包问题的回溯算法所需的计算时间为

0.O（n2n）

1.O（nlogn）

2.O（2n）

3.O（n）

用分支限界法设计算法的第二步是

0.针对所给问题，定义问题的解空间（对解进行编码）

1.确定易于搜索的解空间结构（按树或图组织解）

2.以广度优先或以最小耗费（最大收益）优先的方式搜索解空间

3.在搜索过程中用剪枝函数避免无效搜索

分支限界法解旅行售货员问题时，活结点表的组织形式是

0.最小堆

1.最大堆

2.栈

3.数组

实现合并排序利用的算法是

0.分治策略

1.动态规划法

2.贪心法

3.回溯法

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

0.分治策略

1.动态规划法

2.贪心法

3.回溯法

蒙特卡罗算法是以下的哪种

0.分支界限算法

1.概率算法

2.贪心算法

3.回溯算法

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

1.对

2.错

回溯法解旅行售货员问题时的解空间树是子集树

1.对

2.错

动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

1.对

2.错

定义最优解不是动态规划算法基本要素

1.对

2.错

蒙特卡罗算法是随机化算法

1.对

2.错

用分支限界法设计算法的第一步是针对所给问题，定义问题的解空间（对解进行编码）

1.对

2.错

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

1.对

2.错

动态规划法通常以自底向上的方式求解最优解

1.对

2.错

哈夫曼编码的贪心算法所需的计算时间为O（n）

1.对

2.错

能采用贪心算法求最优解的问题，一般具有的重要性质为重叠子问题性质与贪心选择性质

1.对

2.错

回溯法中常见的两类典型的解空间树是子集树和排列树

1.对

2.错

快速排序算法的性能取决于划分的对称性

1.对

2.错

解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是动态规划，需要排序的是回溯法，分支限界法

1.对

2.错

实现大整数的乘法是利用的算法是分治策略

1.对

2.错

拉斯维加斯算法找到的解一定是正解

1.对

2.错