5.1 KiB
C++ 贪心算法（中） 课后习题
姓名: _____________
一、 填空题
- 在“排队接水”问题中，我们的目标是让所有人的平均等待时间最小，这等价于让所有人的______________________之和最小。
- 在“排队接水”问题总等待时间的计算公式中，排在越前面的人，其接水时间所乘的_____________越大。因此，我们的贪心策略是让接水时间_____________的人排在最前面。
- “活动安排”问题的贪心策略是：将所有活动按_____________从小到大排序，然后依次选择与已选活动不冲突的活动。
- “活动安排”问题可以被抽象为更普适的数学模型，叫做“最多_____________区间问题”。
- 在“射气球”或“区间选点”问题中，我们通常将所有区间按_____________从小到大排序。
- 对于部分背包问题(有n个不同价值，不同重量物品可供选择，每个物品可分割，求在一定背包容量下能获取的物品的最大价值)，它的贪心标准是优先选择_____________最高的物品。
- 我们常用_____________来证明一个贪心策略的正确性。
二、 单项选择题
( ) 1. 在“排队接水”问题中，正确的排队策略是什么？ A. 接水时间长的人排在前面 B. 接水时间短的人排在前面 C. 随机排队 D. 按到达顺序排队
( ) 2. 假设有4个人排队接水，他们的接水时间分别是 $t_1, t_2, t_3, t_4$。在总等待时间的计算公式中，哪个人的接水时间被计算的次数最多？
A. 第1个人(t_1) B. 第2个人(t_2) C. 第3个人(t_3) D. 第4个人(t_4)
( ) 3. 有3个人排队接水，时间分别是 2分钟、5分钟、8分钟。要使总等待时间最短，他们的排队顺序应该是？
A. 8, 5, 2 B. 5, 8, 2 C. 2, 5, 8 D. 任意顺序都可以
( ) 4. 在一个大量有时间冲突的活动中，要求选择出数量最多的、互不冲突的活动问题中，正确的贪心策略是？ A. 优先选择开始时间最早的活动 B. 优先选择持续时间最短的活动 C. 优先选择结束时间最早的活动 D. 优先选择开始时间最晚的活动
( ) 5. 在一个大量有时间冲突的活动中，要求选择出数量最多的、互不冲突的活动问题中，采取“结束时间最早”策略的主要理由是？ A. 让每个活动尽快开始 B. 尽快结束当前活动，为未来留下最大的选择空间 C. 确保持续时间长的活动能被安排 D. 避免活动之间有任何空闲时间
( ) 6. 考虑以下活动(开始时间, 结束时间)：A(1, 4), B(3, 5), C(0, 6), D(5, 7)。按照“活动安排”的贪心策略，最多能选出几个活动？ A. 1 B. 2 C. 3 D. 4
( ) 7. 对于射气球问题：在 X 轴上，有一些水平方向的气球。每个气球可以由一个开始和结束坐标去表示，要求用最少的箭射爆所有气球，它的贪心策略是？ A. 按气球宽度从大到小排序 B. 按气球左端点从小到大排序 C. 按气球右端点从小到大排序 D. 随机选择一个气球射击
( ) 8. 现有A, B, C, D四个活动，它们的起止时间分别是A(8, 11), B(9, 12), C(10, 13), D(8, 10)。为了能安排下尽可能多的活动，根据贪心策略，我们应该首先选择哪个活动？ A. 活动A B. 活动B C. 活动C D. 活动D
( ) 9. 部分背包问题，其贪心选择能够成立的关键前提是？ A. 物品价值都很高 B. 物品重量都很轻 C. 物品可以被任意分割 D. 背包容量非常大
( ) 10. 一个问题能用贪心算法求解，通常需要满足最优子结构和什么性质？ A. 无后效性 B. 先进先出 C. 后进先出 D. 运行速度快
三、 判断题 (对的打“√”，错的打“×”)
( ) 1. 在“排队接水”问题中，让接水时间最长的人排在队尾，总等待时间会最短。 ( ) 2. 在“活动安排”问题中，总是优先选择开始时间最早的活动，一定能得到最优解。 ( ) 3. 贪心算法在每一步都做出一个当前看起来最好的选择。 ( ) 4. 在“射气球”问题中，按右端点排序后，第一支箭应该射在第一个气球的右端点位置。 ( ) 5. “部分背包”问题和“0-1背包”问题（物品不能分割）都可以用相同的贪心策略解决。 ( ) 6. 学习贪心算法的关键在于识别问题的内在数学模型，并找到正确的贪心标准。 ( ) 7. 在“排队接水”问题中，即使所有人的接水时间都一样，交换任意两个人的位置，总等待时间也不会改变。 ( ) 8. 在“最多不相交区间问题”中，我们的目标是让选出的所有区间的总长度最长。 ( ) 9. 贪心算法总能为所有问题找到全局最优解。 ( ) 10. “排队接水”和“活动安排”两个问题的贪心策略，第一步都是对输入数据进行排序。