數據結構演算法面試題

1. 演算法面試通關40講 覃超 Leetcode 題目總結（未完待續）

主要是自己收集的題目，正在學習王爭老師的數據與演算法結構之美和覃超老師的演算法面試通關四十講，兩位老師推薦很經典的面試題。所以為了方便自己，在這里做一個匯總。如果對你有幫助那當然好，或者也可以看參考資料，裡面有很多優秀的Github的資源。

參考資料
演算法復雜度查看： https://www.bigocheatsheet.com/
C語言解法推薦： https://github.com/begeekmyfriend/leetcode
Java解法推薦： https://github.com/azl397985856/leetcode
數據結構與演算法之美（王爭）（有各種語言的版本）： https://github.com/wangzheng0822/algo
Github 40K star leetcode： https://github.com/azl397985856/leetcode
Github 13K star Leetcode： https://github.com/haoel/leetcode
Github 63K star 用動畫的形式呈現解LeetCode題目的思路： https://github.com/MisterBooo/LeetCodeAnimation
python 解法： https://github.com/qiyuangong/leetcode
其他解法： https://github.com/qiyuangong/leetcode

06|面試題：反轉一個單鏈表&判斷鏈表是否有環

數據與演算法結構之美：
21 Merge Two Sorted Lists 【 C 】【 python 】
刪除鏈表倒數第 n 個結點 【 Leetcode 的解題 】
求鏈表的中間結點 Middle of the Linked List

20 Valid Parentheses
232 Implement Queue using Stacks 【 C 】【 My C solution 】
225 Implement Stack using Queues 【 C 】

703 Kth Largest Element in a Stream
239 Sliding Window Maximum

242 Valid Anagram
1 Two Sum 【 C 】
15 3Sum
18 4Sum

98 Validate Binary Search Tree
235 Lowest Common Ancestor of a Binary Search Tree
236 Lowest Common Ancestor of a Binary Tree

50 Pow(x, n)
169 Majority Element

122 Best Time to Buy and Sell Stock II

冒泡排序，選擇排序，插入排序，供參考：【 C 】

