資料結構應試要點——排序與查找

排序與查找的基礎知識請參閱相關書籍，這裡列出考試時需要注意或容易忽視的地方。如有補充，歡迎評論或私信！

查找

順序查找與折半查找

1.對線性的連結清單隻能進行順序查找。

2.有序表的順序查找可以是順序結構也可以是鍊式結構。

3.折半查找僅适用于有序的順序表，不适合鍊式結構。折半查找的過程可以使用二叉判斷樹表示，因而其比較次數不會超過樹高。二叉判斷樹是一種平衡樹，效率穩定，這是其與二叉排序樹主要差別。

4.分塊查找塊内的元素可以無序，塊與塊之間必須有序。

5.折半查找（二叉判斷樹）的平均查找長度：

• ASL（成功）：每一個結點與其所在層次的乘積之和。
• ASL（失敗）：先在每一個度小于2的結點添加虛拟結點（若普通結點為圓形，則這些虛拟結點為矩形或方形，在要求作出判斷樹時應将這些虛拟結點一同畫出），使其度為2，則失敗時的平均查找長度為根結點到這些虛拟結點的路徑長度之和。

6.對于順序查找，無論資料是否有序，查找成功的平均時間均相同，但查找失敗的平均時間不同（有序表顯然要短）。

7.對資料較多（n個）的分塊表進行查找，最理想的塊長為根号n。

8.順序查找的二叉判斷樹的結點或者是葉子結點，或者它隻有右孩子。

B樹與B+樹

1.一棵含n個關鍵字的m階B樹具有如下特點：

• 每個結點至多有m個子樹，（m-1）個關鍵字。
• 除根結點外每個非葉結點至少有⌈m/2⌉棵子樹，⌈m/2⌉ - 1個關鍵字，而根結點需要特殊讨論，其子樹至少為兩棵。
• 其高度至少為以m為底(n + 1)的對數，至多為以⌈m/2⌉為底((n + 1) / 2) + 1的對數。
• B樹的葉結點不存儲任何資料。

2.B樹變高的唯一方法是插入，變矮的唯一方法是删除。

3.B樹的插入位置一定是在最底層中的某個非葉結點。

4.若插入操作導緻關鍵字個數不符合上面1中對個數的要求，則需從⌈m/2⌉處對結點進行分裂。 

5.若删除操作導緻關鍵字個數不符合上面1中對個數的要求且兄弟結點不夠借，則将其父結點拉下，與左右兄弟結點合并。

散清單 （哈希查找）

1.沖突是不可避免的，是以與裝填因子α無關。沖突産生的機率與裝填因子的大小成正比。

2.散清單查找成功的平均查找長度與裝填因子直接相關，與表長無關。

3.在開放定址前提下，删除元素可能會導緻搜尋路徑中斷，通常的做法是在删除的地方做标記。

4.在開放定址中，散列到同一個位址而産生“堆積”（或聚集）問題，是指同義詞沖突的探查序列和非同義詞之間不同的探查序列交織在一起，導緻關鍵字查詢需要經過較長的探測距離，降低了散列的效率。是以要選擇好的處理沖突的方法來避免堆積。

5.沖突對存儲效率、散列函數和裝填因子均不會有影響，而ASL會因堆積現象而增大。

6.同義詞沖突不等于聚集，鍊位址法在同義詞沖突時不會發生聚集現象。

7.散清單的查找效率取決于：散列函數、處理沖突的方法、填裝因子。

8.題目中給出的裝填因子的用處是根據α = n / N求表長N，其中n是關鍵字的個數，若N為分數，則向上取整。如若需要确定散列函數，且形式為H(key) = key % p，則p取不大于N的最大質數。

9.計算平均查找長度時，成功情況下的分母為資料元素的個數，失敗情況下的分母為哈希函數裡key後面的數，即上面的p。

排序

1.根據定義，拓撲排序既不屬于内部排序，也不屬于外部排序。

2.内部排序通常需要進行兩種操作：比較和移動，但基數排序并不基于比較。

3.排序趟數與初始序列狀态有關的排序：交換排序（冒泡排序、快速排序）

4.比較次數與初始序列狀态無關的排序：選擇排序、基數排序

5.移動次數與初始序列狀态無關的排序：歸并排序、基數排序

6.時間複雜度與初始序列狀态有關的排序：直接插入、交換排序（冒泡排序、快速排序）

• 記憶時間複雜度與初始序列狀态無關的排序：一堆（堆排序）烏龜（歸并排序）選（選擇排序）基（基數排序）友

7.穩定的排序：直接插入、冒泡排序、歸并排序、基數排序

8.不穩定的排序：簡單選擇排序、希爾排序、快速排序、堆排序

9.直接插入排序可以用于鍊式存儲的資料排序。

10.快速排序是所有内部排序算法中平均性能最優的排序算法。

11.快速排序在要排序的資料基本有序的情況下最不利于發揮其長處。

12.如何判斷一個序列是否為快速排序第i趟排序結果？

答：找到i個以上元素在其最終排序位置，且這些元素的左序列小于它，右序列大于它。

13.快速排序的空間複雜度較為特殊，最優情況下棧深度為logn，最壞情況下深度為n。

14.選擇排序（簡單選擇、堆排序）不關心序列的初始狀态，時間複雜度始終相同。

15.堆查找效率較低，因其資料存儲是無序的，隻是根結點與其子樹有大小關系而已。