1.算法的時間復(fù)雜度 ：

答：在程序中反復(fù)執(zhí)行的語句的執(zhí)行次數(shù)被稱為語句的頻度，時間復(fù)雜度就是所有語句頻度之和的數(shù)量級，而所有語句的頻度之和與程序最內(nèi)層循環(huán)的頻度是同一個數(shù)量級，所以算法的時間復(fù)雜度是最內(nèi)層循環(huán)的頻度的數(shù)量級

=補充：算法設(shè)計的步驟= ： 1.建立數(shù)據(jù)模型 2.確定數(shù)據(jù)結(jié)構(gòu)與算法 3.選用語言 4.調(diào)試并運行

2.空間復(fù)雜度 ：

答：程序在運行時所占的空間 直接插入排序的空間復(fù)雜度是O（1），遞歸的空間復(fù)雜度是O（n）

3.貪心算法、動態(tài)規(guī)劃和分治算法 ：

答：貪心算法是指從上到下，每次都求解局部最優(yōu)解的算法，特點是每次求解最優(yōu)解，但是最終的結(jié)果不一定是最優(yōu)，經(jīng)典例子是背包問題。

動態(tài)規(guī)劃是將一個大問題劃分成若干個子問題，問題之間存在重疊，從上到下，求解整體最優(yōu)解，每一次的求解會對下一次的問題造成影響，最終的最優(yōu)解不一定包含每次的最優(yōu)解，但是一定有部分最優(yōu)解。經(jīng)典例子是求最長子串。

分治算法是將一個大問題劃分成若干個和大問題相似的子問題，再對子問題進(jìn)行遞歸求解，最終合并得到最后的結(jié)果。特點是大問題的劃分與子問題相似，并且每個問題之間是相互獨立的。經(jīng)典例子是二路歸并排序、快速排序

4.數(shù)據(jù)的存儲結(jié)構(gòu) ：

答： （1）順序存儲：邏輯上相鄰的兩個元素的物理位置也相鄰。 優(yōu)點：能夠隨機存取。 缺點：插入刪除需要移動大量的元素，不方便。

（2）鏈?zhǔn)酱鎯Γ哼壿嬌舷噜彽膬蓚€元素的物理位置不一定相鄰，每個結(jié)點用一個指針來找到下一個結(jié)點的位置。 優(yōu)點：插入和刪除很方便 缺點：隨機讀取時不方便，需要從第一個結(jié)點開始遍歷

（3）索引存儲：在存儲時，還附加建立索引表，索引表中的每一項稱為索引項，索引項的一般形式是（關(guān)鍵字，地址） 優(yōu)點：檢索速度快 缺點：索引表占用存儲空間，并且插入和刪除一個數(shù)據(jù)時，對應(yīng)的索引項也要插入和刪除，會耗費較多的時間

（4）哈希存儲：通過函數(shù)，根據(jù)數(shù)據(jù)的元素的關(guān)鍵字計算該元素的地址 優(yōu)點：檢索、增加和刪除結(jié)點的操作比較快 缺點：可能會出現(xiàn)元素存儲單元的沖突，解決沖突又需要增加時間和空間的開銷

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【891587639】整理了一些個人覺得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書、實戰(zhàn)項目及代碼)??

5.循環(huán)比遞歸的效率一定高嗎 ？

答：循環(huán)和遞歸能夠?qū)崿F(xiàn)相互轉(zhuǎn)換，且各自有自己的優(yōu)缺點，判斷誰的效率高是沒有絕對的答案的。

遞歸： 優(yōu)點：代碼簡潔清晰、容易實現(xiàn) 缺點：當(dāng)遞歸次數(shù)很多時，需要增加額外的堆棧處理，有可能產(chǎn)生堆棧溢出的現(xiàn)象

循環(huán)： 優(yōu)點：結(jié)構(gòu)簡單，速度快，效率高 缺點：不容易理解，編寫復(fù)雜代碼時會比較困難

6.順序表和鏈表的比較 ：

答：順序表和鏈表可以從四個大的方向去比較。 （1）存取（讀?。┓绞剑喉樞虮砟軌螂S機讀取和順序讀取，而鏈表只能按順序讀取 （2）查找：如果是按值查找并且表無序時，順序表和鏈表的時間復(fù)雜度都是O（n），如果表有序，則可以用折半查找法，時間復(fù)雜度是O（nlog2n）；如果是按序號查找，則順序表支持隨機查找，時間復(fù)雜度是O（1），而鏈表的時間復(fù)雜度是O（n） （3）插入和刪除：順序表插入和刪除需要移動大量的元素，時間復(fù)雜度是O（n），鏈表的插入和刪除只需要修改指針的位置，時間復(fù)雜度是O（1） （4）空間分配：順序表的空間分配分為靜態(tài)分配和動態(tài)分配，靜態(tài)內(nèi)存分配時，很容易導(dǎo)致內(nèi)存溢出或者是浪費，而動態(tài)內(nèi)存分配時，有時候不存在一大塊連續(xù)的存儲空間，導(dǎo)致分配失敗，并且需要移動大量的元素，效率低。 而鏈表是直接在需要的時候申請內(nèi)存，只要有內(nèi)存就能夠分配，操作靈活、高效。