(未完待續，大概等我做完上面這些就可以繼續補充剩下的了吧）

2. 資料庫經典筆試題和面試題答案

如下這些有關資料庫知識考查的經典筆試題，非常全面，對計算機專業畢業生參加筆試會很有幫助，建議大家收藏。
一、選擇題

1. 下面敘述正確的是___c___。

A、演算法的執行效率與數據的存儲結構無關

B、演算法的空間復雜度是指演算法程序中指令(或語句)的條數

C、演算法的有窮性是指演算法必須能在執行有限個步驟之後終止

D、以上三種描述都不對

2. 以下數據結構中不屬於線性數據結構的是___c___。

A、隊列B、線性表C、二叉樹D、棧

3. 在一棵二叉樹上第5層的結點數最多是__b____。2的(5-1)次方

A、8 B、16 C、32 D、15

4. 下面描述中，符合結構化程序設計風格的是___a___。

A、使用順序、選擇和重復(循環)三種基本控制結構表示程序的控制邏輯

B、模塊只有一個入口，可以有多個出口

C、注重提高程序的執行效率 D、不使用goto語句

5. 下面概念中，不屬於面向對象方法的是___d___。

A、對象 B、繼承 C、類 D、過程調用

6. 在結構化方法中，用數據流程圖(DFD)作為描述工具的軟體開發階段是___b___。

A、可行性分析 B、需求分析 C、詳細設計 D、程序編碼

7. 在軟體開發中，下面任務不屬於設計階段的是__d____。

A、數據結構設計 B、給出系統模塊結構 C、定義模塊演算法 D、定義需求並建立系統模型

8. 資料庫系統的核心是___b___。

A、數據模型 B、資料庫管理系統 C、軟體工具 D、資料庫

9. 下列敘述中正確的是__c____。

A、資料庫是一個獨立的系統，不需要操作系統的支持

B、資料庫設計是指設計資料庫管理系統

C、資料庫技術的根本目標是要解決數據共享的問題

D、資料庫系統中，數據的物理結構必須與邏輯結構一致

10. 下列模式中，能夠給出資料庫物理存儲結構與物理存取方法的是___a___。

A、內模式 B、外模式 C、概念模式 D、邏輯模式

11. Visual FoxPro資料庫文件是___d___。

A、存放用戶數據的文件 B、管理資料庫對象的系統文件

C、存放用戶數據和系統的文件 D、前三種說法都對

12. SQL語句中修改表結構的命令是___c___。

A、MODIFY TABLE B、MODIFY STRUCTURE

C、ALTER TABLE D、ALTER STRUCTURE

13. 如果要創建一個數據組分組報表，第一個分組表達式是"部門"，第二個分組表達式是"性別"，第三個分組表達式是"基本工資"，當前索引的索引表達式應當是__b____。

A、部門+性別+基本工資 B、部門+性別+STR(基本工資)

C、STR(基本工資)+性別+部門 D、性別+部門+STR(基本工資)

14. 把一個項目編譯成一個應用程序時，下面的敘述正確的是___a___。

A、所有的項目文件將組合為一個單一的應用程序文件

B、所有項目的包含文件將組合為一個單一的應用程序文件

C、所有項目排除的文件將組合為一個單一的應用程序文件

D、由用戶選定的項目文件將組合為一個單一的應用程序文件

15. 資料庫DB、資料庫系統DBS、資料庫管理系統DBMS三者之間的關系是_a___。

A、DBS包括DB和DBMS B、DBMS包括DB和DBS

C、DB包括DBS和DBMS D、DBS就是DB，也就是DBMS

16. 在"選項"對話框的"文件位置"選項卡中可以設置___b___。

A、表單的默認大小 B、默認目錄

C、日期和時間的顯示格式 D、程序代碼的顏色

17. 要控制兩個表中數據的完整性和一致性可以設置"參照完整性"，要求這兩個表_a_。

A、是同一個資料庫中的兩個表 B、不同資料庫中的兩個表

C、兩個自由表 D、一個是資料庫表另一個是自由表

18. 定位第一條記錄上的命令是___a___。

A、GO TOP B、GO BOTTOM C、GO 6 D、SKIP

19. 在關系模型中，實現"關系中不允許出現相同的元組"的約束是通過__b____。

A、候選鍵 B、主鍵 C、外鍵 D、超鍵

20. 設當前資料庫有10條記錄(記錄未進行任何索引)，在下列三種情況下，當前記錄號為1時;EOF()為真時;BOF()為真時，命令?RECN()的結果分別是___a___。

A、1,11,1 B、1,10,1 C、1,11,0 D、1,10,0

21. 下列表達式中結果不是日期型的是___c___。

A、CTOD("2000/10/01") B、{^99/10/01}+365

C、VAL("2000/10/01") D、DATE()

22. 只有滿足聯接條件的記錄才包含在查詢結果中，這種聯接為___c___。

A、左聯接 B、右聯接 C、內部聯接 D、完全聯接

23. 索引欄位值不唯一，應該選擇的索引類型為___b___。

A、主索引 B、普通索引 C、候選索引 D、唯一索引

24. 執行SELECT 0選擇工作區的結果是___b___。

A、選擇了0號工作區 B、選擇了空閑的最小號工作區

C、關閉選擇的工作區 D、選擇已打開的工作區

25. 從資料庫中刪除表的命令是___a___。

A、DROP TABLE B、ALTER TABLE C、DELETE TABLE D、USE

26. DELETE FROM S WHERE 年齡>60語句的功能是__b____。

A、從S表中徹底刪除年齡大於60歲的記錄

B、S表中年齡大於60歲的記錄被加上刪除標記

C、刪除S表 D、刪除S表的年齡列 1 2

3. 數據結構與演算法處理面試題

1、時針走一圈，時針分針重合幾次

2、N*N的方格紙,裡面有多少個正方形

3、2000萬個整數，找出第五十大的數字？

4、網路POI中如何試下查找最近的商家功能(提示：坐標鏡像+R樹)。

5、一個文件中有100萬個整數，由空格分開，在程序中判斷用戶輸入的整數是否在此文件中。說出最優的方法

6、兩個不重復的數組集合中，這兩個集合都是海量數據，內存中放不下，怎麼求共同的元素？

7、燒一根不均勻的繩，從頭燒到尾總共需要1個小時。現在有若干條材質相同的繩子，問如何用燒繩的方法來計時一個小時十五分鍾呢？

8、萬億級別的兩個URL文件A和B，如何求出A和B的差集C(提示：Bit映射->hash分組->多文件讀寫效率->磁碟定址以及應用層面對定址的優化)

9、怎麼在海量數據中找出重復次數最多的一個？

10、海量日誌數據，提取出某日訪問網路次數最多的那個IP。

11、在2.5億個整數中找出不重復的整數，注，內存不足以容納這2.5億個整數。

12、搜索引擎會通過日誌文件把用戶每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255位元組。

13、有一個1G大小的一個文件，裡面每一行是一個詞，詞的大小不超過16位元組，內存限制大小是1M。返回頻數最高的100個詞。

14、有10個文件，每個文件1G，每個文件的每一行存放的都是用戶的query，每個文件的query都可能重復。要求你按照query的頻度排序。

15、給定a、b兩個文件，各存放50億個url，每個url各佔64位元組，內存限制是4G，讓你找出a、b文件共同的url？

16、一個文本文件，大約有一萬行，每行一個詞，要求統計出其中最頻繁出現的前10個詞，請給出思想，給出時間復雜度分析。

17、騰訊面試題：給40億個不重復的unsigned int的整數，沒排過序的，然後再給一個數，如何快速判斷這個數是否在那40億個數當中？

18、100w個數中找出最大的100個數。

4. 面試經典數據結構和演算法匯總

如果說數據結構是骨架，那麼演算法就是靈魂。沒了骨架，靈魂沒有實體寄託；沒了靈魂，骨架也是個空殼。兩者相輔相成，缺一不可，在開發中起到了砥柱中流的作用。

現在我對各種數據結構和演算法做一總結，對比一下它們的效率

1.數據結構篇
1. 如果讓你手寫個棧和隊列，你還會寫嗎？
2. 開發了那麼多項目，你能自己手寫個健壯的鏈表出來嗎？
3. 下次面試若再被問到二叉樹，希望你能對答如流！
4. 面試還在被紅-黑樹虐？看完這篇輕松搞定面試官 ！

2.排序演算法篇
1. 幾個經典的基礎排序演算法，你還記得嗎？
2. 手把手教你學會希爾排序，很簡單！
3. 快速排序演算法到底有多快？
4. 五分鍾教你學會歸並排序
5. 簡單說下二叉樹排序
6. 學會堆排序只需要幾分鍾
7. 圖，這個玩意兒竟然還可以用來排序！

掌握了這些經典的數據結構和演算法，面試啥的基本上沒什麼問題了，特別是對於那些應屆生來說。接下來再總結一下不同數據結構和演算法的效率問題，做一下對比，這也是面試官經常問的問題。

數據結構常用操作效率對比：

常用排序演算法效率的對比：

關於經典的數據結構和演算法，就總結到這，本文建議收藏，利用等公交、各種排隊之時提升自己。這世上天才很少，懶蛋卻很多，你若對得起時間，時間便對得起你。

5. 常見面試演算法題2：二叉樹的最近公共父親節點

程序員面試中對數據結構的考察，除了單鏈表，考察最為頻繁的就是二叉樹了，而二叉樹的最近公共父節點又是較為常見的一道演算法題，博主年前面試vivo互聯網部門的時候就被考察過，下邊介紹下這道演算法題的思路和源碼。
兩個節點Node1和Node2的最近父節點可以用下邊的思路得到：
首先，當Node1位於Node2的左子樹或者右子樹時，則Node1和Node2的最近父節點為Node2;
否則，反之當Node2位於Node1的左子樹或者右子樹時，則Node1和Node2的最近父節點為Node1;
再否則，Node1和Node2的最近父節點為以包含Node1和Node2l兩個節點的最小子樹的根節點。
經過上邊的分析可以用遞歸的方法來解這道題，

6. iOS面試題12-數據結構演算法篇

《 2018 iOS面試題系列 》

        這里沒有圖啊，大家可以抽象一下。

        數據結構的存儲一般常用的有兩種 順序存儲結構 和 鏈式存儲結構

        發揮想像力啊。 舉個列子。數組。1-2-3-4-5-6-7-8-9-10。這個就是一個順序存儲結構 ，存儲是按順序的 舉例說明啊。 棧。做開發的都熟悉。棧是先進後出 ，後進先出的形式 對不對 ？！他的你可以這樣理解

        hello world 在棧裡面從棧底到棧頂的邏輯依次為 h-e-l-l-o-w-o-r-l-d 這就是順序存儲 再比如 隊列 ，隊列是先進先出的對吧，從頭到尾 h-e-l-l-o-w-o-r-l-d 就是這樣排對的

        再次發揮想像力 這個稍微復雜一點 這個圖片我一直弄好 ，回頭找美工問問，再貼上 例如 還是一個數組

        1-2-3-4-5-6-7-8-9-10 鏈式存儲就不一樣了 1(地址)-2(地址)-7(地址)-4(地址)-5(地址)-9(地址)-8(地址)-3(地址)-6(地址)-10(地址)。每個數字後面跟著一個地址 而且存儲形式不再是順序 ，也就說順序亂了，1（地址） 1後面跟著的這個地址指向的是2，2後面的地址指向的是3，3後面的地址指向是誰你應該清楚了吧。他執行的時候是 1(地址)-2(地址)-3(地址)-4(地址)-5(地址)-6(地址)-7(地址)-8(地址)-9(地址)-10(地址)，但是存儲的時候就是完全隨機的。明白了？！

        還是舉例子。理解最重要。不要去死記硬背 哪些什麼。定義啊。邏輯啊。理解才是最重要滴

二叉樹有五種表現形式

       二叉樹可以轉換成森林 樹也可以轉換成二叉樹。這里就不介紹了 你做項目絕對用不到

       數據結構大致介紹這么多吧。理解為主, 別死記，死記沒什麼用

從現在開始介紹演算法啊

       二叉樹這個比較麻煩 還有平衡二叉樹 有點繞 如果不懂二叉樹這一塊 你是百分之二百看不懂的

原文鏈接

7. 數據結構面試常見問題

數據結構面試常見問題

數據結構是計算機存儲、組織數據的方式。數據結構是指相互之間存在一種或多種特定關系的數據元素的集合。下面就是我整理的數據結構面試常見問題，一起來看一下吧。

數據結構面試常見問題 篇1

數據結構與演算法，這個部分的內容其實是十分的龐大，要想都覆蓋到不太容易。在校學習階段我們可能需要對每種結構，每種演算法都學習，但是找工作筆試或者面試的時候，要在很短的時間內考察一個人這方面的能力，把每種結構和演算法都問一遍不太現實。所以，實際的情況是，企業一般考察一些看起來很基本的概念和演算法，或者是一些變形，然後讓你去實現。也許看起來簡單，但是如果真讓你在紙上或者是計算機上快速地完成一個演算法，並且設計測試案例，最後跑起來，你就會發現會很難了。這就要求我們要熟悉，並牢固掌握常用的演算法，特別是那些看起來貌似簡單的演算法，正是這些用起來很普遍的演算法，才要求我們能很扎實的掌握，在實際工作中提高工作效率。遇到復雜的演算法，通過分析和扎實的基本功，應該可以很快地進行開發。

閑話少說，下面進入正題。

一.數據結構部分

1.數組和鏈表的區別。（很簡單，但是很常考，記得要回答全面）

C++語言中可以用數組處理一組數據類型相同的數據，但不允許動態定義數組的大小，即在使用數組之前必須確定數組的大小。而在實際應用中，用戶使用數組之前有時無法准確確定數組的大小，只能將數組定義成足夠大小，這樣數組中有些空間可能不被使用，從而造成內存空間的浪費。鏈表是一種常見的數據組織形式，它採用動態分配內存的形式實現。需要時可以用new分配內存空間，不需要時用將已分配的空間釋放，不會造成內存空間的浪費。

從邏輯結構來看：數組必須事先定義固定的長度（元素個數），不能適應數據動態地增減的情況，即數組的大小一旦定義就不能改變。當數據增加時，可能超出原先定義的元素個數；當數據減少時，造成內存浪費；鏈表動態地進行存儲分配，可以適應數據動態地增減的.情況，且可以方便地插入、刪除數據項。（數組中插入、刪除數據項時，需要移動其它數據項）。

從內存存儲來看：（靜態)數組從棧中分配空間（用NEW創建的在堆中）, 對於程序員方便快速,但是自由度小；鏈表從堆中分配空間, 自由度大但是申請管理比較麻煩.

