考研408數據結構查找算法核心知識點深度解析

一、查找基本概念

1.1 核心定義與易錯點

1. 查找表與關鍵字

   • 易錯點：混淆靜態查找表（僅查詢）與動態查找表（含插入/刪除操作）的應用場景。例如哈希表屬于動態查找結構，而分塊查找適用于靜態數據。
   • 難點：理解平均查找長度（ASL）的計算公式：
     [
     ASL = \sum_{i=1}^{n} P_i \times C_i
     ]
     其中 (P_i) 為查找概率，(C_i) 為比較次數。考生常忽略概率不等的情況，錯誤假設等概率條件。

2. 判定樹與查找效率

   • 易錯點：誤將折半查找判定樹視為完全二叉樹。實際上，當元素個數 (n) 不是 (2^k-1) 時，判定樹中存在非滿結點層。

---

二、順序查找

2.1 算法實現與優化