1、常考基礎必知必會A.排序：排序有幾種，各種排序的比較，哪些排序是穩定的，快排的算法；B.查找：哈希查找、二叉樹查找、折半查找的對比，哈希映射和哈希表的區別C.鏈表和數組的區別，在什么情況下用鏈表什么情況下用數組？D.棧和隊列的區別？E.多態，舉例說明;overload和override的區別?strcpyF.字符串有關的函數，比如讓你寫一個拷貝字符串的函數啊，或者字符串反轉啊什么的。和memcpy?G.繼承、多繼承？H.面向對象有什么好處？? 在什么時候分I.說說static的與眾不同之處，如果一個變量被聲明為static,它會被分配在哪里配空間等？J.什么是虛函數、純虛函數、虛的析構函數，用

2、途？K.內存泄漏及解決方法？網絡部分：OSI模型7層結本TCP/IP模型Z勾？B. TCP/UDP區另IC. TCP建立連接的步驟？D.香農定理？二叉樹三種遍歷白非遞歸算法(背誦版)1.先序遍歷非遞歸算法#definemaxsize100typedefstructBitreeElemmaxsize;inttop;SqStack;voidPreOrderUnrec(Bitreet)SqStacks;StackInit(s);p=t;while(p!=null|!StackEmpty(s)while(p!=null)序遍歷非遞歸算法#definemaxsize100typedefstructBit

