贪心与分治（共 12 题）

单选题

1. 贪心算法的核心思想是（ ）。
   {{ select(1) }}

• 在每一步选择中都做当前状态下的最优选择
• 在每一步选择中都选择局部最优解
• 在每一步选择中都选择全局最优解
• 以上都对

2. 关于分治算法，以下哪个说法正确？
   {{ select(2) }}

• 分治算法将问题分成子问题，然后分别解决子问题，最后合并结果。
• 归并排序不是分治算法的应用。
• 分治算法通常用于解决小规模问题。
• 分治算法的时间复杂度总是优于 O(n log n)。

3. 下面代码实现了分治求“最大连续子段和”，其时间复杂度为（ ）。

   int solve(vector<int>& a, int l, int r) {
       if (l == r) return a[l];
       int mid = (l+r)/2;
       int left = solve(a, l, mid);
       int right = solve(a, mid+1, r);
       int sum = 0, lmax = INT_MIN;
       for (int i = mid; i >= l; i--) { sum += a[i]; lmax = max(lmax, sum); }
       sum = 0; int rmax = INT_MIN;
       for (int i = mid+1; i <= r; i++) { sum += a[i]; rmax = max(rmax, sum); }
       return max({left, right, lmax+rmax});
   }
   

   {{ select(3) }}

• O(n²)
• O(n log n)
• O(log n)
• O(n)

4. 小杨想编写一个判断任意输入的整数 N 是否为素数的程序，下面哪个方法不合适？（ ）
   {{ select(4) }}

• 埃氏筛法
• 线性筛法
• 二分答案
• 枚举法

5. 小杨在生日聚会时拿一块 H*W 的巧克力招待来的 K 个小朋友，保证每位小朋友至少能获得一块相同大小的巧克力。那么小杨想分出来最大边长的巧克力可以使用（ ）。
   {{ select(5) }}

• 二分法
• 贪心法
• 动态规划
• 枚举法

6. 归并排序的基本思想是（ ）。
   {{ select(6) }}

• 动态规划
• 分治
• 贪心算法
• 回溯算法

7. 小杨设计了一个拆数程序，它能够将任意的非质数自然数 N 转换成若干个质数的乘积，这个程序是可以设计出来的。这体现了（ ）。
   {{ select(7) }}

• 唯一分解定理
• 贪心思想
• 分治思想
• 动态规划

8. 在全国人口普查时，将其分解为对每个省市县乡来进行普查和统计。这是典型的（ ）。
   {{ select(8) }}

• 分治策略
• 贪心策略
• 动态规划
• 回溯策略

9. 下面关于分治算法的说法，正确的是（ ）。
   {{ select(9) }}

• 分治算法通常使用递归实现
• 分治算法一定比普通算法效率高
• 分治算法不能解决大规模问题
• 分治算法只能用于排序问题

10. 小杨有 100 元去超市买东西，每个商品有各自的价格，每种商品只能买 1 个，小杨的目标是买到最多数量的商品。小杨采用的策略是每次挑价格最低的商品买，这体现了（ ）。
    {{ select(10) }}

• 分治思想
• 贪心思想
• 动态规划思想
• 回溯思想

判断题

11. 若一个问题满足最优子结构性质，则一定可以用贪心算法得到最优解。
    {{ select(11) }}

• 正确
• 错误

12. 贪心算法可以达到局部最优，但可能不是全局最优解。
    {{ select(12) }}

• 正确
• 错误