數據結構與演算法面試題
❶ 數據結構面試題
1. 數據結構的定義。
2. 棧的兩個應用：括弧匹配和表達式的計算。是怎麼應用的？表達式計算用的是哪種表達方式？有什麼好處?
3. 字元串匹配演算法：樸素的匹配演算法、KMP演算法。
4. 二叉樹前序、中序、後序遞歸遍歷演算法。二叉樹前序非遞歸遍歷演算法。
5. 堆，建堆演算法，堆的插入和刪除演算法，堆排序。
6. 哈希。哈希函數的有哪些種？余數的取法？ 處理沖突的方法？ 閉散列方法有哪些？
7. 二叉搜索樹的搜索、插入、刪除。時間復雜度。
8. 二叉平衡樹的插入結點的原理，有哪幾種旋轉方式？分別適用於哪種情況。分析二叉平衡樹的時間復雜度。
9. 紅黑樹的定義，紅黑樹的性能分析和與二叉平衡樹的比較。
10. 圖有哪些儲存表示。
11. 鏈表插入排序、鏈表歸並排序。
12. 常見的有哪幾種排序演算法，試比較其時間復雜度，以及是否穩定，及各自使用的情形。
13. 常用分配排序有哪幾種？ 基數排序的定義，分類及原理。
14. 外部排序的過程。
15. B樹、B+樹、Trie的概念及用途，添加刪除結點的原理。
❷ 經典筆試面試知識整理，數據結構與演算法(代碼演示)
題目描述：
在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。
輸入描述: array： 待查找的二維數組 target：查找的數字
輸出描述:
查找到返回true，查找不到返回false
題目描述：
請實現一個函數，將漏祥一個字元串中的空格替換成「%20」。例如，當字元串為We Are Happy.則經過替換之後的字元串為We%20Are%20Happy。
題目描述： 輸入一個鏈表，從尾到頭列印鏈表每個節點的值。
輸入描述： 輸入為鏈表的表頭
輸出描述： 輸出為需要列印的「新鏈表」的表頭
題目描述：
輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。
例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹並返回。
題目描述：
把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個遞增排序的數組的一喊搜鉛個旋轉，輸出旋轉數組的最小元素。
例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1。 NOTE：給出的所有元素都大於0，若數組大小為0，請返回0。
1、題目描述：
大家都知道斐波那契數列，現在要求輸入一個整數n，請你輸出斐波那契數列的第n項。n<=39
2、題目描述：
一隻青蛙一次可以跳上1級台階，也可以跳上2級。求該青蛙跳上一個n級的台階總共有多少種跳法。
3、題目描述：
一隻青蛙一次可以跳上1級台階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的台階總共有多少種跳法。
4、題目描述：
我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個2*1的小矩形無重疊地覆蓋一個2*n的大矩形，總共有多少種方法？
1、題目描述：
輸入一個整數，輸出該數二進製表示中1的個數。其中負數用補碼表示。
2、題目描述：
給定一個double類型的浮點數base和int類型的整數exponent。求base的exponent次方。
題目描述：
輸入一個整數數組，實現一個函數來調整鄭好該數組中數字的順序，使得所有的奇數位於數組的前半部分，所有的偶數位於位於數組的後半部分，並保證奇數和奇數，偶數和偶數之間的相對位置不變。
題目描述：
用兩個棧來實現一個隊列，完成隊列的Push和Pop操作， 隊列中的元素為int類型。
題目描述：
輸入一個鏈表，輸出該鏈表中倒數第k個結點。
❸ 面試經典數據結構和演算法匯總
如果說數據結構是骨架，那麼演算法就是靈魂。沒了骨架，靈魂沒有實體寄託；沒了靈魂，骨架也是個空殼。兩者相輔相成，缺一不可，在開發中起到了砥柱中流的作用。
現在我對各種數據結構和演算法做一總結，對比一下它們的效率
1.數據結構篇
1. 如果讓你手寫個棧和隊列，你還會寫嗎？
2. 開發了那麼多項目，你能自己手寫個健壯的鏈表出來嗎？
3. 下次面試若再被問到二叉樹，希望你能對答如流！
4. 面試還在被紅-黑樹虐？看完這篇輕松搞定面試官 ！
2.排序演算法篇
1. 幾個經典的基礎排序演算法，你還記得嗎？
2. 手把手教你學會希爾排序，很簡單！
3. 快速排序演算法到底有多快？
4. 五分鍾教你學會歸並排序
5. 簡單說下二叉樹排序
6. 學會堆排序只需要幾分鍾
7. 圖，這個玩意兒竟然還可以用來排序！
掌握了這些經典的數據結構和演算法，面試啥的基本上沒什麼問題了，特別是對於那些應屆生來說。接下來再總結一下不同數據結構和演算法的效率問題，做一下對比，這也是面試官經常問的問題。
數據結構常用操作效率對比：
常用排序演算法效率的對比：
關於經典的數據結構和演算法，就總結到這，本文建議收藏，利用等公交、各種排隊之時提升自己。這世上天才很少，懶蛋卻很多，你若對得起時間，時間便對得起你。