3、reeElemmaxsize;inttop;SqStack;voidInOrderUnrec(Bitreet)SqStacks;StackInit(s);p=t;while(p!=null|!StackEmpty(s)while(p!=null)序遍歷非遞歸算法#definemaxsize100typedefenumL,Rtagtype;typedefstructBitreeptr;tagtypetag;stacknode;typedefstructstacknodeElemmaxsize;inttop;SqStack;ag=R)x=pop(s);p=;visite(p-data);ag=R;

4、tr-rchild;while (!StackEmpty(s);序遍歷非遞歸算法#definemaxsize100typedefenumL,Rtagtype;typedefstructBitreeptr;tagtypetag;stacknode;typedefstructstacknodeElemmaxsize;inttop;SqStack;ag=R)x=pop(s);p=;visite(p-data);ag=R;tr-rchild;while(!StackEmpty(s);串的基本概念，串與線性表的關系(串是其元素均為字符型數據的特殊線性表)，空串與空格串的區別，串相等的條件；2 .串的基本

5、操作，以及這些基本函數的使用，包括：取子串，串連接，串替換，求串長等等。運用串的基本操作去完成特定的算法是很多學校在基本操作上的考查重點。3 .順序串與鏈串及塊鏈串的區別和聯系，實現方式。4. KMP算法思想。KMP中next數組以及nextval數組的求法。明確傳統模式匹配算法的不足，明確next數組需要改進。可能進行的考查方式是：求next和nextval數組值，根據求得的next或nextval數組值給出運用KMP算法進行匹配的匹配過程。5、多維數組和廣義表矩陣包括：對稱矩陣，三角矩陣，具有某種特點的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲方式：三元組，帶輔助行向量的二元組，十字鏈表存儲。

6、掌握將稀疏矩陣的三元組或二元組向十字鏈表進行轉換的算法。6、樹與二叉樹樹一章的知識點包括：二叉樹的概念、性質和存儲結構，二叉樹遍歷的三種算法（遞歸與非遞歸），在三種基本遍歷算法的基礎上實現二叉樹的其它算法，線索二叉樹的概念和線索化算法以及線索化后的查找算法，最優二叉樹的概念、構成和應用，樹的概念和存儲形式，樹與森林的遍歷算法及其與二叉樹遍歷算法的聯系，樹與森林和二叉樹的轉換。（1）二叉樹的概念、性質和存儲結構考查方法可有：直接考查二叉樹的定義，讓你說明二叉樹與普通雙分支樹（左右子樹無序）的區別；考查滿二叉樹和完全二叉樹的性質，普通二叉樹的五個性質：A.第i層的最多結點數，B.深度為k的二叉樹的

7、最多結點數，=n2+1的性質，個結點的完全二叉樹的深度，E.順序存儲二叉樹時孩子結點與父結點之間的換算關系（root從1開始，則左為：2*i,右為：2*i+1）。二叉樹的順序存儲和二叉鏈表存儲的各自優缺點及適用場合，二叉樹的三叉鏈表表示方法。（2）二叉樹的三種遍歷算法這一知識點掌握的好壞，將直接關系到樹一章的算法能否理解，進而關系到樹一章的算法設計題能否順利完成。二叉樹的遍歷算法有三種：先序，中序和后序。其劃分的依據是視其每個算法中對根結點數據的訪問順序而定。不僅要熟練掌握三種遍歷的遞歸算法，理解其執行的實際步驟，并且應該熟練掌握三種遍歷的非遞歸算法。由于二叉樹一章的很多算法，可以直接根據三種

8、遞歸算法改造而來(比如：求葉子個數)，所以，掌握了三種遍歷的非遞歸算法后，對付諸如：利用非遞歸算法求二叉樹葉子個數”這樣的題目就下筆如有神了。(3)可在三種遍歷算法的基礎上改造完成的其它二叉樹算法：求葉子個數，求二叉樹結點總數，求度為1或度為2的結點總數，復制二叉樹，建立二叉樹，交換左右子樹，查找值為n的某個指定結點，刪除值為n的某個指定結點，諸如此類等等等等。如果你可以熟練掌握二叉樹的遞歸和非遞歸遍歷算法，那么解決以上問題就是小菜一碟了。(4)線索二叉樹：線索二叉樹的引出，是為避免如二叉樹遍歷時的遞歸求解。眾所周知，遞歸雖然形式上比較好理解，但是消耗了大量的內存資源，如果遞歸層次一多，勢必帶

9、來資源耗盡的危險，為了避免此類情況,線索二叉樹便堂而皇之地出現了。對于線索二叉樹，應該掌握：線索化的實質，三種線索化的算法，線索化后二叉樹的遍歷算法，基本線索二叉樹的其它算法問題(如：查找某一類線索二叉樹中指定結點的前驅或后繼結點就是一類常考題)。(5)最優二叉樹(哈夫曼樹):最優二叉樹是為了解決特定問題引出的特殊二叉樹結構，它的前提是給二叉樹的每條邊賦予了權值，這樣形成的二叉樹按權相加之和是最小的。最優二叉樹一節，直接考查算法源碼的很少，一般是給你一組數據，要求你建立基于這組數據的最優二叉樹，并求出其最小權值之和，此類題目不難，屬送分題。(6)樹與森林：二叉樹是一種特殊的樹，這種特殊不僅僅在

10、于其分支最多為2以及其它特征，一個最重要的特殊之處是在于：二叉樹是有序的！即：二叉樹的左右孩子是不可交換的，如果交換了就成了另外一棵二叉樹。樹與森林的遍歷，不像二叉樹那樣豐富，他們只有兩種遍歷算法：先根與后根（對于森林而言稱作：先序與后序遍歷）。此二者的先根與后根遍歷與二叉樹中的遍歷算法是有對應關系的：先根遍歷對應二叉樹的先序遍歷，而后根遍歷對應二叉樹的中序遍歷。二叉樹、樹與森林之所以能有以上的對應關系，全拜二叉鏈表所賜。二叉樹使用二叉鏈表分別存放他的左右孩子，樹利用二叉鏈表存儲孩子及兄弟（稱孩子兄弟鏈表），而森林也是利用二叉鏈表存儲孩子及兄弟。7、圖1 .圖的基本概念：圖的定義和特點，無向圖

11、，有向圖，入度，出度，完全圖，生成子圖，路徑長度，回路，（強）連通圖，（強）連通分量等概念。2 .圖的幾種存儲形式：鄰接矩陣，（逆）鄰接表，十字鏈表及鄰接多重表。在考查時，有的學校是給出一種存儲形式，要求考生用算法或手寫出與給定的結構相對應的該圖的另一種存儲形式。3 .考查圖的兩種遍歷算法：深度遍歷和廣度遍歷深度遍歷和廣度遍歷是圖的兩種基本的遍歷算法，這兩個算法對圖一章的重要性等同于先序、中序、后序遍歷”對于二叉樹一章的重要性。在考查時，圖一章的算法設計題常常是基于這兩種基本的遍歷算法而設計的，比如：求最長的最短路徑問題”和判斷兩頂點間是否存在長為K的簡單路徑問題”，就分別用到了廣度遍歷和深度

12、遍歷算法。4 .生成樹、最小生成樹的概念以及最小生成樹的構造：PRIM算法和KRUSKAL算法。考查時，一般不要求寫出算法源碼，而是要求根據這兩種最小生成樹的算法思想寫出其構造過程及最終生成的最小生成樹。5 .拓撲排序問題:拓撲排序有兩種方法，一是無前趨的頂點優先算法，二是無后繼的頂點優先算法。換句話說,種是從前向后”的排序，一種是從后向前”排。當然，后一種排序出來的結果是逆拓撲有序”的。6 .關鍵路徑問題：這個問題是圖一章的難點問題。理解關鍵路徑的關鍵有三個方面：一是何謂關鍵路徑；二是最早時間是什么意思、如何求；三是最晚時間是什么意思、如何求。簡單地說，最早時間是通過從前向后”的方法求的，而

13、最晚時間是通過從后向前”的方法求解的，并且，要想求最晚時間必須是在所有的最早時間都已經求出來之后才能進行。在實際設計關鍵路徑的算法時，還應該注意以下這一點：采用鄰接表的存儲結構，求最早時間和最晚時間要采用不同的處理方法，即：在算法初始時，應該首先將所有頂點的最早時間全部置為0。關鍵路徑問題是工程進度控制的重要方法，具有很強的實用性。7 .最短路徑問題：與關鍵路徑問題并稱為圖一章的兩只攔路虎。概念理解是比較容易的，關鍵是算法的理解。最短路徑問題分為兩種：一是求從某一點出發到其余各點的最短路徑(單源最短路徑)；二是求圖中每一對頂點之間的最短路徑。這個問題也具有非常實用的背景特色，一個典型的應該就是

14、旅游景點及旅游路線的選擇問題。解決第一個問題用DIJSKTRA算法，解決第二個問題用FLOYD算法，注意區分。8、查找(search);靜態查找與動態查找的含義及區先弄清楚以下幾個概念：關鍵字、主關鍵字、次關鍵字的含義另I；平均查找長度ASL的概念及在各種查找算法中的計算方法和計算結果，特別是一些典型結構的SL值，應該記住。一般將search分為三類：在順序表上的查找；在樹表上的查找；在哈希表上的查找。（1）線性表上的查找：主要分為三種線性結構：順序表傳統查找方法：逐個比較；有序順序表一一二分查找法（注意適用條件以及其遞歸實現方法）;索引順序表一一對索引結構，采用索引查找算法。注意這三種表下的

15、ASL值以及三種算法的實現。（2）樹表上的查找：樹表主要分為以下幾種：二叉排序樹（即二叉查找樹），平衡二叉查找樹（AVL科）,B樹，鍵樹。其中，尤以前兩種結構為重，也有部分名校偏愛考B樹的。由于二叉排序樹與平衡二叉樹是一種特殊的二叉樹。二叉排序樹，簡言之，就是左小右大”，它的中序遍歷結果是一個遞增的有序序列。平衡二叉排序樹是二叉排序樹的優化，其本質也是一種二叉排序樹，只不過，平衡排序二叉樹對左右子樹的深度有了限定：深度之差的絕對值不得大于1。對于二叉排序樹，判斷某棵二叉樹是否二叉排序樹”這算法經常被考到，可用遞歸，也可以用非遞歸。平衡二叉樹的建立也是一個常考點，但該知識點歸根結底還是關注的平衡

16、二叉樹的四種調整算法，調整的一個參照是：調整前后的中序遍歷結果相同。B樹是二叉排序樹的進一步改進，也可以把B樹理解為三叉、四叉.排序樹。除B樹的查找算法外，應該特另注意一下B樹的插入和刪除算法，因為這兩種算法涉及到B樹結點的分裂和合并，是一個難點。鍵樹(keywordtree),又稱數字搜索樹(digitalsearchtree)或字符樹。trie樹也可說等同于鍵樹或屬于鍵樹的一種。鍵樹特別適用于查找英文單詞的場合。一般不要求能完整描述算法源碼，多是根據算法思想建立鍵樹及描述其大致查找過程。(3)基于哈希表的查找算法：哈希譯自“hash詞，意為散列”或雜湊”。哈希表查找的基本思想是：根據當前待

17、查找數據的特征，以記錄關鍵字為自變量，設計一個function,該函數對關鍵字進行轉換后，其解釋結果為待查的地址。基于哈希表的考查點有：哈希函數的設計，沖突解決方法的選擇及沖突處理過程的描述。9、內部排序考查你對書本上的各種排序算法及其思想以及其優缺點和性能指標(時間復雜度)能否了如指掌。排序方法分類有：插入、選擇、交換、歸并、計數等五種排序方法。(1)插入排序中又可分為：直接插入、折半插入、2路插入(?)、希爾排序。這幾種插入排序算法的最根本的不同點，說到底就是根據什么規則尋找新元素的插入點。直接插入是依次尋找，折半插入是折半尋找，希爾排序，是通過控制每次參與排序的數的總范圍由小到大”的增量

18、來實現排序效率提高的目的。(2)交換排序，又稱冒泡排序，在交換排序的基礎上改進又可以得到快速排序。快速排序的思想，一語以敝之：用中間數將待排數據組一分為二。(3)選擇排序可以分為：簡單選擇、樹選擇、堆排序。選擇排序相對于前面幾種排序算法來說，難度大一點。這三種方法的不同點是，根據什么規則選取最小的數。簡單選擇，是通過簡單的數組遍歷方案確定最小數樹選擇，是通過錦標賽”類似的思想，讓兩數相比，不斷淘汰較大（小）者，最終選出最小（大）數;而堆排序，是利用堆這種數據結構的性質，通過堆元素的刪除、調整等一系列操作將最小數選出放在堆頂。堆排序中的堆建立、堆調整是重要考點。（4）歸并排序，是通過歸并”這種操

19、作完成排序的目的，既然是歸并就必須是兩者以上的數據集合才可能實現歸并。所以，在歸并排序中，關注最多的就是2路歸并。算法思想比較簡單，有一點，要銘記在心：歸并排序是穩定排序。（5）基數排序，是一種很特別的排序方法，也正是由于它的特殊，所以，基數排序就比較適合于一些特別的場合，比如撲克牌排序問題等。基數排序，又分為兩種：多關鍵字的排序（撲克牌排序），鏈式排序（整數排序）。基數排序的核心思想也是利用基數空間”這個概念將問題規模規范、變小，并且，在排序的過程中，只要按照基排的思想，是不用進行關鍵字比較的，這樣得出的最終序列就是一個有序序列。本章各種排序算法的思想以及偽代碼實現，及其時間復雜度都是必須掌

20、握的。.1這些個父節點選擇元素時，就會破壞穩定性。有可能第n/2個父節點交換把后面一個元素交換過去了，而第n/2-1個父節點把后面一個相同的元素沒有交換，那么這2個相同的元素之間的穩定性就被破壞了。所以，堆排序不是穩定的排序算法。冒泡排序插入排序二路插入排序希爾排序快速排序選擇排序歸并排序堆排序算法的C/C+實現#includeusingnamespacestd;m,Rm+1.high,先將它們合并到一個局部的暫存向量R1（相當于輸出堆）中，待合并完成后將R1復制回Rlow.high中。時間復雜度o(nlogn)空間復雜度o(n)比較次數？*/voidmerge(intarray口,inti,

21、intm,intn)intj,k；intiStart=i,iEnd=n;intarrayDest256;for(j=m+1,k=i;i=m&j=n;+k)if(arrayiarrayj)arrayDestk=arrayi+;elsearrayDestk=arrayj+;if(i=m)for(;k=n;k+,i+)arrayDestk=arrayi;if(j=n)for(;k=n;k+,j+)arrayDestk=arrayj;for(j=iStart;j=iEnd;j+)arrayj=arrayDestj;voidmerge_sort(intarray,ints,intt)intm;if(st

22、)m=(s+t)/2;merge_sort(array,s,m);merge_sort(array,m+1,t);merge(array,s,m,t);/*堆排序算法思想：堆排序(HeapSort)是指利用堆(heaps)這種數據結構來構造的一種排序算法。堆是一個近似完全二叉樹結構，并同時滿足堆屬性：即子節點的鍵值或索引總是小于(或者大于)它的父節點。時間復雜度o(nlogn)空間復雜度o(1)比較次數：較多*/voidheap_adjust(intarray,inti,intlen)intrc=array;for(intj=2*i;jif(jlen&arrayj=arrayj)break;a

23、rrayi=arrayj;i=j;arrayi=rc;voidheap_sort(intarray,intlen)inti;for(i=(len-1)i=0;i-)heap_adjust(array,i,len);for(i=(len-1);i0;i-)swap(array0,arrayi);內存空間占用的少，因為鏈表節點會附加上一塊或兩塊下一個節點的信但是數組在建立時就固定了。所以也有可能會因為建立的數組過大或不足引起內存上的問題。B.數組內的數據可隨機訪問，但鏈表不具備隨機訪問性。這個很容易理解，數組在內存里是連續的空間，比如如果一個數組地址從100到200,且每個元素占用兩個字節，那么1

24、00-200之間的任何一個偶數都是數組元素的地址，可以直接訪問。鏈表在內存地址可能是分散的。所以必須通過上一節點中的信息找能找到下一個節點。C.查找速度上。這個也是因為內存地址的連續性的問題，不羅索了。鏈表優于數組的：A.插入與刪除的操作。如果數組的中間插入一個元素，那么這個元素后的所有元素的內存地址都要往后移動。刪除的話同理。只有對數據的最后一個元素進行插入刪除操作時，才比較快。鏈表只需要更改有必要更改的節點內的節點信息就夠了。并不需要更改節點的內存地址。B.內存地址的利用率方面。不管你內存里還有多少空間，如果沒辦法一次性給出數組所需的要空間，那就會提示內存不足，磁盤空間整理的原因之一在這里

25、。而鏈表可以是分散的空間地址。C.鏈表的擴展性比數組好。因為一個數組建立后所占用的空間大小就是固定的，如果滿了就沒法擴展，只能新建一個更大空間的數組；而鏈表不是固定的，可以很方便的擴展。12、C+操作符優先級：記憶方法：去掉一個最高的，去掉一個最低的，剩下的是一、二、三、賦值；雙目運算符中，順序為算術、關系和邏輯，移位和邏輯位插入其中。-摘自C語言程序設計實用問答問題：如何記住運算符的15種優先級和結合性？解答：C語言中運算符種類比較繁多，優先級有15種，結合性有兩種。如何記憶兩種結合性和15種優先級？下面講述一種記憶方法。結合性有兩種，一種是自左至右，另一種是自右至左，大部分運算符的結合性是

26、自左至右，只有單目運算符、三目運算符的賦值運算符的結合性自右至左。優先級有15種，記憶方法如下：記住一個最高的：構造類型的元素或成員以及小括號。記住一個最低的：逗號運算符。剩余的是一、二、三、賦值意思是單目、雙目、三目和賦值運算符。在諸多運算符中，又分為：算術、關系、邏輯。兩種位操作運算符中，移位運算符在算術運算符后邊，邏輯位運算符在邏輯運算符的前面。再細分如下：算術運算符*,/,%高于+,-。關系運算符中：,=,和Memberaccessfromapointerptr-age=34;yes.Memberaccessfromanobject=34;no+Post-incrementfor(in

27、ti=0;i10;i+)cout0;i-)couti;yesdynamic_castRuntime-checkedtypeconversionY&y=dynamic_cast(x);nostatic_castUncheckedtypeconversionY&y=static_cast(x);noreinterpret_castReinterpretingtypeconversionintconst*p=reinterpret_cast(0x1234);noconst_castCastaway/Addconstnessint*q=const_cast(p);notypeidGettypeinfo

28、rmationstd:type_infoconst&t=typeid(x);no111i13iiI!Logicalnegationif(!done).yesrighttoleftnotAlternatespellingfor!Bitwisecomplementflags=flags;yescomplAlternatespellingfor+Pre-incrementfor(i=0;i10;+i)cout0;-i)cout*Memberpointerselectorptr-*var=24;yeslefttoright.*Memberobjectselectorobj.*var=24;no15*M

