C++ 與資料結構面試必考知識點完整總結

前言

整理了一些筆試面試中高頻出現的 C++ 基礎與資料結構知識點，內容涵蓋廣義表、虛函數機制、二叉樹性質、堆操作、樹的遍歷、printf 行為、記憶體佈局、繼承與多型、拓撲排序、AVL 樹旋轉、排序算法特性、final/finally/finalize 差異、free/delete 差異、內聯與虛函數、宏與 const、STL 容器底層結構、位元組對齊等核心概念。適合面試前快速查漏補缺，也可作為平時複習的參考筆記。

一、資料結構核心概念

1. 廣義表

• 表頭：可以是單一元素值，也可以是一個子表。
• 表尾：除去表頭後剩下的元素組成的表，表尾要么是表，要么是空表。

2. 二叉樹關鍵性質

• 深度：樹的層數。
• 度：節點的孩子數；樹的度為所有節點度的最大值。
• 完全二叉樹：將滿二叉樹從右向左刪除節點所得的二叉樹。
• 葉子節點與度為 2 的節點關係：任何二叉樹中，度為 0 的葉子節點比度為 2 的節點多 1 個（即 n0 = n2 + 1）。若完全二叉樹有 n 個葉子節點，總節點數最多 2n 個。
• 前序+中序可唯一確定二叉樹：先序第一個為根，中序以根分左右子樹，遞歸構建。
• 葉子節點在三種遍歷中的相對順序不變：前序、中序、後序中，所有葉子節點的先後順序完全相同。
• 先序與後序序列相反：若一棵非空二叉樹的先序遍歷序列與後序遍歷序列正好相反，則該樹只有一個葉子節點（即為單鏈結構）。

3. 堆的基本操作

• 插入：新元素放在最後，然後向上調整（上浮）。
• 刪除：將最後一個元素移到刪除位置，然後向下調整（下沉）。

4. 樹與森林轉二叉樹

將樹 T 轉換為二叉樹 B 後，對 B 中任一節點 N：

• 左子樹來自 N 在 T 中的長子（第一個孩子）。
• 右子樹來自 N 在 T 中相鄰的右兄弟。

5. 圖的連通性

• 連通圖：任意兩頂點之間都有路徑。
• 連通分量：非連通圖中的極大連通子圖（頂點數極大）。

6. 拓撲排序

用於確定依賴關係集合中任務的執行順序。得到的線性序列只要滿足「前驅任務在後繼任務之前」即可，序列可能不唯一（如 V1→V2，序列中 V1 僅需在 V2 前）。

7. B 樹與 B+ 樹

• B 樹：m 階 B 樹滿足：每節點至多 m 棵子樹；非根非葉節點至少 ⌈m/2⌉ 棵子樹；根非葉至少 2 棵；所有葉節點同層；非葉節點包含關鍵字與子樹指針，關鍵字分隔子樹範圍。僅支持隨機檢索。
• B+ 樹：非葉節點 n 個子樹對應 n 個關鍵字（純索引）；所有葉節點包含全部關鍵字及記錄指針，且按序鏈接。既支持隨機檢索，又支持順序檢索，更適合文件系統。

二、C++ 語言核心機制

1. 構造函數不能是虛函數的五大理由

1. 存儲空間角度：虛函數調用需 vtable 指針（vptr），但構造時對象尚未實例化，內存空間不存在，無法定位 vtable。
2. 使用角度：虛函數用於「信息不全時通過基類指針/引用調用派生類覆寫」。構造函數本職是初始化實例，創建時類型已明確，無需多態。
3. 析構對比：創建對象需明確類型，但銷毀常通過基類指針，故析構函數必須是虛函數以正確調用派生類析構。
4. 實現角度：vtable 在構造函數調用後才建立；調用構造時對象真實類型尚未確定（子類會調父類構造）；構造函數僅執行一次，非動態行為。
5. VPTR 初始化順序：每個構造函數調用首要任務是初始化 VPTR 指向當前類的 vtable。構造鏈從基類到派生類，每層構造都會覆寫 VPTR，最終由最派生類構造決定。若構造期間調用虛函數，只會解析到當前類的 vtable，而非最終 vtable。

2. 運算符與表達式細節

• printf 參數壓棧順序：從右向左壓棧，先運行右側參數。例：printf("%d,%d", a, ++a) 輸出兩個相等的值（均為 a+1 後的值）。
• 判斷寫法建議：將右值放在 == 左側（如 if (0 == x)），可避免誤寫成賦值 = 導致邏輯錯誤。
• ASCII 轉義：所有 ASCII 碼均可用 \ 加數字（通常八進制）表示，見反斜線加三位數字即為字符常量。
• 前置/後置 ++ 差異：
  • 前置 ++i 返回左值（對象本身），可連續使用如 ++++i。
  • 後置 i++ 返回右值（舊值副本），不可連續使用如 i++++（無法對右值自增）。
  • 同一表達式中多次後置 ++ 使用的是變化前的值；前置 ++ 每次改變變量。表達式結束後原變量均已改變。例：x=1; y=(x++)+(x++); 結果 y=2, x=3。
• 邏輯運算短路特性：&& 左操作數為假則不執行右側；|| 左操作數為真則不執行右側。
• 隱式類型轉換規則：雙目運算中，若有 double 則另一轉為 double；否則有 float 轉 float；否則有 long 轉 long；否則（byte, short, int, char）均轉 int。

3. 記憶體佈局與對齊

• 基本類型大小（32/64 位差異見下表）：
  char=1B, short=2B, int=4B, float=4B, double=8B；指針 32 位 4B，64 位 8B；long 32 位 4B，64 位 8B；long long 皆 8B。
