資料結構與算法-面試題彙總

目錄

棧和隊列

哈希表

什麼是哈希表，哈希表的實作是怎麼樣的，哈希沖突是什麼，怎麼解決哈希沖突？

樹

簡述完全二叉樹

簡述AVL樹

簡述紅黑樹

紅黑樹和AVL樹有什麼差別？

圖

簡述最小生成樹和其對應的算法

簡述最短路徑算法

排序

簡述穩定排序和非穩定排序的差別

常見的穩定排序算法有哪些

常見的不穩定排序算法有哪些

簡述快速排序

簡述希爾排序

簡述歸并排序

簡述堆排序

棧和隊列

棧是一種後進先出的線性表，其限制隻能在表尾進行插入或删除操作。

隊列是一種先進先出的線性表。其限制隻能線上性表的一端進行插入，而在另一端删除元素。

哈希表

什麼是哈希表，哈希表的實作是怎麼樣的，哈希沖突是什麼，怎麼解決哈希沖突？

哈希表（又名散清單）是根據鍵（key）直接通路記憶體存儲位置的一種資料結構，通過計算一個關于鍵值的函數，将所需查詢的資料映射到表中的一個位置來通路記錄，映射函數叫做散列函數，存放記錄的數組叫散清單

哈希沖突的解決辦法：

• 開放定址法：當發生哈希沖突時，如果哈希表未被裝滿，那麼可以把這個值存放到沖突位置中的下一個空位置中去
• 鍊位址法：對相同的哈希位址，設定一個單連結清單，單連結清單内放的都是哈希沖突
• 再哈希法：又叫雙哈希法，有多個不同的Hash函數，當發生沖突時，使用第二個，第三個，….，等哈希函數計算位址，直到無沖突。雖然不易發生聚集，但是增加了計算時間。
• 建立公共溢出區： 将哈希表分為基本表和溢出表兩部分，凡是和基本表發生沖突的元素，一律填入溢出表

樹

簡述完全二叉樹

一棵深度為k的有n個結點的二叉樹，對樹中的結點按從上至下、從左到右的順序進行編号，如果編号為i（1≤i≤n）的結點與滿二叉樹中編号為i的結點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。

簡述AVL樹

AVL樹是一種改進版的搜尋二叉樹，其引入平衡因子（左子支高度與右子支高度之差的絕對值），通過旋轉使其盡量保持平衡。任何一個節點的左子支高度與右子支高度之差的絕對值不超過1。

簡述紅黑樹

紅黑樹本身是有2-3樹發展而來，紅黑樹是保持黑平衡的二叉樹，其查找會比AVL樹慢一點，添加和删除元素會比AVL樹快一點。增删改查統計性能上講，紅黑樹更優。紅黑樹主要特征是在每個節點上增加一個屬性表示節點顔色，可以紅色或黑色。紅黑樹和 AVL 樹類似，都是在進行插入和删除時通過旋轉保持自身平衡，進而獲得較高的查找性能。紅黑樹保證從根節點到葉尾的最長路徑不超過最短路徑的 2 倍，是以最差時間複雜度是 O(logn)。紅黑樹通過重新着色和左右旋轉，更加高效地完成了插入和删除之後的自平衡調整。

紅黑樹和AVL樹有什麼差別？

紅黑樹的優點

紅黑是用非嚴格的平衡來換取增删節點時候旋轉次數的降低，任何不平衡都會在三次旋轉之内解決，而AVL是嚴格平衡樹，是以在增加或者删除節點的時候，根據不同情況，旋轉的次數比紅黑樹要多。是以紅黑樹的插入效率更高！！！

與AVL樹的比較

    紅黑樹要求從根節點到葉子節點的最長路徑不大于最短路徑的兩倍

    AVL 樹要求每一個子樹的左右孩子節點高度差不超過1

保持平衡的要求上面，AVL樹要求大于RBtree, 也就帶來了search, insert 和delete操作的性能差異

相同點

圖

簡述最小生成樹和其對應的算法

最小生成樹：對于有 n 個結點的原圖，生成原圖的極小連通子圖，其包含原圖中的所有 n 個結點，并且有保持圖連通的最少的邊。

普裡姆算法（加點）：取圖中任意一個頂點 v 作為生成樹的根，之後往生成樹上添加新的頂點 w。在添加的頂點 w 和已經在生成樹上的頂點v 之間必定存在一條邊，并且該邊的權值在所有連通頂點 v 和 w 之間的邊中取值最小。之後繼續往生成樹上添加頂點，直至生成樹上含有 n-1 個頂點為止。

克魯斯卡爾算法（加邊）：先構造一個隻含 n 個頂點的子圖 SG，然後從權值最小的邊開始，若它的添加不使 SG 中産生回路，則在 SG 上加上這條邊，如此重複，直至加上 n-1 條邊為止。

簡述最短路徑算法

Dijkstral算法為求解一個點到其餘各點最小路徑的方法，其算法為：

假設我們求解的是頂點v到其餘各個點的最短距離。n次循環至n個頂點全部周遊：

1. 從權值數組中找到權值最小的，标記該邊端點k
2. 列印該路徑及權值
3. 如果存在經過頂點k到頂點i的邊比v->i的權值小
4. 更新權值數組及對應路徑

排序

簡述穩定排序和非穩定排序的差別

穩定排序：排序前後兩個相等的數相對位置不變，則算法穩定

非穩定排序：排序前後兩個相等的數相對位置發生了變化，則算法不穩定

常見的穩定排序算法有哪些

插入排序、冒泡排序、歸并排序

常見的不穩定排序算法有哪些

希爾排序、直接選擇排序、堆排序、快速排序

簡述快速排序

随機選擇一個基準元素，通過一趟排序将要排序的資料分割成獨立的兩部分，一部分全部小于等于基準元素，一部分全部大于等于基準元素，再按此方法遞歸對這兩部分資料進行快速排序。

排序算法不穩定，時間複雜度 O(nlogn)，空間複雜度 O(logn)。

簡述希爾排序

希爾排序：把記錄按下标的一定增量分組，對每組進行直接插入排序，每次排序後減小增量，當增量減至 1 時排序完畢。

排序算法不穩定。時間複雜度 O(nlogn)，空間複雜度 O(1)。

簡述歸并排序

歸并排序：将待排序序列分成兩部分，然後對兩部分分别遞歸排序，最後進行合并。

排序算法穩定，時間複雜度都為 O(nlogn)，空間複雜度為 O(n)。

簡述堆排序

堆排序：将待排序數組看作一個樹狀數組，建立一個二叉樹堆。通過對這種資料結構進行每個元素的插入，完成排序工作。

排序算法不穩定，時間複雜度 O(nlogn)，空間複雜度 O(1)。