总结：主要还是新学的算法章节有漏洞，比如贪心、动态规划、回溯，等等。

答案：T

考点：判断贪心算法能否得到最优解。

解法：从最简单的条件开始构造，尝试举反例，举不出一般就证明是对的。注意本题是求最大的profit（价值）总和，并不是求最大的重量，因此背包贪心常见的反例在这里不成立！

背包常见的反例（以重量最大值为目标）：

假设有四个物品，重量分别为2,3,3,5。

答案：F

考点：skew heaps摊还分析。 解法：详见我的ADS期中复习笔记. 不要忽略第二点对light nodes数量减少的影响！

答案：B

考点：主要还是Huffman code/tree没掌握。可以参考PPT上的原案例，注意e的值已经不同了：

答案：B

考点：B+树的性质特征。见我的关于B+树的笔记

题解：B选项中，因为delete后要借了，所以肯定之前是临界值 \lceil M/2 \rceil。C选项，因为是向$w$借，所以肯定还是够借的，不可能是临界值 \lceil M/2 \rceil。 A选项，因为如果只看被删除的元素，可能是会影响一个internal节点；但如果被borrow的节点恰好也在internal节点中，那么也会改变B+树内部结构，使internal节点再增加或减少。

答案：A ？ 考点：【Backtracing】turnpike reconstruction problem

题解：题干的意思是Distant Set数据结构是B+树。因此我们不仅要知道PPT上数组版本的turnpike reconstruction problem时间复杂度计算方式，还要知道哪几步替换为了B+树操作，时间复杂度怎么变。

答案：C 见期中复习笔记

题解：

• 注意是问最优时间！

• 最优时间：

• 如果是最坏时间：

tic-tac-toe使用α-β剪枝的时间复杂度：