• 對齊規則：char 任意地址；short 2 倍數地址；int 4 倍數地址。結構體起始地址與大小須為對齊數整數倍，成員按各自對齊規則存放，必要時填充。
• 三大存儲區：局部變量→棧；全局/靜態變量→靜態存儲區；動態分配→堆。
• 棧與堆生長方向：堆向上（地址增大），棧向下（地址減小）。
• 數組指針：&a 返回指向整個數組的指針（如 int (*)[4]）；數組名直接賦值給指針得首元素指針。
• 結構體 vs 聯合體：結構體順序存儲，大小為成員大小之和（含填充）；聯合體重疊存儲，大小為最大成員大小（考慮對齊）。
• sizeof vs strlen：sizeof 計算結束符 \0，strlen 不計算。
• 虛函數表指針位置：擁有虛函數的類，對象首地址存放 vptr，其後為成員變量。

4. 繼承與多型

• 公有繼承即子類型：派生類對象可用於基類對象適用的所有場合（里氏替換原則）。
• 純虛函數與抽象類：virtual void f() = 0; 含純虛函數的類為抽象類，不能實例化對象，只能作基類；可定義抽象類指針/引用實現多態；不能用作參數類型、返回類型或轉換類型。
• 多型資料類型：包含的資料元素類型不確定（如 void*、模板、variant 等）。

5. 宏與 const

• 處理階段不同：宏在預處理展開，const 在編譯階段處理。
• 類型檢查：宏無類型，不檢查；const 有具體類型，編譯期類型檢查。
• 存儲方式：宏每用一次展開一次；const 在內存分配一次，節省空間、提高效率。
• 建議：C++ 中盡量用 const 常量完全取代宏常量。

6. 內聯與虛函數

虛函數調用在運行期才確定具體函數，內聯要求編譯期展開，兩者矛盾。即使最簡單的虛函數，編譯器也無法內聯。

7. free vs delete

• free(ptr)：釋放指針指向的內存，但指針本身仍指向原地址（成野指針），需手動置空。
• delete ptr：刪除對象並調用析構函數，指針不會自動置空，但語義上表示對象生命周期結束。

8. STL 容器底層結構

• list：雙向鏈表。
• map / set / multimap / multiset：紅黑樹（RB-Tree，平衡二叉搜索樹）。

9. final / finally / finalize（Java 風格，C++ 僅有 final）

• final (C++11)：修飾類不可繼承；修飾虛函數不可覆寫；修飾變量不可修改（須初始化）。
• finally (Java)：異常處理塊，無論是否拋出異常都執行，用於清理資源。
• finalize (Java)：Object 方法，垃圾回收前調用，用於釋放非內存資源。

10. string::reserve()

預分配緩衝區容量至少為 size，避免頻繁重新分配導致效率下降。若 size 小於當前長度，則縮減至恰好容納現有字符。線性時間複雜度。

三、AVL 樹平衡旋轉詳解

插入節點後若破壞平衡（平衡因子 |bf| > 1），找到離插入節點最近且 |bf|>1 的節點 A（失去平衡的最小子樹根），按插入位置分四種情況調整：

1. LL 型（左左）

插入在 A 的左孩子 B 的左子樹。A bf 由 1 增至 2。一次順時針旋轉（右旋）：B 上旋成根，A 下旋成 B 右子樹，B 原右子樹變為 A 左子樹。

2. RR 型（右右）

插入在 A 的右孩子 C 的右子樹。A bf 由 -1 減至 -2。一次逆時針旋轉（左旋）：C 上旋成根，A 下旋成 C 左子樹，C 原左子樹變為 A 右子樹。

3. LR 型（左右）

插入在 A 的左孩子 B 的右子樹。A bf 由 1 增至 2。雙旋轉：先左旋後右旋。先將 B 的右子樹根 D 左旋提升到 B 位置（變 LL 型），再將 D 右旋提升到 A 位置。

4. RL 型（右左）

插入在 A 的右孩子 C 的左子樹。A bf 由 -1 減至 -2。雙旋轉：先右旋後左旋。先將 C 的左子樹根 D 右旋提升到 C 位置（變 RR 型），再將 D 左旋提升到 A 位置。

核心口訣：平衡靠旋轉，參與旋轉 3 個節點（含可能的 NULL）。左旋時 p->right 必不為空，右旋時 p->left 必不為空。從空樹建立並保持平衡，不平衡只發生在插入/刪除，標誌為出現 bf==2 或 bf==-2 的節點。

四、排序算法特性總結

（圖片包含各排序算法的時間複雜度、空間複雜度、穩定性等對比）

五、棧的存儲結構

• 順序棧：用連續存儲單元自棧底到棧頂存放元素，附設 top 指針指示棧頂。
• 鏈式棧：鏈表實現，操作更易實現（屬線性表操作特例）。

六、線索二叉樹

利用 n 個節點的二叉樹有 n+1 個空指針域（或說 n-1 個非空指針？實際為 n+1 個空鏈域），將空指針指向特定遍歷序列（先序/中序/後序）的前驅或後繼。左空指向前驅，右空指向後繼。

七、自動變量

僅在定義時創建，函數返回時系統自動回收存儲空間。未特別說明的局部變量均為自動變量，可用 auto 關鍵字說明（C++11 前）。

八、常見誤區提示

• 非法指針：指向已回收內存或錯誤地址。
• 類對象指針轉型：指針值不變，僅改變讀取地址的方式（解釋類型）。
• 運算符重載參數：成員函數重載前綴一元運算符參數表為空；重載後綴一元運算符參數表有一個 int 佔位參數。