模拟一
判断题
R1-1 F
考点:时间复杂度的表示含义,数量级比较
F
考点:skew heap, merge 操作, amortized cost计算, potential functions记忆
?
【knapsack problem】背包问题
【approximation ratio】近似度;近似比
考点:背包问题,贪心算法,packing rule
T
题解:假设最小情况:由于AVL的子树还是AVL,所以我们可以作图递推前几个,发现,所以最少是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+树的定义好多有分歧,见我的平板笔记