1.從訪問方式來看：數組在內存中是連續存儲的，因此，可以利用下標索引進行隨機訪問；鏈表是鏈式存儲結構，在訪問元素的時候只能通過線性的方式由前到後順序訪問，所以訪問效率比數組要低。

2.鏈表的一些操作，如鏈表的反轉，鏈表存在環路的判斷（快慢指針），雙向鏈表，循環鏈表相關操作。

3.隊列（特殊的如優先順序隊列），棧的應用。（比如隊列用在消息隊列，棧用在遞歸調用中）

4.二叉樹的基本操作

二叉樹的三種遍歷方式（前序，中序，後序）及其遞歸和非遞歸實現，三種遍歷方式的主要應用（如後綴表達式等）。相關操作的時間復雜度。

5.字元串相關

整數，浮點數和字元串之間的轉換（atoi,atof,itoa）

字元串拷貝注意異常檢查，比如空指針，字元串重疊，自賦值，字元串結束符'/0'等。

二.演算法部分

1.排序演算法：

排序可以算是最基本的，最常用的演算法，也是筆試面試中最常被考察到的演算法。最基本的冒泡排序，選擇排序，插入排序要可以很快的用代碼實現，這些主要考察你的實際編碼能力。堆排序，歸並排序，快排序，這些演算法需要熟悉主要的思想，和需要注意的細節地方。需要熟悉常用排序演算法的時間和空間復雜度。

