算法

1. 算法的幾個特征是什么。

2. 算法復雜性的定義。大O、θ、?、小o分別表示的含義。

3. 遞歸算法的定義、遞歸算法的兩要素。

4. 分治算法的思想，經典的分治算法(全排列、二分搜索、歸并排序、快速排序、線性時間選擇、最接近點對問題)。

5. 動態規劃算法解題框架，動態規劃算法的兩個要素是什么？備忘錄方法是什么？

6. 經典的動態規劃問題(矩陣連乘問題、最長公共子序列問題、0-1背包問題)。

7. 貪心算法的思想，貪心算法的兩個要素。

8. 經典的貪心問題(活動安排問題、背包問題、裝載問題、哈夫曼編碼、單源最短路徑、最小生成樹問題)。

9. 回溯法的思想，回溯法中有哪兩種典型的模型。

10. 經典的回溯算法(n后問題、0-1背包問題、旅行售貨商問題)。

11. 分支限界法思想，有哪兩種分支限界法。

12. 經典的分支限界算法(0-1背包問題、旅行售貨商問題)。

數據結構

1. 數據結構的定義。

2. 棧的兩個應用：括號匹配和表達式的計算。是怎么應用的？表達式計算用的是哪種表達方式？有什么好處?

3. 字符串匹配算法：樸素的匹配算法、KMP算法。

4. 二叉樹前序、中序、后序遞歸遍歷算法。二叉樹前序非遞歸遍歷算法。

5. 堆，建堆算法，堆的插入和刪除算法，堆排序。

6. 哈希。哈希函數的有哪些種？余數的取法？ 處理沖突的方法？ 閉散列方法有哪些？

7. 二叉搜索樹的搜索、插入、刪除。時間復雜度。

8. 二叉平衡樹的插入結點的原理，有哪幾種旋轉方式？分別適用于哪種情況。分析二叉平衡樹的時間復雜度。

9. 紅黑樹的定義，紅黑樹的性能分析和與二叉平衡樹的比較。

10. 圖有哪些儲存表示。

11. 鏈表插入排序、鏈表歸并排序。

12. 常見的有哪幾種排序算法，試比較其時間復雜度，以及是否穩定，及各自使用的情形。

13. 常用分配排序有哪幾種？ 基數排序的定義，分類及原理。

14. 外部排序的過程。

15. B樹、B+樹、Trie的概念及用途，添加刪除結點的原理。