7.頭指針和頭結(jié)點的區(qū)別：

答：頭指針是指在第一個結(jié)點之前的指針，它是一個鏈表存在的標(biāo)志，是必須存在必不可少的。 頭結(jié)點是第一個結(jié)點之前的結(jié)點，它是為了方面在第一個結(jié)點之前進(jìn)行元素的插入和刪除操作，它不是必須的，并且數(shù)據(jù)域也可以不存放信息。

8.棧和隊列的區(qū)別 ：

答：棧是只能在一端進(jìn)行插入和刪除的線性表，插入和刪除都在棧頂進(jìn)行，它的特點是“先進(jìn)后出”。常用于瀏覽器的回退或者是括號的匹配問題，遞歸問題，但是遞歸問題要注意堆棧的溢出現(xiàn)象

隊列是在一端插入在另一端刪除的線性表，插入的那端是隊尾，刪除的那端是隊首，特點是“先進(jìn)先出”，在層次遍歷和BFS算法、狄杰斯特拉算法中使用到

9.共享棧 ：

答：利用棧底位置不變的特性，讓兩個順序棧共享同一個一維數(shù)組空間，將兩個棧的棧底分別設(shè)在共享空間的兩端，兩個棧頂向共享空間延伸。

10.如何區(qū)分循環(huán)隊列是隊空還是隊滿 ？

答：有兩種區(qū)分方式： 第一種：犧牲一個單元來區(qū)分隊空和隊滿 隊空的標(biāo)志是 隊首指針 = = 隊尾指針； 隊滿的標(biāo)志是（隊尾指針+1）%maxsize ==隊首指針

第二種： 類型中增設(shè)表示元素數(shù)據(jù)的內(nèi)存單元 隊空：元素的個數(shù)為0 隊滿：元素的個數(shù)為Maxsize

11.棧在括號匹配中的算法思想 ：

答：（1）如果是左括號，則入棧 （2）如果是右括號，則判斷當(dāng)前棧是否為空，如果為空，則不匹配，不為空，則看是否與棧頂?shù)淖罄ㄌ柶ヅ?，如果匹配，則棧頂元素出棧 （2）最終所有的元素都進(jìn)棧和出棧完畢，檢查棧是否為空，如果不為空，則說明還有多余的左括號沒有匹配，因此括號匹配失敗，如果為空，則括號匹配成功。

12.棧在后綴表達(dá)式求值的算法思想 ：

答：掃描表達(dá)式的每一項 （1）如果是操作數(shù)，則進(jìn)棧 （2）如果是運算符，則從棧中退出兩個元素，進(jìn)行出棧，并且將得到的結(jié)果入棧 （3）表達(dá)式的所有項都掃描完后，最后棧頂存放的元素就是最終的結(jié)果。

13.棧在遞歸中的應(yīng)用 ：

答：若在一個函數(shù)、一個過程或者一個數(shù)據(jù)結(jié)構(gòu)的定義中直接或者間接的調(diào)用了它自身，則這個函數(shù)、這個過程、這個數(shù)據(jù)結(jié)構(gòu)稱為是遞歸定義的，簡稱為遞歸。 遞歸問題只需要少數(shù)的代碼就能夠描述出解題過程中所需要的多次重復(fù)計算，大大減少了程序的代碼量，遞歸所用到的是系統(tǒng)管理棧，但是通常情況下，每次遞歸都要保留現(xiàn)場，空間復(fù)雜度為O（n），效率不高，并且當(dāng)遞歸次數(shù)過深的時候，容易出現(xiàn)堆棧溢出的現(xiàn)象。 將遞歸轉(zhuǎn)化成非遞歸算法，也是用棧來實現(xiàn)的。相比起遞歸算法的系統(tǒng)管理棧，需要建一個自己管理的棧。

14.隊列在層次遍歷中的作用 ：

答：首先根結(jié)點入隊，接著隊根結(jié)點的子結(jié)點進(jìn)行預(yù)處理，等預(yù)處理完后，根結(jié)點出隊，接著剛剛處理的子結(jié)點入隊，這部分的子結(jié)點又進(jìn)行預(yù)處理，直到所有的結(jié)點都入隊出隊處理完畢。

15.隊列在計算機系統(tǒng)中的應(yīng)用 ：

