1. 什么是時間復雜度？O（n）的O代表了什么？
答：時間復雜度是指執(zhí)行算法所需要的計算工作量，可以用于描述一個程序的規(guī)模。O（n）中的O表示的是最壞情況下的時間復雜度。

2. 時間復雜度的量級排序是什么？
答：O（logn）< O（n）< O（nlogn）< O（n^2）< O（2^n）< O（n?。?/p>

3. 順序存儲與鏈式存儲是什么？他們各自的優(yōu)缺點是什么？
答：順序存儲結構是一種地址空間連續(xù)、支持隨機訪問的線性表結構，優(yōu)點是支持隨機訪問，缺點是插入或刪除某個元素需要移動大量的元素；鏈式存儲是不要求連續(xù)地址空間，只需要在邏輯上通過指針進行相連的線性表結構，優(yōu)點是插入與刪除元素簡單，缺點是不支持隨機訪問。

4. 為什么循環(huán)隊列要犧牲一個空間？
答：在循環(huán)隊列中通常有隊頭指針和隊尾指針，其中隊頭指針指向隊列中的第一個元素，隊尾指針指向最后一個元素的下一個位置。如此一來在隊列執(zhí)行判空和判滿的操作時，判定條件都是頭指針等于尾指針。此時通過犧牲一個空間，可以將兩種操作分開：判空時條件是頭指針等于尾指針，判滿時條件是（rear+1）% size == front。
用于區(qū)分判滿和判空的類似操作還可以是維護一個size變量來存儲隊列元素的個數(shù)，或者設定一個flag變量，用于表示最后一次操作是插入還是刪除。當front==rear時，若最后一次操作是插入，則代表隊滿；如果是刪除，則代表隊空。

5. 有一個循環(huán)隊列Q，編號為0到n-1，頭尾指針分別是f與r，求當前隊列中的元素個數(shù)？
答：（f-r+n）% n。

6. 介紹一下KMP算法？
答：KMP算法是一種字符串匹配算法，通常用于查找文本串S中模式串P出現(xiàn)的位置。相比于樸素的字符串匹配算法中，匹配失敗需要主串和模式串同時回溯的做法，KMP只需要回溯模式串而不需要回溯主串，提高查找效率。KMP算法的實現(xiàn)需要借助于next數(shù)組，該數(shù)組記錄了當匹配失敗情況發(fā)生時，模式串需要回溯到什么位置開始重新匹配，其本質是模式串子串的最長相同前后綴。
Next數(shù)組的計算流程如下：初始化next數(shù)組為模式串的大小，初始化i與j指針為0與-1，當j==-1或者next[i]==next[j]時，i與j同時加1，此時j代表的是已經(jīng)匹配了多長的前后綴，即next[i] = j；如果不滿足該條件，則j回溯，j = next[j]，并循環(huán)知道將next數(shù)組填充完畢。
匹配流程如下：初始化i與j指針為-1，i指針指向主串，j指針指向模式串，進行與樸素匹配類似的操作。唯一的不同是，當主串的第i個字符不等于模式串的第j個字符時，i不用回溯，而只需要將j=next[j]便可繼續(xù)進行匹配，直到j指向模式串最后一個字符之后則代表匹配成功，否則匹配失敗。

7. 滿二叉樹與完全二叉樹的區(qū)別？
答：滿二叉樹即對于一顆高為h的二叉樹，結點個數(shù)為2^h-1的二叉樹，表現(xiàn)為除了最后一層葉子結點之外，根節(jié)點以及分支結點都有兩個孩子，即每一層都是滿的。
而完全二叉樹則是在滿二叉樹的基礎上，在最后一層從右往左依次刪除一定數(shù)量的葉子結點所形成的二叉樹。完全二叉樹的特點是葉子結點只出現(xiàn)在倒數(shù)第一和第二層，且如果有分支結點僅有一個孩子，那只能是左孩子。