各種排序演算法的使用范圍總結：

（1）當數據規模較小的時候，可以用簡單的排序演算法如直接插入排序或直接選擇排序。

（2）當文件的初態已經基本有序時，可以用直接插入排序或冒泡排序。

（3）當數據規模比較大時，應用速度快的排序演算法。可以考慮用快速排序。當記錄隨機分布的時候，快排的平均時間最短，但可能出現最壞的情況，這時候的時間復雜度是O(n^2)，且遞歸深度為n,所需的棧空間問O(n)。

（4）堆排序不會出現快排那樣的最壞情況，且堆排序所需的輔助空間比快排要少。但這兩種演算法都不是穩定的，若要求排序時穩定的，可以考慮用歸並排序。

（5）歸並排序可以用於內排序，也可以用於外排序。在外排序時，通常採用多路歸並，並且通過解決長順串的合並，產生長的初始串，提高主機與外設並行能力等措施，以減少訪問外存額次數，提高外排序的效率。

2,查找演算法

能夠熟練寫出或者是上機編碼出二分查找的程序。

3.hash演算法

4.一些演算法設計思想。

貪心演算法，分治演算法，動態規劃演算法，隨機化演算法，回溯演算法等。這些可以根據具體的例子程序來復習。

5.STL

STL(Standard Template Library)是一個C++領域中，用模版技術實現的數據結構和演算法庫，已經包含在了C++標准庫中。其中的vecor,list,stack,queue等結構不僅擁有更強大的功能，還有了更高的安全性。除了數據結構外，STL還包含泛化了的迭代器，和運行在迭代器上的各種實用演算法。這些對於對性能要求不是太高，但又不希望自己從底層實現演算法的應用還是很具有誘惑力的。

