模拟一#

判断题#

R1-1 F

考点：时间复杂度的表示含义，数量级比较

F

考点：skew heap, merge 操作, amortized cost计算, potential functions记忆

?

【knapsack problem】背包问题

【approximation ratio】近似度；近似比

考点：背包问题，贪心算法，packing rule

T

题解：假设最小情况：由于AVL的子树还是AVL，所以我们可以作图递推前几个，发现$f_n = f_{n-2} + f_{n-1} + 1$，所以最少是33个。显然还可以再加2个变成35，题干正确。

T

考点：Divide && Conquer公式记忆（多种方法？条件？）

解析：主方法形式三失效了。但是题干假设我们已知时间复杂度，符合代换法”先猜后证“条件，用代换法证明。

T

考点：leftest heap定义，merge操作（时间复杂度？） ?

NP没学

单选题#

【balanced binary tree parallel algorithm】

考点：并行计算，求前缀和

D

考点：binomial queues, deleteMin操作

D

考点：【贪心】任务排序问题

分析：这类题型的关键能力是构造反例。

如何构造：

• 从简构造，比如只有两个任务（最少）的情况
• 根据题干写约束条件，列方程求解，得反例（？……TBC）

题解：感谢@Xecades 大佬贡献的D选项证明！如下： B、C选项容易构造出反例。如：d1=5，t1=3，d2=2，t2=1

A

考点：(倒排索引) precision && recall 计算

？

【binary counter】

考点：二项式堆的势能函数，摊还分析

考点：对分治法conqure和merge代价的式子理解

A

考点：binomial queues的数组表示？

考点：【动规/贪心】背包问题（考的蛮多的感觉）

考点：NP没学

D

考点：skew heap，merge操作

D

考点：skew heap，merge操作

A

考点：Divide && Conquer公式记忆

D

考点：splay tree的find操作（带基本spaly操作）

A？

考点：不会做

B

考点：B+树（B+树的定义好多有分歧，见我的平板笔记