8. 二叉排序樹（查找樹）與二叉平衡樹的區(qū)別？
答：二叉排序樹即BST，其每一個結點都有用于排序的關鍵碼，結點左子樹的所有結點的關鍵碼都小于當前結點的關鍵碼，而所有右子樹的關鍵碼都大于該結點的關鍵碼。對二叉排序樹進行中序遍歷，即可以得到從小到大有序的關鍵碼序列。它利用了二分的思想，可以快速查找到關鍵碼，查找效率為O（nlog2n）。
二叉平衡樹是一種特殊的二叉排序樹，它滿足對于樹上的任意一個結點，其左子樹的深度與右子樹的深度之差的絕對值不超過1。平衡因子可以用于描述二叉平衡樹，平衡因子是某個結點的左子樹深度與右子樹深度之差，對于一棵二叉平衡樹，其任意結點的平衡因子只能是-1，0或1。

9. 二叉排序樹的查找、插入與刪除操作過程是什么？
答：查找從根節(jié)點開始，如果要查找的關鍵碼大于當前關鍵碼，則下一個查找的結點為根節(jié)點的右子樹，反之則是左子樹。再以新節(jié)點為根，重復以上的查找步驟，直到查到得到匹配的關鍵碼為止。
插入操作則是基于查找操作進行，查找合適的位置進行插入。該合適的位置指的是按照查找步驟進行到的葉子節(jié)點處，若欲插入的關鍵碼大于該葉子結點，則插入為右孩子，反之為左孩子。插入的結點必須是葉子結點。若開始樹空，則直接成為根節(jié)點；若欲插入的關鍵碼已存在，則插入失敗。二叉樹的構造過程也是不斷插入的過程。
刪除操作同樣是基于查找操作，首先查找到欲刪除的結點。此時，刪除結點通常包括三種情況：① 若刪除的結點是葉子結點，則可以直接將結點刪去；② 若刪除的結點只有左孩子或者右孩子，則用它的孩子代替它；③ 若刪除的結點有左右孩子，則可以尋找其中序遍歷的直接前驅或者直接后繼代替它，再刪去該直接前驅或直接后繼。具體做法是：尋找刪去結點的左子樹的右右右孩子直到右孩子為空，即為直接前驅，或者尋找右子樹的左左左孩子直到左孩子為空，即為直接后繼。替代之后，再按照①②情況對直接前驅或后繼進行刪除。

10. 二叉平衡樹的插入與刪除過程（對平衡二叉樹的調整）？
答：平衡二叉樹的插入與刪除操作與二叉搜索樹相同，若出現(xiàn)不平衡現(xiàn)象，則需要對其進行調整。出現(xiàn)不平衡現(xiàn)象則意味著出現(xiàn)某結點的平衡因子大于1或者小于-1的情況，此時需要查找最小不平衡點，即距離插入結點最近的平衡因子大于1或者小于-1的結點，對其進行調整，調整思路分為以下四種情況：
① 插入結點位于最小不平衡點的左孩子的左子樹中（LL型）：利用扁擔原理，以最小不平衡點的左孩子為支撐進行右旋。代碼操作為：最小不平衡點的左指針指向其左孩子的右孩子，其左孩子的右指針指向最小不平衡點，再將其左孩子的父節(jié)點更換為最小不平衡點的父節(jié)點。
② 插入結點位于最小不平衡點的右孩子的右子樹中（RR型）：與LL型類似進行左旋。
③ 插入結點位于最小不平衡點的左孩子的右子樹中（LR型）：先進行左旋，再進行右旋。按照RR型的調整方式對最小不平衡點的左孩子進行調整使其變成LL型，再對最小不平衡點進行LL型的調整方式。
④ 插入結點位于最小不平衡點的右孩子的左子樹中（RL型）：與LR型類似先進行右旋再進行左旋。

11. 什么是哈夫曼樹？
答：哈夫曼樹又稱為最優(yōu)二叉樹，其特點是，給定一組帶權的葉子結點，若構造所得到的二叉樹擁有最小的帶權路徑長度WPL，則稱該二叉樹為一棵哈夫曼樹。構造哈夫曼樹的具體過程是：將帶權葉子結點并入一個集合，首先在集合中挑選出兩個權值最小的葉子結點進行合并（值相加）得到新的結點加入集合，再將兩個被選中的結點剔除出集合。在樹的構造上，將這兩個結點作為葉子結點銜接到合并而成的新結點上。重復以上過程直到集合中只有一個元素，哈夫曼樹則完成構造。
哈夫曼樹的應用是哈夫曼編碼，其特點是消除了編碼前綴相同的二義性。特別的，在哈夫曼編碼中，只有哈夫曼樹的葉子結點可以進行編碼。

