高级数据结构

课程信息

• 课程名称：高级数据结构
• 开课学期：2023-2024 学年春夏学期
• 授课教师：卜佳俊

课程内容

1. AVL 树、伸展树、摊还分析
2. 红黑树、B+ 树
3. 倒排索引（Inverted File Index）
4. 左式堆（Leftist Skew Heap）
5. 二项队列（Binomial Queue）
6. 回溯（Backtracking）
7. 分治（Divide and Conquer）
8. 动态规划（Dynamic Programming）
9. 贪心（Greedy）
10. NP 完全问题（NP-Complete Problem）
11. 近似算法（Approximation Algorithm）
12. 局部搜索（Local Search）
13. 随机化算法（Randomized Algorithm）
14. 并行算法（Parallel Algorithm）
15. 外部排序（External Sorting）

期末题型知识点（需要会写代码的）

程序填空

• B+ 树
  • 从根开始 FindKey（19-20 模拟）
• 二项队列：
  • 合并（20-21 模拟）(15-16 模拟）
  • 删除根（18-19 模拟）
  • 查找（16-17 模拟）
• 局部搜索：
  • 背包问题（21-22 模拟）
• 红黑树：
  • 判断（17-18 模拟）

编程题

• 回溯：
  • 解码问题：有多少种解码方式（19-20 模拟）
• 局部搜索：
  • 面包选择问题：是否立即选择面包（20-21 模拟）
• AVL 树：
  • 建树和判断（21-22 模拟）
  • 插入（17-18 模拟）
• 动态规划：
  • 最小步骤（18-19 模拟）
  • 最少时间（16-17 模拟）
• 其他：
  • 快速幂