21-22 期末真题

判断题

1-3 online approximation近似算法

at least 和 at most 是两种东西

bin-packing问题

Bin Packing Problem (Minimize number of used Bins) - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

https://www.geeksforgeeks.org/bin-packing-problem-minimize-number-of-used-bins/

 

1. 算法需要计算每对点之间的距离,这一步的时间复杂度为O(N^2)。

2. 将所有距离插入AVL树D中,插入操作的平均时间复杂度为O(logN)。

3. 在重构凸包的过程中,需要从D中查找并删除某些距离,查找和删除操作在AVL树中的时间复杂度均为O(logN)。

4. 如果不发生回溯,那么查找和删除距离的总次数为O(N)。

选择题

编程题

20-21 高级数据结构春夏

判断题

1. B+树的内容

2. 局部搜索算法Optimization Problem，Local Search Algorithm
1. 邻域内的最优解和全局最优解之间的关系

3. 什么是stop word

4. skip list的搜索、删除元素的最坏时间

5. NPC和NP问题的概念是什么

6. optimal number

7. Fibonacci number
要回答为什么通过矩阵幂的方法计算斐波那契数的复杂度是 \(O(\log n)\)，我们需要理解以下几点：
1. 矩阵幂计算：
• 给定矩阵 \(A = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}\)，要计算其第 \(n\) 次幂 \(A^n\)。
• 矩阵幂 \(A^n\) 可以通过递归的方法来计算，这种方法被称为“快速幂”或“二分幂法”。
2. 快速幂算法：
• 快速幂算法的核心思想是将计算 \(A^n\) 转换成若干次矩阵乘法。具体来说：
• 如果 \(n\) 是偶数，\(A^n = (A^{n/2}) \times (A^{n/2})\)；
• 如果 \(n\) 是奇数，\(A^n = A \times (A^{(n-1)/2}) \times (A^{(n-1)/2})\)。
• 这种方法通过每次将指数减半，将复杂度从线性的 \(O(n)\) 降低到对数级别的 \(O(\log n)\)。
3. 算法复杂度分析：
• 每次矩阵乘法的复杂度是常数时间 \(O(1)\)，因为 2x2 矩阵的乘法固定需要常数步操作。
• 因此，计算 \(A^n\) 的时间复杂度主要取决于递归调用的次数。
• 由于每次递归调用将问题规模减半，所以总的递归调用次数为 \(\log n\)，因此总体时间复杂度是 \(O(\log n)\)。
4. 斐波那契数计算：
• 一旦我们计算出 \(A^n\)，斐波那契数 \(F_n\) 就可以直接从矩阵 \(A^n\) 的元素中读取出来。因此，整个过程的时间复杂度仍然是 \(O(\log n)\)。
综上所述，通过快速幂法计算矩阵幂 \(A^n\) 的时间复杂度是 \(O(\log n)\)，因此计算第 \(n\) 个斐波那契数的时间复杂度也是 \(O(\log n)\)。
同理，那么n^2也不会影响logn的时间复杂度

8. optimal prefix code

9. 并行和串序

10. skew heap中的light node的数量
The number of light nodes along the right path of a skew heap is O(logN).
是正确的

11. replacement selection

12. What makes the time complexity analysis of a backtracking algorithm very difficult is that the number of solutions that do satisfy the restriction is hard to estimate. 回溯的基本概念

13. 预期时间，实际时间和均摊时间

选择题

1. 贪心算法找optimal solution
1. 使用条件和限制

2. 均匀分配中的期望值计算

3. merge the leftist heaps

4. 数据结构local adjustment 参考splay树的access操作

5. 均摊分析的具体分析

6. 剪枝

7. 递归的时间复杂度分析

8. 对不同数组进行二分查找搜索

9. AVL树的高度操作定义

10. 红黑树的再次定义操作

11. bin-packing approximation ratio
1. 考察NF和FF的具体定义和含义

12. Ranking problem

13. In a binomial queue, the total number of the nodes at even depth is always ___ than that of the nodes at odd depth (the root is defined to be at the depth 0).

14. Minimum Degree Spanning Tree problem
为了回答这个关于最小度生成树问题的问题，我们需要理解题目给出的算法及其对应的势函数。

题目概述

我们需要找到一个生成树，使其最大顶点度数最小。给定一个无向连通图 \(G(V, E)\)，我们需要找到一个生成树 \(T\)，使得其顶点度数的最大值最小。算法如下：
1. 找到 \(G\) 的任意生成树 \(T\)。
2. 如果存在某条边 \(e \in E(G) \setminus E(T)\) 的端点是 \(u\) 和 \(v\)，并且存在路径上另一个顶点 \(w\)，使得 \( \max \{ d(u), d(v) \} + 1 < d(w) \)，那么用 \(e\) 替换掉 \(T\) 中连接 \(w\) 的某条边 \(e'\)，即 \( T := T \cup \{e\} \setminus \{e'\} \)。
3. 重复步骤2，直到没有边可以替换。

证明算法终止

要证明这个算法在有限步骤内终止，我们需要定义一个非负的势函数 \( \phi(T) \)，并证明在每一步操作后 \( \phi(T) \) 严格减小。

选择合适的势函数