29、ultiplicationinti=2*4;yeslefttoright/Divisionfloatf=/;yes%Modulusintrem=4%3;yes16+Additioninti=2+3;yeslefttoright-Subtractioninti=5-1;yes17Bitwiseshiftleftintflags=33Bitwiseshiftrightintflags=331;yes8Comparisonless-thanif(i42)yeslefttoright=Comparisonless-than-or-equal-toif(iComparisongreater-thanif

30、(i42).yes=Comparisongreater-than-or-equal-toif(i=42).yes191=Comparisonequal-toif(i=42).yeslefttorighteqAlternatespellingfor=!=Comparisonnot-equal-toif(i!=42).yesnot_eqAlternatespellingfor!=110&BitwiseANDflags=flags&42;yeslefttorightbitandAlternatespellingfor&111ABitwiseexclusiveOR(XOR)flags=flagsa42

31、;yeslefttorightxorAlternatespellingforA12IBitwiseinclusive(normal)ORflags=flags|42;yeslefttorightbitorAlternatespellingfor|q13&LogicalANDif(conditionA&conditionB).yeslefttorightandAlternatespellingfor&r-14IILogicalORif(conditionA|conditionB).yeslefttorightorAlternatespellingfor|115?:Ternarycondition

32、al(if-then-else)inti=ab?a:b;norighttoleft1111111I161111i=Assignmentoperatorinta=b;yesrighttoleft+=Incrementandassigna+=3;yes-=Decrementandassignb-=4;yes*=Multiplyandassigna*=5;yes/=Divideandassigna/=2;yes%=Moduloandassigna%=3;yes&=BitwiseANDandassignflags&=new_flags;yesand_eqAlternatespellingfor&=A=

33、Bitwiseexclusiveor(XOR)andassignflagsa=new_flags;yesxor_eqAlternatespellingforA=|=BitwisenormalORandassignflags|=new_flags;yesor_eqAlternatespellingfor|=Bitwiseshiftleftandassignflags=Bitwiseshiftrightandassignflags=2;yesi17throwthrowexceptionthrowEClass(Message);no118,Sequentialevaluationoperatorfo

34、r(i=0,j=0;i2;2 .根結點的兒子數為2,M;3 .除根結點以外的非葉子結點的兒子數為M/2,M;4 .每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字）5 .非葉子結點的關鍵字個數=指向兒子的指針個數-1；6 .非葉子結點的關鍵字：K1,K2,，KM-1;且KiKi+1;7 .非葉子結點的指針：P1,P2,，PM；其中P1指向關鍵字小于K1的子樹，PM指向關鍵字大于KM-1的子樹，其它Pi指向關鍵字屬于（Ki-1,Ki）的子樹；8 .所有葉子結點位于同一層；如：（M=3）B-樹的搜索，從根結點開始，對結點內的關鍵字（有序）序列進行二分查找，如果命中則結束，

35、否則進入查詢關鍵字所屬范圍的兒子結點；重復，直到所對應的兒子指針為空，或已經是葉子結點；B-樹的特性：1 .關鍵字集合分布在整顆樹中；2 .任何一個關鍵字出現且只出現在一個結點中；3 .搜索有可能在非葉子結點結束；4 .其搜索性能等價于在關鍵字全集內做一次二分查找5 .自動層次控制由于限制了除根結點以外的非葉子結點，至少含有M/2個兒子，確保了結點的至少利用率，其最底搜索性能為：其中，M為設定的非葉子結點最多子樹個數，N為關鍵字總數；所以B-樹的性能總是等彳于二分查找（與M值無關），也就沒有B樹平衡的問題；由于M/2的限制，在插入結點時，如果結點已滿，需要將結點分裂為兩個各占M/2的結點；刪除

36、結點時，需將兩個不足M/2的兄弟結點合并；（3）B+樹B+樹是B-樹的變體，也是一種多路搜索樹：1 .其定義基本與B-樹同，除了：2 .非葉子結點的子樹指針與關鍵字個數相同；3 .非葉子結點的子樹指針Pi,指向關鍵字值屬于Ki,Ki+1）的子樹（B-樹是開區間）；5 .為所有葉子結點增加一個鏈指針；6 .所有關鍵字都在葉子結點出現；如：（M=3）B+的搜索與B-樹也基本相同，區別是B+樹只有達到葉子結點才命中（B-樹可以在非葉子結點命中），其性能也等價于在關鍵字全集做一次二分查找；B+的特性:1 .所有關鍵字都出現在葉子結點的鏈表中（稠密索引），且鏈表中的關鍵字恰好是有序的2 .不可能在非葉子

37、結點命中；3 .非葉子結點相當于是葉子結點的索引（稀疏索引），葉子結點相當于是存儲（關鍵字）數據的數據層；4 .更適合文件索引系統；（4）B*樹是B+樹的變體，在B+樹的非根和非葉子結點再增加指向兄弟的指針；B*樹定義了非葉子結點關鍵字個數至少為（2/3）*M,即塊的最低使用率為2/3（代替B+樹白1/2）;B+樹的分裂：當一個結點滿時，分配一個新的結點，并將原結點中1/2的數據復制到新結點，最后在父結點中增加新結點的指針；B+樹的分裂只影響原結點和父結點，而不會影響兄弟結點，所以它不需要指向兄弟的指針；B*樹的分裂：當一個結點滿時，如果它的下一個兄弟結點未滿，那么將一部分數據移到兄弟結點中，

38、再在原結點插入關鍵字，最后修改父結點中兄弟結點的關鍵字（因為兄弟結點的關鍵字范圍改變了）;如果兄弟也滿了，則在原結點與兄弟結點之間增加新結點，并各復制1/3的數據到新結點，最后在父結點增加新結點的指針；所以，B*樹分配新結點的概率比B+樹要低，空間使用率更高；（5）紅黑樹紅黑樹（Red-BlackTree）是二叉搜索樹（BinarySearchTree）的一種改進。我們知道二叉搜索樹在最壞的情況下可能會變成一個鏈表（當所有節點按從小到大的順序依次插入后）。而紅黑樹在每一次插入或刪除節點之后都會花O(logN)的時間來對樹的結構作修改，以保持樹的平衡。也就是說，紅黑樹的查找方法與二叉搜索樹完全一

39、樣；插入和刪除節點的的方法前半部分節與二叉搜索樹完全一樣，而后半部分添加了一些修改樹的結構的操作。map就是采用紅黑樹存儲的，紅黑樹(RBTree)是平衡二叉樹，其優點就是樹到葉子節點深度一致，查找的效率也就一樣，為logN。在實行查找，插入，刪除的效率都一致，而當是全部靜態數據時，沒有太多優勢，可能采用hash表各合適。相對來說，hash_map是一個hashtable占用內存更多，查找效率高一些，但是hash的時間比較費時。總體而言，hash_map查找速度會比map快，而且查找速度基本和數據數據量大小無關，屬于常數級別；而map的查找速度是log(n)級別。并不一定常數就比10g(n)小

40、，hash還有hash函數的耗時，明白了吧，如果你考慮效率，特別是在元素達到一定數量級時，考慮考慮hash_map。但若你對內存使用特別嚴格，希望程序盡可能少消耗內存，那么一定要小心，hash_map可能會讓你陷入尷尬，特別是當你的hash_map對象特別多時，你就更無法控制了，而且hash_map的構造速度較慢。現在知道如何選擇了嗎？權衡三個因素：查找速度，數據量，內存使用。紅黑樹的每個節點上的屬性除了有一個key、3個指針：parent、Ichild、rchild以外，還多了一個屬性：coloro它只能是兩種顏色：紅或黑。而紅黑樹除了具有二叉搜索樹的所有性質之外，還具有以下4點性質：1 .

41、根節點是黑色的。2 .空節點是黑色的(紅黑樹中，根節點的parent以及所有葉節點lchild、rchild都不指向NULL,而是指向一個定義好的空節點)。3 .紅色節點的父、左子、右子節點都是黑色。4 .在任何一棵子樹中，每一條從根節點向下走到空節點的路徑上包含的黑色節點數量都相同。(6)trie樹Trie樹，即DoubleArray字典查找樹，既可用于一般的字典搜索，也可用于索引查找。每個節點相當于DFA的一個狀態，終止狀態為查找結束。有序查找的過程相當于狀態的不斷轉換對于給定的一個字符串a1,a2,a3,an則采用TRIE樹搜索經過n次搜索即可完成一次查找。不過好像還是沒有B樹的搜索效率

42、高，B樹搜索算法復雜度為10gt(n+1/2).當t趨向大，搜索效率變得高效。Trie樹的優點舉例已知n個由小寫字母構成的平均長度為10的單詞，判斷其中是否存在某個串為另一個串的前綴子串。下面對比3種方法：1 .最容易想到的：即從字符串集中從頭往后搜，看每個字符串是否為字符串集中某個字符串的前綴，復雜度為O(nA2)o2 .使用hash:我彳門用hash存下所有字符串的所有的前綴子串。建立存有子串hash的復雜度為O(n*len)。查詢的復雜度為O(n)*O(1)=O(n)。3 .使用trie：因為當查詢如字符串abc是否為某個字符串的前綴時，顯然以b,c,d.等不是以a開頭的字符串就不用查找

43、了。所以建立trie的復雜度為O(n*len),而建立+查詢在trie中是可以同時執行的，建立的過程也就可以成為查詢的過程，hash就不能實現這個功能。所以總的復雜度為O(n*len),實際查詢的復雜度只是O(len)。解釋一下hash為什么不能將建立與查詢同時執行，例如有串：911,911456輸入，如果要同時執行建立與查詢，過程就是查詢911,沒有，然后存入9、91、911,查詢911456,沒有然后存入9114、91145、911456,而程序沒有記憶功能，并不知道911在輸入數據中出現過。所以用hash必須先存入所有子串，然后for循環查詢。而trie樹便可以，存入911后，已經記錄9

44、11為出現的字符串，在存入911456的過程中就能發現而輸出答案；倒過來亦可以，先存入911456,在存入911時，當指針指向最后一個1時，程序會發現這個1已經存在，說明911必定是某個字符串的前綴，該思想是我在做pku上的3630中發現的，詳見本文配套的入門練習小結B樹：二叉樹，每個結點只存儲一個關鍵字，等于則命中，小于走左結點，大于走右結點；B-樹：多路搜索樹，每個結點存儲M/2到M個關鍵字，非葉子結點存儲指向關鍵字范圍的子結點;所有關鍵字在整顆樹中出現，且只出現一次，非葉子結點可以命中；B+樹：在B-樹基礎上，為葉子結點增加鏈表指針，所有關鍵字都在葉子結點中出現，非葉子結點作為葉子結點的

45、索引；B+樹總是到葉子結點才命中；B*樹：在B+樹基礎上，為非葉子結點也增加鏈表指針，將結點的最低利用率從1/2提高到2/3;14、最小生成樹算法之Prim算法（C+實現）在無向帶權連通圖G中，如果一個連通子樹包含所有頂點，并且連接這些頂點的邊權之和最小，那么這個連通子圖就是G的最小生成樹。求最小生成樹的一個常見算法是Prim算法，該算法的基本思想是：1）設置兩個集合V和S,任意選擇一個頂點作為起始頂點，將起始頂點放入集合S,其余頂點存入集合V中；S和V中邊(即為最小生成樹的中的一2)然后使用貪心策略，選擇一條長度最短并且端點分別在條邊)，將這條邊在V中的端點加入到集合S中；3)循環執行第2)

