程序員軟考專用復(fù)習(xí)資料

1、?？蓟A(chǔ)必知必會A.排序：排序有幾種，各種排序的比較，哪些排序是穩(wěn)定的，快排的算法；B.查找：哈希查找、二叉樹查找、折半查找的對比，哈希映射和哈希表的區(qū)別C.鏈表和數(shù)組的區(qū)別，在什么情況下用鏈表什么情況下用數(shù)組？D.棧和隊列的區(qū)別？E.多態(tài)，舉例說明;overload和override的區(qū)別?strcpyF.字符串有關(guān)的函數(shù)，比如讓你寫一個拷貝字符串的函數(shù)啊，或者字符串反轉(zhuǎn)啊什么的。和memcpy?G.繼承、多繼承？H.面向?qū)ο笥惺裁春锰帲? 在什么時候分I.說說static的與眾不同之處，如果一個變量被聲明為static,它會被分配在哪里配空間等？J.什么是虛函數(shù)、純虛函數(shù)、虛的析構(gòu)函數(shù)，用

2、途？K.內(nèi)存泄漏及解決方法？網(wǎng)絡(luò)部分：OSI模型7層結(jié)本TCP/IP模型Z勾？B. TCP/UDP區(qū)另IC. TCP建立連接的步驟？D.香農(nóng)定理？二叉樹三種遍歷白非遞歸算法(背誦版)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);串的基本概念，串與線性表的關(guān)系(串是其元素均為字符型數(shù)據(jù)的特殊線性表)，空串與空格串的區(qū)別，串相等的條件；2 .串的基本

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

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

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

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

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

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

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

12、遍歷算法。4 .生成樹、最小生成樹的概念以及最小生成樹的構(gòu)造：PRIM算法和KRUSKAL算法?？疾闀r，一般不要求寫出算法源碼，而是要求根據(jù)這兩種最小生成樹的算法思想寫出其構(gòu)造過程及最終生成的最小生成樹。5 .拓?fù)渑判騿栴}:拓?fù)渑判蛴袃煞N方法，一是無前趨的頂點(diǎn)優(yōu)先算法，二是無后繼的頂點(diǎn)優(yōu)先算法。換句話說,種是從前向后”的排序，一種是從后向前”排。當(dāng)然，后一種排序出來的結(jié)果是逆拓?fù)溆行颉钡摹? .關(guān)鍵路徑問題：這個問題是圖一章的難點(diǎn)問題。理解關(guān)鍵路徑的關(guān)鍵有三個方面：一是何謂關(guān)鍵路徑；二是最早時間是什么意思、如何求；三是最晚時間是什么意思、如何求。簡單地說，最早時間是通過從前向后”的方法求的，而

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

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

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

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

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

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

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

20、握的。.1這些個父節(jié)點(diǎn)選擇元素時，就會破壞穩(wěn)定性。有可能第n/2個父節(jié)點(diǎn)交換把后面一個元素交換過去了，而第n/2-1個父節(jié)點(diǎn)把后面一個相同的元素沒有交換，那么這2個相同的元素之間的穩(wěn)定性就被破壞了。所以，堆排序不是穩(wěn)定的排序算法。冒泡排序插入排序二路插入排序希爾排序快速排序選擇排序歸并排序堆排序算法的C/C+實(shí)現(xiàn)#includeusingnamespacestd;m,Rm+1.high,先將它們合并到一個局部的暫存向量R1（相當(dāng)于輸出堆）中，待合并完成后將R1復(fù)制回Rlow.high中。時間復(fù)雜度o(nlogn)空間復(fù)雜度o(n)比較次數(shù)？*/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)這種數(shù)據(jù)結(jié)構(gòu)來構(gòu)造的一種排序算法。堆是一個近似完全二叉樹結(jié)構(gòu)，并同時滿足堆屬性：即子節(jié)點(diǎn)的鍵值或索引總是小于(或者大于)它的父節(jié)點(diǎn)。時間復(fù)雜度o(nlogn)空間復(fù)雜度o(1)比較次數(shù)：較多*/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);內(nèi)存空間占用的少，因?yàn)殒湵砉?jié)點(diǎn)會附加上一塊或兩塊下一個節(jié)點(diǎn)的信但是數(shù)組在建立時就固定了。所以也有可能會因?yàn)榻⒌臄?shù)組過大或不足引起內(nèi)存上的問題。B.數(shù)組內(nèi)的數(shù)據(jù)可隨機(jī)訪問，但鏈表不具備隨機(jī)訪問性。這個很容易理解，數(shù)組在內(nèi)存里是連續(xù)的空間，比如如果一個數(shù)組地址從100到200,且每個元素占用兩個字節(jié)，那么1

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

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