12. 樹有什么存儲結構？
答：對于普通的樹來說，存儲結構通常分順序存儲與鏈式存儲，并且再細分為以下三種存儲結構：① 雙親表示法：這是一種順序存儲結構，以順序表為載體，每個結點有數(shù)據(jù)域和雙親位。其中，雙親位存儲的數(shù)據(jù)是該結點的父節(jié)點所存儲的下標；② 孩子表示法：這是一種順序存儲結構與鏈式存儲結構的結合，每個結點有數(shù)據(jù)域和第一個孩子指針域，以鏈表的形式存儲該結點所有孩子的下標數(shù)據(jù)；③ 孩子兄弟表示法：這是一種鏈式存儲結構，每個結點有兩個指針域，一個是指向自己的第一個孩子結點，另一個則指向自己的第一個右兄弟。
而對于二叉樹來說，也可以分為順序存儲與鏈式存儲結構。① 順序存儲結構中，按照二叉樹層序遍歷的順序將結點存儲于順序表中，特別注意空節(jié)點也需要占有位置。若某結點下標為i，則其左孩子下標為2i，右孩子下標為2i+1，父節(jié)點下下標為i/2向下取整。該存儲結構適合存儲完全二叉樹；② 鏈式存儲結構中，每個結點通常一個數(shù)據(jù)域與兩個指針域，分別指向自己的左孩子和右孩子。而為了充分利用左右孩子指針，可以將左孩子指向自己的前序、中序或后序遍歷的直接前序，右孩子指向直接后繼，從而形成二叉線索樹，方便查找。

13. B樹和B+樹的區(qū)別？
答：B樹是一種多路平衡查找樹。首先，多路是因為對于一棵m叉B樹，每個結點最多有m棵子樹，并且結點有m-1個關鍵字。關鍵字的左子樹的關鍵字都小于當前，右子樹的關鍵字都大于當前。而為了保持較高的查找效率，B樹的高度不能太高，因此限定除了根節(jié)點以外（根節(jié)點至少要有一個關鍵碼，即要有兩個分支），所有結點的關鍵碼個數(shù)不能少于m除以2向上取整再減1個。而平衡是因為B樹是一棵高平衡樹，所有結點的平衡因子都為0，葉子結點均在最后一層，倒數(shù)第二層稱為終端結點。
B+樹與B樹有所不同，主要有以下幾點：① B+樹的結點關鍵碼個數(shù)與結點的子樹個數(shù)相同，而B樹中關鍵碼個數(shù)比子樹個數(shù)少1； ② B+樹的關鍵碼存儲的是其對應子結點中關鍵碼的最大值，利用了分塊查找的思想，而B樹則是利用了二分查找的思想； ③ B+樹的倒數(shù)第二層稱為索引結點，通過指針彼此連接，而B樹的倒數(shù)第二層是終端結點，沒有相互連接； ④ B+樹的結點不存儲記錄，記錄只存儲在最后一層的葉子結點中，因此查找結束通常發(fā)生在葉子結點，而B樹的每個結點都存儲記錄，因此查找結束可以發(fā)生在任何結點。 ⑤ 由于B+樹的特性，其可以實現(xiàn)范圍查找（通過索引結點的索引遍歷），并且查找速度穩(wěn)定，相反B樹不能實現(xiàn)范圍查找（每次都需要從頭開始查找），速度不穩(wěn)定。

14. B樹和B+樹在數(shù)據(jù)庫中的應用？
答：在數(shù)據(jù)庫查詢中，通常以樹形結構來存儲數(shù)據(jù)。B樹或者B+樹中的每一個關鍵字，代表一個相應的磁盤塊。系統(tǒng)首先從根節(jié)點讀取磁盤塊到內(nèi)存，再按照內(nèi)存中讀取的分塊信息繼續(xù)讀取子樹中關鍵字所代表的磁盤塊，知道尋找得到關鍵字，再讀出記錄。因此，樹的高度意味著需要進行多少次I/O操作，高度越少，需要進行的I/O次數(shù)相應越少。
如果使用AVL樹存儲數(shù)據(jù)，當數(shù)據(jù)量大的時候，AVL樹的高度會變得非常大。而B樹與B+樹一個結點可以存儲多個值，讀取磁盤時是將整個結點讀取到內(nèi)存再進行處理，因此可以提升I/O效率。而B樹的缺點是不利于范圍查找，每次查找需要多次從根節(jié)點開始，B+樹由于有索引結點的存在，并且按照索引值從小到大進行排序，只在葉子結點存儲記錄，因此可以通過鏈表的遍歷實現(xiàn)范圍查找。

