ADS? YDS! (×) 🔗暄暄的考试技巧

平衡搜索树

AVL Tree

🔋Balance Factor = hL - hR，取值-1, 0, 1，h( null ) = -1
🔋AVL树节点最少的情况是（空树高定义为-1时） :::info ❓
1, 2, 4, 7, 12, 20, 33
❓
注意有时候会把空树树高定义成0，此题选 B

❓

（F）是完全二叉树，不是完美二叉树！ ::: :::info ❓

::: :::info ❓In an AVL tree, it is impossible to have the balance factor of every non-leaf node to be +1/-1. (F) ::: :::info ❓
只有 I 。AVL 删除就是 BST 删除然后调整 :::

Splay Tree

🔋 :::info ❓

::: 🔋

1. 找到待删除元素X，经过AVL操作，X变为根节点
2. 删除X，这时有两个子树
3. 找到左子树的最大元素Y，经过AVL操作，Y变为左子树的根节点（Y没有右孩子）
4. 将右子树接到左子树的右孩子上 :::info ❓
   
   :::

   Red-Black Tree

   🔋

• 每个节点要么红要么黑
• 根节点是黑色
• 叶节点( NIL )是黑色，但不显式的画出（红黑树中的叶节点是NULL指针）
• 红节点的两个儿子必须是黑色

• 对于每个节点，从其出发到叶节点的所有简单路径都有相同个数的黑节点 :::info ❓
  
  （T）很明显如果红点度为1，右子树黑高为1，左子树因为其儿子为黑，加上NIL，所以一定比右子树大1 ::: 🔋计算黑高不要忘记 NIL
  🔋有 N 个内点的红黑树高度最多是
  🔋插入 & 删除
  :::info ❓
  
  （T） ::: 🔋插入 & 删除（Cont.）
  Red-Black Trees & B+ Trees :::info ❓
  
  
  ❓
  (F) When inserting a node into a red-black tree, we shall first insert the node as into an ordinary binary search tree, and then color the node black.

• 应该涂成红色 ::: Red-Black Trees & B+ Trees :::info ❓删除emm，直接二叉搜索树删然后自己涂色可能正确率高一点 :::

  B+ Tree

  🔋 :::info ❓
  (T) The root of a B+ tree of order m has at most m subtrees.

• 性质1

❓

此题选 D ，A 错误原因是可能是叶子，没有儿子（参见性质第一条） ::: 🔋
Red-Black Trees & B+ Trees :::info ❓
::: :::info ❓

36 = 18 ::: :::info ❓

0个和1个很容易做到，2个如上图，删除17，21被借走合并，内点更新为19和22
❓

::: 🔋B+ 树操作复杂度，注意查找不论度数均是
:::success ❓
*(T) The time bound of the FIND operation in a B+ tree containing N numbers is O(logN), no matter what the degree of the tree is.

• depth 有 log N / log M，每一层二分查找是 log M :::

  优先队列

  Leftist Heap & Skew Heap

  🔋
  Leftist Heaps & Skew Heaps | 左式堆、斜堆
  🔋
  Leftist Heaps & Skew Heaps | 左式堆、斜堆 :::info ❓
  
  是这样的。。
  ❓
  
  因为斜堆不加判断的进行左右儿子的交换，所以右路径的长度并没有保证，可以任意长
  ❓
  (T) A leftist heap with the null path length of the root beingmust have at least nodes.

• 由于 Npl 的限制，所以左右子树的 Npl 是，以此类推，为

(F) The NPL of each node in a heap is supposed to be calculated from top down.

• bottom up

❓

容易想当然的认为左式堆满足定义就总比斜堆平衡，事实上一个很明显的反例就是顺序插入（如第一道例题所示），斜堆的结果是完美二叉树！
❓
遇到要合并的题，无脑迭代合并，又快又准；斜堆注意全交换就行


❓

分治法建堆，第一轮1 1合并，第二轮2 2合并，第三轮4 4合并……，合并时间复杂度为，故可以写出递推为，求得时间复杂度为 ::: 🔋斜堆摊还分析中 light 和 heavy 的定义
:::info ❓ :::