答：有兩個方面的應(yīng)用： （1）解決了主機和外部設(shè)備之間速度不匹配的問題 以主機和打印機為例，主機輸出數(shù)據(jù)的速度比打印機輸出數(shù)據(jù)的速度要快很多，由于速度不匹配，直接把輸出的數(shù)據(jù)給打印機肯定是不行的，于是需要設(shè)置一個緩沖區(qū)，主機將一部分要打印的數(shù)據(jù)寫入緩沖區(qū)，寫滿后就暫停輸出，轉(zhuǎn)去做其他的事情，而打印機就從緩沖區(qū)中按照先進(jìn)先出的原則依次取出數(shù)據(jù)并打印出來，打印完后向主機發(fā)出請求。這里的打印緩沖區(qū)就是一個隊列。

（2）CPU資源的競爭 答：在一個多終端的計算機系統(tǒng)中，多個用戶需要CPU各自運行自己的程序，分別通過各自的終端向操作系統(tǒng)提出占用CPU的請求。操作系統(tǒng)按照每個請求在時間上的先后順序，將他們排成一個隊列，每次把CPU分配給隊首請求的用戶使用。當(dāng)相應(yīng)的程序運行結(jié)束或者用完規(guī)定的時間間隔后，令其出隊，再把CPU分配給新的隊首請求的用戶使用。

16.矩陣的壓縮技術(shù) ：

答：針對特殊的矩陣進(jìn)行壓縮存儲 對稱矩陣：含有大量相同元素的矩陣 稀疏矩陣、上（下）三角矩陣：含有大量0元素的矩陣

壓縮思想：矩陣中相同的數(shù)據(jù)元素（包括元素0）只存儲一個

17.串的模式匹配 ：

串的模式匹配指子串在主串中的位置。 暴力匹配算法：從主串的第一個字符開始，與子串的第一個字符比較，一旦出現(xiàn)不匹配的字符，則主串往后移動一個位置，子串移動子串的第一個位置，并與主串對齊 KMP算法：暴力匹配的弊端就是，沒有充分利用已經(jīng)匹配了的串的信息，好的解決方法應(yīng)該是在模式串中找到最長的子串，并且記錄到next[]數(shù)組中 KMP算法的步驟 （1）主串S和模式串T進(jìn)行比較，并設(shè)起始的下標(biāo)為i和j （2）如果S[i]==T[j],則繼續(xù)比較，并且i和j自增1 （3）當(dāng)s[I]!=T[j]時，將j=next[j];將模式串右移，直到與主串對齊；如果j == -1，則主串往后移動一個單位，i++；j++，j又回到模式串的第一個位置

18.遞歸轉(zhuǎn)換成非遞歸為什么要用棧 ：

答：在實現(xiàn)函數(shù)調(diào)用的時候，系統(tǒng)底層就是用棧來保護(hù)現(xiàn)場的；具體來說，每次調(diào)用函數(shù)時，會把當(dāng)前函數(shù)的局部變量和返回地址都壓棧保存起來，當(dāng)系統(tǒng)調(diào)用結(jié)束返回時，再把局部變量從棧中彈出來； 遞歸的核心就是重復(fù)的函數(shù)調(diào)用，如果要變成非遞歸，就需要自己實現(xiàn)棧的數(shù)據(jù)結(jié)構(gòu)來保存一些狀態(tài)變量，這其實就是模擬函數(shù)的調(diào)用。

19.堆排序 ：

堆：是一種特殊的完全二叉樹，葉子結(jié)點的值大于或者小于根結(jié)點的值 （PS：完全二叉樹是指第n-1層，每一層的結(jié)點數(shù)是2^(n-1),最后一層的結(jié)點可以不放滿，但是必須是從左至右放的）

堆排序：最好、最壞、平均時間復(fù)雜度是O（nlogn） 思想：（以大根堆為例）將待排序的構(gòu)造成一個大根堆，此時最大的元素就是根結(jié)點的元素，這時候，將這個元素與末尾的元素進(jìn)行交換，然后再將剩下的n-1個元素構(gòu)造成一個大根堆，就會形成一個有序 區(qū)。

步驟： （1）構(gòu)造初始堆 a.建立一個完全二叉樹 b.從最后一個非葉子結(jié)點開始調(diào)整，一旦比根結(jié)點大，則與根結(jié)點進(jìn)行交換，最終最大的元素位于根結(jié)點的位置上 （2）將堆頂元素與末尾元素進(jìn)行交換，末尾的元素值最大 （3）重新調(diào)整結(jié)構(gòu)，使其滿足堆定義，然后繼續(xù)交換堆頂元素當(dāng)前末尾元素，反復(fù)執(zhí)行+調(diào)整步驟，直到整個序列有序。

20.圖的思維導(dǎo)圖 ：