15. 你了解紅黑樹嗎？能不能簡單聊聊紅黑樹？

16. 介紹一下最小生成樹算法？
答：首先講一下我對于最小生成樹的理解。生成樹是一種特殊的圖，它通過普通的圖結構刪減邊得到，沒有環(huán)路，但每個結點相互連通。而最小生成樹就是找到路徑權重之和最小的那個生成樹。最小生成樹算法有普里姆和科魯茲卡爾算法。
普里姆算法：首先在圖中取一個結點加入空集中形成一個集合，并且挑選與該結點相連接權值最小的結點加入集合，再繼續(xù)尋找一個與集合中結點相連接權值最短的結點加入集合。循環(huán)以上步驟直到圖中所有結點都加入集合，則完成最小生成樹的構建。時間復雜度為O(n^2)。
科魯茲卡克算法：首先將圖中所有的變從小打到進行排序，然后從小邊開始尋找，找到一條合適的邊加入圖中。合適的邊指的是在該邊加入圖中之前，該邊兩端的結點集合并不連通。重復以上過程直到圖連通，則完成最小生成樹的構建。判斷是否屬于同一個連通集通常使用并查集算法，時間復雜度為O(log2n)，由于算法需要進行n次搜索，因此總時間復雜度為O(nlog2n)。

17. 介紹一下最短路徑算法？
答：最短路徑算法即求圖中兩點之間的最短路徑問題，通常有BFS算法、迪杰斯特拉算法和弗洛伊德算法，其中BFS只能處理無權圖，迪杰斯特拉算法可以進一步解決帶權圖問題，弗洛伊德可以進一步解決帶負權邊圖問題，但是他們都不能解決帶負權回路圖問題。
BFS即廣度優(yōu)先搜索，通過隊列來實現(xiàn)，首先將單原點加入隊列。每次循環(huán)將隊列中隊頭元素彈出，并且將與該元素所代表的結點相鄰的結點加入隊列，直到隊列為空。每次循環(huán)代表距離加一，BFS可以找出單源點到其他結點的路徑長度，取最小即為最短路。
迪杰斯特拉應用了貪心的思想，通常解決單源點問題。首先將源點直接相連的結點作為候選結點，不直接相連的結點將距離標注為無窮。此時在所有候選節(jié)點中選出距離源點最短的結點，作為下一次迭代的中間結點，并對于中間結點直接相連的結點的路徑長度進行更新，即“若源點到中間結點的距離加中間結點到該結點的距離<源點到該節(jié)點的距離”則進行更新。重復以上過程，直到所有結點完成更新。其時間復雜度為O(n^2)。
弗洛伊德則是應用了動態(tài)規(guī)劃的思想，通常解決多源點問題。首先對圖進行初始化，遍歷圖中所有結點，將與結點直接相鄰的結點之間的邊標注上原有的權值，而到不相鄰結點的權值標注為無窮。算法將遍歷圖中所有結點，每次將遍歷到的結點作為中間結點，并且對所有結點之間的權值進行更新，即“若結點1到結點2的距離>結點1到中間結點再到結點2的距離”則進行更新。由于需要進行三層遍歷，其實間復雜度為O(n^3)。

18. 最小生成樹算法以及最短路徑算法的優(yōu)化？
答：最小生成樹算法中的普里姆算法與科魯茲卡爾算法都需要排序，前者需要對點到集合的路徑進行排序，而后者需要對邊進行排序，因此二者都可以利用堆進行優(yōu)化，通過訪問堆頂元素以及堆調整來實現(xiàn)快速訪問最短邊。與此類似，最短路徑中的迪杰斯特拉也可以利用堆進行優(yōu)化，時間復雜度可以下降為O(nlog2n)。（在更新最短路徑的時候會破壞原有的堆結構，此時應該對被破壞的結點進行上浮到合適的位置）