Binomial Queue

🔋有个儿子，个节点，深度为处有个节点
🔋
:::info ❓

ppt 原话，后半句是因此平均插入时间是常数 :::

摊还分析

摊还分析到现在也没学会，不过参考@27rabbit(27rabbit) 前辈的文章还是有一些新的理解
势能分析法
🔋
:::info ❓

❓

❓

❓

在扩倍的时候操作代价最大，选择 A 作为势能函数时，此时势能下降最大 :::

Backtracking

:::danger
注：回溯的效率跟S的规模、约束函数的复杂性、满足约束条件的结点数相关。

• 约束函数决定了剪枝的效率，但是如果函数本身太复杂也未必合算。满足约束条件的结点数最难估计，使得复杂度分析很难完成。 :::

  8-Queens

  :::info ❓
  (F) In the 4-queens problem, (x1, x2, x3, x4) correspond to the 4 queens’ column indices. During backtracking, (1, 4, 2, ?) will be checked before (2, 4, 1, ?), and none of them has any solution in their branches.
  前半句对，后半句错，(2, 4, 1, 3)是一组解
  ❓
  (T) In the 4-queens problem, (x1, x2, x3, x4) correspond to the 4 queens’ column indices. During backtracking, (1, 3, 4, ?) will be checked before (1, 4, 2, ?), and none of them has any solution in their branches.
  :::

  Tic-tac-toe

  🔋winning case 是当前状态下所有可能的胜利状态 :::info ❓
  
  电脑是 O ，人是 X，O 有 3 种，X 也有 3 种，故为0 :::

  Turnpike Reconstruction

  🔋每次取最大距离并把产生的新距离从集合中删除，没有符合的就回溯。 :::info ❓
  
  （F）还可以是 (0, 4, 6, 8) :::

  α-β 剪枝

  🔋α 剪枝是小中取大，β 是大中取小
  
  :::info ❓
  
  ❓
  
  选 D。希望剪掉15，已知9，那么他们父亲节点必然<=9，因此当第二层中间节点>=9时，第二层最右侧节点将被剪掉。 :::

  Dynamic Programming

  :::info ❓
  
  要满足无后效性，D 和过去未来都有关
  (T) To solve a problem by dynamic programming instead of recursions, the key approach is to store the results of computations for the subproblems so that we only have to compute each different subproblem once. Those solutions can be stored in an array or a hash table.
  意思是说结果可以暂存在数组或者哈希表里 :::

  Ordering Matrix Multiplications

  🔋
  
  :::info ❓
  :::

  Optimal Binary Search Tree

Divide & Conquer

Closest Points Problem

:::info (T) If devide-and-conquer strategy is used to find the closest pair of points in a plane, unless the points are sorted not only by their x coordinates but also by their y coordinates, it would be impossible to solve it in a time of O(NlogN), where N is the number of points. :::

主定理

🔋
:::info ❓
两个排好序（升序）的数组，求第 k 小的数。

我们可以得出复杂度是 ::: 🔋
:::info ❓
来一道第二主定理的题

❓

此题选 B，本计算 fw 还是带选项算快亿点，下面是正常的迭代：
:::

倒排文件索引

wrt 曰：“背多分，不讲。”

🔋precison 是在查询到的文件中相关的比例，recall 是相关的文件中被查询到的比例。 :::info ❓

F，不是剔除常用单词，而是提取词干
❓

❓

（T）响应速度重要
❓
::: | | A | B | | —- | —- | —- | | precison | 125/(125+189) | 1500/(1500+2300) | | recall | 125/2019 | 1500/2019 |

从这里开始是夏学期的内容

Greedy | 贪心算法

Activity Selection Problem

🔋Greedy Method
🔋 :::info ❓
应该是 in some :::

Huffman Codes

🔋 :::danger

• 霍夫曼树的待编码字符只出现在叶子上，也即编码是前缀的（没有任何编码是其他编码的前n位） ::: :::info ❓ :::

NP Completeness

🔋
NP-Completeness

:::info ❓

事定义

选 A :::

Approximation | 近似算法

:::info ❓

❓
:::

Local Search

:::info ❓

:::