26、自左至右，只有單目運(yùn)算符、三目運(yùn)算符的賦值運(yùn)算符的結(jié)合性自右至左。優(yōu)先級有15種，記憶方法如下：記住一個最高的：構(gòu)造類型的元素或成員以及小括號。記住一個最低的：逗號運(yùn)算符。剩余的是一、二、三、賦值意思是單目、雙目、三目和賦值運(yùn)算符。在諸多運(yùn)算符中，又分為：算術(shù)、關(guān)系、邏輯。兩種位操作運(yùn)算符中，移位運(yùn)算符在算術(shù)運(yùn)算符后邊，邏輯位運(yùn)算符在邏輯運(yùn)算符的前面。再細(xì)分如下：算術(shù)運(yùn)算符*,/,%高于+,-。關(guān)系運(yùn)算符中：,=,和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 .根結(jié)點(diǎn)的兒子數(shù)為2,M;3 .除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)的兒子數(shù)為M/2,M;4 .每個結(jié)點(diǎn)存放至少M(fèi)/2-1（取上整）和至多M-1個關(guān)鍵字；（至少2個關(guān)鍵字）5 .非葉子結(jié)點(diǎn)的關(guān)鍵字個數(shù)=指向兒子的指針個數(shù)-1；6 .非葉子結(jié)點(diǎn)的關(guān)鍵字：K1,K2,，KM-1;且KiKi+1;7 .非葉子結(jié)點(diǎn)的指針：P1,P2,，PM；其中P1指向關(guān)鍵字小于K1的子樹，PM指向關(guān)鍵字大于KM-1的子樹，其它Pi指向關(guān)鍵字屬于（Ki-1,Ki）的子樹；8 .所有葉子結(jié)點(diǎn)位于同一層；如：（M=3）B-樹的搜索，從根結(jié)點(diǎn)開始，對結(jié)點(diǎn)內(nèi)的關(guān)鍵字（有序）序列進(jìn)行二分查找，如果命中則結(jié)束，

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

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

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

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

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

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

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

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

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

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

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

46、步直到S中包含了所有頂點(diǎn)。O(NA2)的時間復(fù)雜根據(jù)以上思想我們很快可以給出一個O(NA3)的算法，即選擇一條最短邊需要度，具體實(shí)現(xiàn)代碼如下：.，n，c皿為(i，j)的權(quán)，打印最小生成樹的每條邊*/voidprim(intcMAXVEXMAXVEX,intn)inti,j,k,min,lowcostMAXVEX,closestMAXVEX;for(i=2;i=n;i+)/*從頂點(diǎn)1開始*/lowcosti=c1i;closesti=1;closest1=0;for(i=2;i=n;i+)/*從U之外求離U中某一頂點(diǎn)最近的頂點(diǎn)*/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循環(huán)都是從下標(biāo)2開始的？尤其是第二個想不通。答：因?yàn)镻rim算法可以任選起點(diǎn)，通常選定點(diǎn)1為起點(diǎn)，也就是說點(diǎn)1一開始就在U里面了,自然不必出現(xiàn)在第二個循環(huán)（在V-U中尋找點(diǎn)）中。2） lowcost數(shù)組顧名思義知道是存放最小代價信息的數(shù)組，但是具體的說lowcost放著是什么的最小代價，比

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