我们来看给出的四个势函数选项：
A. \( \phi(T) = \sum_{(u,v) \in E(T)} \max \{ d(u), d(v) \} \)
• 这个函数计算了生成树中每条边的最大顶点度数的和。此函数未必会严格减小，因为替换一条边未必总能减少这些最大值的和。
B. \( \phi(T) = \sum_{v \in V} d(v) \)
• 这个函数计算了所有顶点度数的总和。由于生成树的顶点数和边数是固定的，总顶点度数是 \(2(V-1)\)，不会随替换操作改变。
C. \( \phi(T) = \sum_{v \in V} 3^{d(v)} \)
• 这个函数是所有顶点度数的指数和。当顶点度数增加时，指数值会显著增加，因此每次替换操作导致的顶点度数减少会明显反映在势函数上，从而使其严格减小。
D. \( \phi(T) = \sum_{u \in V} \sum_{v \in V, v \neq u} \sum_{w \in V, w \neq u, v} \max \{ d(u), d(v), d(w) \} \)
• 这个函数涉及三重和且计算每三顶点组合的最大值，这使得势函数过于复杂，并且不容易分析其变化。

结论

综合分析，选项 C 最适合作为势函数。它计算的是顶点度数的指数和，能够保证每次替换操作后势函数严格减小，从而证明算法在有限步骤内终止。
因此，正确答案是：
• C. \( \phi(T) = \sum_{v \in V} 3^{d(v)} \)
🦄
最关键的点在于理解清楚题意 注意vertex的度数



什么是红黑树的内部节点

15.  k-way merge and a k-size heap
好的，我们来一步一步解析这道关于外部排序问题的选择题。题目要求判断以下关于用 \(k\)-路归并和大小为 \(k\) 的堆进行排序的比较次数 \(T(N, k)\) 和 \(k\) 的关系的哪个陈述是正确的。
首先，我们需要理解外部排序中的 \(k\)-路归并和堆的使用方式。

外部排序中的 \(k\)-路归并

在外部排序中，我们通常将数据分成多块，每块数据能在内存中处理。然后使用 \(k\)-路归并，将这 \(k\) 块数据合并到一起。
• \(k\)-路归并：指的是同时合并 \(k\) 个有序块，每次从 \(k\) 个块中选择最小的元素。
• 堆：通常使用大小为 \(k\) 的最小堆来实现 \(k\)-路归并，因为堆能有效地找出 \(k\) 个元素中的最小元素。

比较次数分析

对于 \(k\)-路归并：
• 每次归并操作需要从 \(k\) 个元素中找出最小元素。
• 使用大小为 \(k\) 的最小堆，每次插入和删除操作的时间复杂度是 \(O(\log k)\)。
我们来具体分析每个选项：
选项 A：\(T(N, k)\) 和 \(k\) 无关。
• 分析：显然，比较次数 \(T(N, k)\) 与 \(k\) 是有关的，因为 \(k\) 决定了每次归并操作需要比较的元素数量。
• 结论：错误。
选项 B：\(T(N, k)\) 是 \(O(k^2)\)（在 \(N\) 固定时）。
• 分析：这个描述不太符合实际情况，因为比较次数不可能是 \(k^2\)。使用堆结构，操作次数应与 \(\log k\) 相关，而不是 \(k^2\)。
• 结论：错误。
选项 C：\(T(N, k)\) 是 \(O(k \log k)\)（在 \(N\) 固定时）。
• 分析：对于每次归并操作，我们需要进行 \(k\) 次插入和删除操作，每次操作的时间复杂度是 \(O(\log k)\)。所以总的比较次数是 \(O(k \log k)\)。
• 结论：正确。
选项 D：\(T(N, k)\) 是 \(O(k)\)（在 \(N\) 固定时）。
• 分析：这忽略了堆操作的对数复杂度，仅考虑了线性复杂度，这是不正确的。
• 结论：错误。

结论

选项 C 是正确的，因为 \(T(N, k)\) 的复杂度是 \(O(k \log k)\)，这符合使用大小为 \(k\) 的堆来实现 \(k\)-路归并的情况。

16. AVL trees and splay trees具体的新操作
显然答案是两个
首先BF是左子树的高度-右子树的高度，因此结果是0,-1,+1
splay树里面，旋转一次可能是一次或者是两次旋转

17. b+树的插入操作

18. recall和precision

19. P和NP还有NPC问题的区别
所有的P问题都是NP问题，NP问题和NPH的问题的交集是NPC问题
There exists an NP-complete problem such that all the NP problems can be polynomially reduced to it.所有的NP问题都可以归约化为一个NPC问题
还有存在可判定的但是不属于NP的决策问题
🦄
SAT问题，顶点覆盖问题，哈密顿回路问题，TSP问题，团问题，最长路径问题，背包问题都是NPC问题，停机问题不是NPC问题，停机问题是不可判定问题

20. Vertex Cover problem问题
1. NP，P，NPC问题的概念和如何区分
2. NPC问题可以相互归约
3. 顶点覆盖问题可以在多项式时间内归约到Clique Problem
4. NPC问题的时间复杂度肯定不是多项式的
5. 给出一个覆盖集，判断节点数是否小于K，再判断是否每条边都有一个顶点在这个集合中，这里的时间复杂度是𝑂(𝐸+𝑉)

编程题

1. bionomial_heap 的合并