19. 介紹一下拓撲排序？
答：拓撲排序即一種生成圖的拓撲序列的方式，用于檢查圖中是否存在環(huán)，或者應用于找出事件發(fā)生的先后順序。拓撲排序的具體步驟是：利用?；蛘哧犃?，將圖中入度為0的結點入棧，同時在圖中將該結點進行刪除，再將刪除該結點之后入度變?yōu)?的結點進行入棧，重復以上順序即可獲得拓撲序列。若算法結束時，序列長度不等于圖中結點的數(shù)量，則說明圖中存在環(huán)，即無法描述先后順序。

20. 介紹一下AOE網(wǎng)？
答：AOE網(wǎng)是在帶權有向圖中，以頂點代表時間，以有向邊代表活動，以邊上的權值代表完成該活動的開銷或所需時間的網(wǎng)絡。從源點到匯點的有向路徑可能有多條，在所有路徑中，具有最大路徑長度的路徑稱為關鍵路徑，關鍵路徑上的活動稱為關鍵活動。完成整個工程的最短時間就是關鍵路徑的長度，若關鍵活動不能按時完成，則整個工程的完成時間就會延長。

21. 哈希表的概念？構造方法？解決沖突的方式？裝填因子？
答：哈希表的概念：散列表（Hash table，也叫哈希表），是根據(jù)關鍵碼值(Key value)而直接進行訪問的數(shù)據(jù)結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度；
哈希表的構造方法：哈希表的構造方法一般有直接定址法、數(shù)字分析法和平方取中法（取關鍵字平均值的中間幾位作為散列地址）；
解決沖突的方法：開放定址法（線性探測、平方探測）、拉鏈法、再哈希法；
裝填因子：哈希表中記錄長度 / 哈希表長度。

22. 你了解的排序算法有什么？
答：首先是插入排序方法，包括插入排序與希爾排序。其次是選擇排序方法，包括簡單選擇排序和堆排序。而后是交換排序方法，包括冒泡排序和快速排序。最后是其他類排序，例如歸并排序、基數(shù)排序、敗者樹、外部排序等。
不同排序方法的穩(wěn)定性與時間復雜度不同：

23. 快速排序的復雜度分析？
答：快速排序的時間復雜度應該為O(n*遞歸深度)，而遞歸深度則是由遞歸樹的高度決定?？焖倥判蛑械倪f歸樹是一棵二叉樹，因此其最大的高度是n（即所有序列都有序時），最低高度是log2n向下取整+1，因此快速排序的最好時間復雜度為O(nlog2n)，最壞時間復雜度為O(n^2)。

24. 大、小根堆的建堆過程？堆排序的過程？
答：以大根堆為例，首先以數(shù)組的形式存儲堆，因為堆是一顆完全二叉樹，因此對于下標為i的結點，其左孩子的下標為2i+1，右孩子的小標為2i+2。首先將初始堆（待排序序列）按照順序存儲在數(shù)組中。初建堆的過程將從最后一個分支節(jié)點開始，若結點的值小于其左孩子與右孩子中較大的一個，則與該孩子結點進行交換，直到無法再交換為止。然后再對倒數(shù)第二個分支結點進行調整，直到完成對根節(jié)點的調整即完成大根堆的建堆過程。
若需要進行堆排序，則將根節(jié)點與最后一個葉子結點進行交換，并將最后一個葉子結點移除序列（該結點即為序列中最大的結點），而后對新的根節(jié)點進行調整形成堆結構，重復上述過程直到所有結點都移除堆結構即可得到已排序的序列。

25. 歸并排序的最壞時間復雜度優(yōu)于快排，為什么我們還是選擇快排？
答：快排是一個in-place排序算法，而歸并排序是一個out-place排序算法，期間存在O（n）的空間復雜度，這就意味著堆內(nèi)存的拷貝釋放等底層操作，當排序數(shù)量大時，這些時間開銷將會增大。另一個原因是，快排通常情況下多為平均時間復雜度，最壞的情況出現(xiàn)的概率往往很小。文章來源地址http://www.zghlxwxcb.cn/news/detail-535853.html

到了這里，關于計算機保研面試常見問題（408數(shù)據(jù)結構簡答題）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！