算法分析与设计答案2023

第四章测试

1.

贪心算法总能找到可行解，但未必是最优解。

A:对 B:错
答案:A
2.

贪心选择通过一步步选择得到问题的解，每一步的局部最优解都构成全局最优解的一部分。

A:对 B:错 3.

问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。

A:错 B:对 4.

Kruskal算法的贪婪准则是每一次选取不构成环路的最小边。

A:错 B:对 5.

贪心算法基本要素有（   ）和最优子结构性质。

A:重叠子问题性质 B:贪心选择性质 C:分解合并性质 D:独立子问题性质 6.

下面不是证明贪心算法证明方法的有（）。

A:界 B:交换论证 C:领先 D:优化 7.

最小生成树问题可以使用的算法有（ ）

A:Solim B:Kruskal C:Dijkstra D:Prim 8.

区间问题包含()

A:区间覆盖 B:区间调度 C:区间选点 D:区间划分 9.

负权的单源最短路问题可以使用Dijkstra算法求解

A:对 B:错 10.

设C是一个环， f 是C中的最大边，那么最小生成树中肯定包含f。  

A:对 B:错