數據結構面試常見問題 篇2

1. 什麼是數據結構？

數據結構是數據組織（存儲）和操作進行檢索和訪問的方式。它還定義了不同數據集相互關聯、建立關系和形成演算法的方式。

2. 描述數據結構的類型？

列表：鏈接到先前或/和後續數據項的相關事物的集合。

數組：所有相同的值的集合。

Records：欄位的集合，每個欄位都包含來自單一數據類型的數據。

樹：在分層框架中組織數據的數據結構。這種形式的數據結構遵循數據項插入、刪除和修改的順序。

表格：數據以行和列的形式保存。這些與記錄相當，因為數據的結果或更改反映在整個表中。

3. 什麼是線性數據結構？請舉例

如果數據結構的所有元素或數據項都按順序或線性順序排列，則數據結構是線性的。元素以非分層方式存儲，因此除了列表中的第一個和最後一個元素外，每個項目都有後繼者和前驅者。數組、堆棧、字元串、隊列和鏈表，都屬於線性數據結構。

4. 數據結構有哪些應用？

數值分析、操作系統、人工智慧、編譯器設計、資料庫管理、圖形、統計分析和模擬。

5、文件結構和存儲結構有什麼區別？

區別在於訪問的內存區域。存儲結構是指計算機系統內存中的數據結構，而文件結構是指輔助存儲器中的存儲結構。