46、步直到S中包含了所有頂點。O(NA2)的時間復雜根據以上思想我們很快可以給出一個O(NA3)的算法，即選擇一條最短邊需要度，具體實現代碼如下：.，n，c皿為(i，j)的權，打印最小生成樹的每條邊*/voidprim(intcMAXVEXMAXVEX,intn)inti,j,k,min,lowcostMAXVEX,closestMAXVEX;for(i=2;i=n;i+)/*從頂點1開始*/lowcosti=c1i;closesti=1;closest1=0;for(i=2;i=n;i+)/*從U之外求離U中某一頂點最近的頂點*/min=MAXCOST;j=1;k=i;while(j=n)if(

47、lowcostjmin=lowcostj;k=j；j+；printf(%d,%d)”,closestk,k);/*打印邊*/closestk=0;/*k假如到U中*/for(j=2;jif(closestj!=0&ckjLOWCOSTJ)lowcostj=ckj;closestj=k;問題：1）為何兩個for循環都是從下標2開始的？尤其是第二個想不通。答：因為Prim算法可以任選起點，通常選定點1為起點，也就是說點1一開始就在U里面了,自然不必出現在第二個循環（在V-U中尋找點）中。2） lowcost數組顧名思義知道是存放最小代價信息的數組，但是具體的說lowcost放著是什么的最小代價，比

48、如lowcosti=c1i;表示的是什么意思（我要帶i的語言描述）?答：存放的是當前從點集U到點集V-U的最短邊長，lowcosti=c1i是初始化，開始時點集U中只有點1,因此當前點集U到點集V-U的各最短邊長lowcosti就等于點1到點i的邊權。3） closesti=1又是什么含意呢？答：closesti記錄對應lowcosti的邊的起點，因為lowcosti是當前終點為i的各條邊中的最小值,再加上一個closesti記錄起點，就能確定最小生成樹的邊了。closesti=1是初始化，自然每一個邊都是從點1出發的。?4）求教第二個for循環的整層循環是寫什么，我要每一行的注釋。到底是在作什么答:for(i=