6、什麼是多維數組？

多維數組的意思是指三維或者三維以上的數組。 三維數組具有高、寬、深的概念,或者說行、列、層的概念,即數組嵌套數組達到三維及其以上。是最常見的多維數組,由於其可以用來描述三維空間中的位置或狀態而被廣泛使用。

7. 什麼是鏈表數據結構？

這是最常見的數據結構面試問題之一，面試官希望你能給出全面的答案。嘗試盡可能多地解釋，而不是用一句話來完成你的答案！

它是一個線性數據結構或一系列數據對象，其中元素不存儲在相鄰的內存位置。元素使用指針鏈接以形成鏈。每個元素都是一個單獨的對象，稱為節點。每個節點有兩項：數據欄位和對下一個節點的引用。鏈表中的入口點稱為頭。如果列表為空，則頭部為空引用，最後一個節點具有對空的引用。

一個鏈表是一個動態的數據結構，其中節點的數量是不固定的，這樣的例子有擴大和縮小需求的能力。

它適用於以下情況：

我們處理未知數量的對象或不知道列表中有多少項目；

我們需要從列表中進行恆定時間的插入/刪除，就像在時間可預測性至關重要的實時計算中一樣；

不需要隨機訪問任何元素；

該演算法需要一個數據結構，無論對象在內存中的物理地址如何，都需要在其中存儲對象；

我們需要在列表中間插入項目，就像在優先隊列中一樣；

一些實現是堆棧和隊列、圖形、名稱目錄、動態內存分配以及對長整數執行算術運算

8.什麼是雙向鏈表？請舉例

它是鏈表的一種復雜類型（雙端 LL），其中一個節點有兩個鏈接，一個連接到序列中的下一個節點，另一個連接到前一個節點。這允許在兩個方向上遍歷數據元素。

舉例：

帶有下一個和上一個導航按鈕的音樂播放列表

具有 BACK-FORWARD 訪問頁面的瀏覽器緩存

瀏覽器上的撤消功能

9. 為什麼要做演算法分析？

一個問題可以使用多種解決演算法以多種方式解決。演算法分析提供對演算法所需資源的估計，以解決特定的計算問題。還確定了執行所需的時間和空間資源量。

演算法的時間復雜度量化了演算法運行所花費的時間，作為輸入長度的函數。空間復雜度量化了演算法佔用的空間或內存量，以作為輸入長度的函數運行。

;