軟考程序員?？贾R點復(fù)習(xí)

20XX年軟考程序員?？贾R點復(fù)習(xí)筆記第一章?？蓟A(chǔ)知識必會A.排序：排序有幾種，各種排序的比較，哪些排序是穩(wěn)定的，快排的算法;B.查找：哈希查找、二叉樹查找、折半查找的對比，哈希映射和哈希表的區(qū)別?C.鏈表和數(shù)組的區(qū)別，在什么情況下用鏈表什么情況下用數(shù)組?D.棧和隊列的區(qū)別?E.多態(tài)，舉例說明;overload和override的區(qū)別?F.字符串有關(guān)的函數(shù)，比如讓你寫一個拷貝字符串的函數(shù)啊，或者字符串反轉(zhuǎn)啊什么的。strcpy和memcpy?G.繼承、多繼承?H.面向?qū)ο笥惺裁春锰?I.說說static的與眾不同之處，如果一個變量被聲明為static，它會被分配在哪里?在什么時候分配空間等?J.什么是虛函數(shù)、純虛函數(shù)、虛的析構(gòu)函數(shù)，用途?K.內(nèi)存泄漏及解決方法?網(wǎng)絡(luò)部分：OSI模型7層結(jié)構(gòu)，TCP/IP模型結(jié)構(gòu)?B.TCP/UDP區(qū)別?C.TCP建立連接的步驟?D.香農(nóng)定理?20XX年軟考程序員?？贾R點復(fù)習(xí)筆記第二章二叉樹三種遍歷的非遞歸算法(背誦版)1.先序遍歷非遞歸算法#definemaxsize100

typedefstruct

{

BitreeElem[maxsize];

inttop;

}SqStack;voidPreOrderUnrec(Bitreet)

{

SqStacks;

StackInit(s);

p=t;

while(p!=null||!StackEmpty(s))

{

while(p!=null)

//遍歷左子樹

{

visite(p->data);

push(s,p);

p=p->lchild;

}//endwhile

if(!StackEmpty(s))

//通過下一次循環(huán)中的內(nèi)嵌while實現(xiàn)右子樹遍歷

{

p=pop(s);

p=p->rchild;

}//endif

}//endwhile

}//PreOrderUnrec20XX年軟考程序員?？贾R點復(fù)習(xí)筆記第三章2、線性表(1)性表的鏈?zhǔn)酱鎯Ψ绞郊耙韵聨追N常用鏈表的特點和運算：單鏈表、循環(huán)鏈表，雙向鏈表，雙向循環(huán)鏈表。(2)單鏈表的歸并算法、循環(huán)鏈表的歸并算法、雙向鏈表及雙向循環(huán)鏈表的插入和刪除算法等都是較為常見的考查方式。(3)單鏈表中設(shè)置頭指針、循環(huán)鏈表中設(shè)置尾指針而不設(shè)置頭指針以及索引存儲結(jié)構(gòu)的各自好處。3、棧與隊列你可以問一下自己是不是已經(jīng)知道了以下幾點：(1)棧、隊列的定義及其相關(guān)數(shù)據(jù)結(jié)構(gòu)的概念，包括：順序棧，鏈棧，共享棧，循環(huán)隊列，鏈隊等。棧與隊列存取數(shù)據(jù)(請注意包括：存和取兩部分)的特點。(2)遞歸算法。棧與遞歸的關(guān)系，以及借助棧將遞歸轉(zhuǎn)向于非遞歸的經(jīng)典算法：n!階乘問題，fib數(shù)列問題，hanoi問題，背包問題，二叉樹的遞歸和非遞歸遍歷問題，圖的深度遍歷與棧的關(guān)系等。其中，涉及到樹與圖的問題，多半會在樹與圖的相關(guān)章節(jié)中進行考查。(3)棧的應(yīng)用：數(shù)值表達(dá)式的求解，括號的配對等的原理，只作原理性了解，具體要求考查此為題目的算法設(shè)計題不多。(4)循環(huán)隊列中判隊空、隊滿條件，循環(huán)隊列中入隊與出隊(循環(huán)隊列在插入時也要判斷其是否已滿，刪除時要判斷其是否已空)算法?！狙h(huán)隊列的隊空隊滿條件為了方便起見，約定：初始化建空隊時，令front=rear=0,當(dāng)隊空時：front=rear，當(dāng)隊滿時：front=rear亦成立，因此只憑等式front=rear無法判斷隊空還是隊滿。有兩種方法處理上述問題：(1)另設(shè)一個標(biāo)志位以區(qū)別隊列是空還是滿。(2)少用一個元素空間，約定以“隊列頭指針front在隊尾指針rear的下一個位置上”作為隊列“滿”狀態(tài)的標(biāo)志。隊空時：front=rear，隊滿時：(rear+1)%maxsize=front】如果你已經(jīng)對上面的幾點了如指掌，棧與隊列一章可以不看書了。注意，我說的是可以不看書，并不是可以不作題哦。循環(huán)隊列的主要操作：(1)創(chuàng)建循環(huán)隊列(2)初始化循環(huán)隊列(3)判斷循環(huán)隊列是否為空(4)判斷循環(huán)隊列是否為滿(5)入隊、出隊//空出頭尾之間的一個元素不用#include#include#defineMAXSIZE100typedefstruct{intelem[MAXSIZE];intfront,rear;}Quque;//定義隊頭intinitQue(Quque**q)//初始化{(*q)->front=0;(*q)->rear=0;}intisFull(Quque*q){if(q->front==(q->rear+1)%MAXSIZE)//判滿(空出一個元素不用)劉勉剛return1;elsereturn0;}intinsertQue(Quque**q,intelem){if(isFull(*q))return-1;(*q)->elem[(*q)->rear]=elem;(*q)->rear=((*q)->rear+1)%MAXSIZE;//插入return0;}intisEmpty(Quque*q){if(q->front==q->rear)//判空return1;elsereturn0;}intdeleteQue(Quque**q,int*pelem){if(isEmpty(*q))return0;*pelem=(*q)->elem[(*q)->front];(*q)->front=((*q)->front+1)%MAXSIZE;return0;}20XX年軟考程序員?？贾R點復(fù)習(xí)筆記第四章4、串串一章需要攻破的主要堡壘有：1.串的基本概念，串與線性表的關(guān)系(串是其元素均為字符型數(shù)據(jù)的特殊線性表)，空串與空格串的區(qū)別，串相等的條件;2.串的基本操作，以及這些基本函數(shù)的使用，包括：取子串，串連接，串替換，求串長等等。運用串的基本操作去完成特定的算法是很多學(xué)校在基本操作上的考查重點。3.順序串與鏈串及塊鏈串的區(qū)別和聯(lián)系，實現(xiàn)方式。4.KMP算法思想。KMP中next數(shù)組以及nextval數(shù)組的求法。明確傳統(tǒng)模式匹配算法的不足，明確next數(shù)組需要改進?？赡苓M行的考查方式是：求next和nextval數(shù)組值，根據(jù)求得的next或nextval數(shù)組值給出運用KMP算法進行匹配的匹配過程。5、多維數(shù)組和廣義表矩陣包括：對稱矩陣，三角矩陣，具有某種特點的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲方式：三元組，帶輔助行向量的二元組，十字鏈表存儲。掌握將稀疏矩陣的三元組或二元組向十字鏈表進行轉(zhuǎn)換的算法。6、樹與二叉樹樹一章的知識點包括：二叉樹的概念、性質(zhì)和存儲結(jié)構(gòu)，二叉樹遍歷的三種算法(遞歸與非遞歸)，在三種基本遍歷算法的基礎(chǔ)上實現(xiàn)二叉樹的其它算法，線索二叉樹的概念和線索化算法以及線索化后的查找算法，最優(yōu)二叉樹的概念、構(gòu)成和應(yīng)用，樹的概念和存儲形式，樹與森林的遍歷算法及其與二叉樹遍歷算法的聯(lián)系，樹與森林和二叉樹的轉(zhuǎn)換。(1)二叉樹的概念、性質(zhì)和存儲結(jié)構(gòu)考查方法可有：直接考查二叉樹的定義，讓你說明二叉樹與普通雙分支樹(左右子樹無序)的區(qū)別;考查滿二叉樹和完全二叉樹的性質(zhì)，普通二叉樹的五個性質(zhì)：A.第i層的最多結(jié)點數(shù)，B.深度為k的二叉樹的最多結(jié)點數(shù)，C.n0=n2+1的性質(zhì)，D.n個結(jié)點的完全二叉樹的深度，E.順序存儲二叉樹時孩子結(jié)點與父結(jié)點之間的換算關(guān)系(root從1開始，則左為：2*i，右為：2*i+1)。二叉樹的順序存儲和二叉鏈表存儲的各自優(yōu)缺點及適用場合，二叉樹的三叉鏈表表示方法。(2)二叉樹的三種遍歷算法這一知識點掌握的好壞，將直接關(guān)系到樹一章的算法能否理解，進而關(guān)系到樹一章的算法設(shè)計題能否順利完成。二叉樹的遍歷算法有三種：先序，中序和后序。其劃分的依據(jù)是視其每個算法中對根結(jié)點數(shù)據(jù)的訪問順序而定。不僅要熟練掌握三種遍歷的遞歸算法，理解其執(zhí)行的實際步驟，并且應(yīng)該熟練掌握三種遍歷的非遞歸算法。由于二叉樹一章的很多算法，可以直接根據(jù)三種遞歸算法改造而來(比如：求葉子個數(shù))，所以，掌握了三種遍歷的非遞歸算法后，對付諸如：“利用非遞歸算法求二叉樹葉子個數(shù)”這樣的題目就下筆如有神了。(3)可在三種遍歷算法的基礎(chǔ)上改造完成的其它二叉樹算法：求葉子個數(shù)，求二叉樹結(jié)點總數(shù)，求度為1或度為2的結(jié)點總數(shù)，復(fù)制二叉樹，建立二叉樹，交換左右子樹，查找值為n的某個指定結(jié)點，刪除值為n的某個指定結(jié)點，諸如此類等等等等。如果你可以熟練掌握二叉樹的遞歸和非遞歸遍歷算法，那么解決以上問題就是小菜一碟了。(4)線索二叉樹：線索二叉樹的引出，是為避免如二叉樹遍歷時的遞歸求解。眾所周知，遞歸雖然形式上比較好理解，但是消耗了大量的內(nèi)存資源，如果遞歸層次一多，勢必帶來資源耗盡的危險，為了避免此類情況，線索二叉樹便堂而皇之地出現(xiàn)了。對于線索二叉樹，應(yīng)該掌握：線索化的實質(zhì)，三種線索化的算法，線索化后二叉樹的遍歷算法，基本線索二叉樹的其它算法問題(如：查找某一類線索二叉樹中指定結(jié)點的前驅(qū)或后繼結(jié)點就是一類常考題)。(5)最優(yōu)二叉樹(哈夫曼樹)：最優(yōu)二叉樹是為了解決特定問題引出的特殊二叉樹結(jié)構(gòu)，它的前提是給二叉樹的每條邊賦予了權(quán)值，這樣形成的二叉樹按權(quán)相加之和是最小的。最優(yōu)二叉樹一節(jié)，直接考查算法源碼的很少，一般是給你一組數(shù)據(jù)，要求你建立基于這組數(shù)據(jù)的最優(yōu)二叉樹，并求出其最小權(quán)值之和，此類題目不難，屬送分題。(6)樹與森林：二叉樹是一種特殊的樹，這種特殊不僅僅在于其分支最多為2以及其它特征，一個最重要的特殊之處是在于：二叉樹是有序的!即：二叉樹的左右孩子是不可交換的，如果交換了就成了另外一棵二叉樹。樹與森林的遍歷，不像二叉樹那樣豐富，他們只有兩種遍歷算法：先根與后根(對于森林而言稱作：先序與后序遍歷)。此二者的先根與后根遍歷與二叉樹中的遍歷算法是有對應(yīng)關(guān)系的：先根遍歷對應(yīng)二叉樹的先序遍歷，而后根遍歷對應(yīng)二叉樹的中序遍歷。二叉樹、樹與森林之所以能有以上的對應(yīng)關(guān)系，全拜二叉鏈表所賜。二叉樹使用二叉鏈表分別存放他的左右孩子，樹利用二叉鏈表存儲孩子及兄弟(稱孩子兄弟鏈表)，而森林也是利用二叉鏈表存儲孩子及兄弟。20XX年軟考程序員?？贾R點復(fù)習(xí)筆記第五章9、內(nèi)部排序考查你對書本上的各種排序算法及其思想以及其優(yōu)缺點和性能指標(biāo)(時間復(fù)雜度)能否了如指掌。排序方法分類有：插入、選擇、交換、歸并、計數(shù)等五種排序方法。(1)插入排序中又可分為：直接插入、折半插入、2路插入(?)、希爾排序。這幾種插入排序算法的最根本的不同點，說到底就是根據(jù)什么規(guī)則尋找新元素的插入點。直接插入是依次尋找，折半插入是折半尋找，希爾排序，是通過控制每次參與排序的數(shù)的總范圍“由小到大”的增量來實現(xiàn)排序效率提高的目的。(2)交換排序，又稱冒泡排序，在交換排序的基礎(chǔ)上改進又可以得到快速排序?？焖倥判虻乃枷?，一語以敝之：用中間數(shù)將待排數(shù)據(jù)組一分為二。(3)選擇排序可以分為：簡單選擇、樹選擇、堆排序。選擇排序相對于前面幾種排序算法來說，難度大一點。這三種方法的不同點是，根據(jù)什么規(guī)則選取最小的數(shù)。簡單選擇，是通過簡單的數(shù)組遍歷方案確定最小數(shù);樹選擇，是通過“錦標(biāo)賽”類似的思想，讓兩數(shù)相比，不斷淘汰較大(小)者，最終選出最小(大)數(shù);而堆排序，是利用堆這種數(shù)據(jù)結(jié)構(gòu)的性質(zhì)，通過堆元素的刪除、調(diào)整等一系列操作將最小數(shù)選出放在堆頂。堆排序中的堆建立、堆調(diào)整是重要考點。(4)歸并排序，是通過“歸并”這種操作完成排序的目的，既然是歸并就必須是兩者以上的數(shù)據(jù)集合才可能實現(xiàn)歸并。所以，在歸并排序中，關(guān)注最多的就是2路歸并。算法思想比較簡單，有一點，要銘記在心：歸并排序是穩(wěn)定排序。(5)基數(shù)排序，是一種很特別的排序方法，也正是由于它的特殊，所以，基數(shù)排序就比較適合于一些特別的場合，比如撲克牌排序問題等?；鶖?shù)排序，又分為兩種：多關(guān)鍵字的排序(撲克牌排序)，鏈?zhǔn)脚判?整數(shù)排序)?；鶖?shù)排序的核心思想也是利用“基數(shù)空間”這個概念將問題規(guī)模規(guī)范、變小，并且，在排序的過程中，只要按照基排的思想，是不用進行關(guān)鍵字比較的，這樣得出的最終序列就是一個有序序列。本章各種排序算法的思想以及偽代碼實現(xiàn)，及其時間復(fù)雜度都是必須掌握的。穩(wěn)定性分析排序算法的穩(wěn)定性，通俗地講就是能保證排序前2個相等的數(shù)其在序列的前后位置順序和排序后它們兩個的前后位置順序相同。穩(wěn)定性的好處：若排序算法如果是穩(wěn)定的，那么從一個鍵上排序，然后再從另一個鍵上排序，第一個鍵排序的結(jié)果可以為第二個鍵排序所用?；鶖?shù)排序就是這樣，先按低位排序，逐次按高位排序，低位相同的元素其順序再高位也相同時是不會改變的。另外，如果排序算法穩(wěn)定，對基于比較的排序算法而言，元素交換的次數(shù)可能會少一些(個人感覺，沒有證實)。分析一下常見的排序算法的穩(wěn)定性，每個都給出簡單的理由。(1)冒泡排序冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個元素比較，交換也發(fā)生在這兩個元素之間。所以，如果兩個元素相等，我想你是不會再無聊地把他們倆交換一下的;如果兩個相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩(wěn)定排序算法。(2)選擇排序選擇排序是給每個位置選擇當(dāng)前元素最小的，比如給第一個位置選擇最小的，在剩余元素里面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因為只剩下它一個最大的元素了。那么，在一趟選擇，如果當(dāng)前元素比一個元素小，而該小的元素又出現(xiàn)在一個和當(dāng)前元素相等的元素后面，那么交換后穩(wěn)定性就被破壞了。比較拗口，舉個例子，序列58529，我們知道第一遍選擇第1個元素5會和2交換，那么原序列中2個5的相對前后順序就被破壞了，所以選擇排序不是一個穩(wěn)定的排序算法。(3)插入排序插入排序是在一個已經(jīng)有序的小序列的基礎(chǔ)上，一次插入一個元素。當(dāng)然，剛開始這個有序的小序列只有1個元素，就是第一個元素。比較是從有序序列的末尾開始，也就是想要插入的元素和已經(jīng)有序的最大者開始比起，如果比它大則直接插入在其后面，否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的。(4)快速排序快速排序有兩個方向，左邊的i下標(biāo)一直往右走，當(dāng)a[i]<=a[center_index]，其中center_index是中樞元素的數(shù)組下標(biāo)，一般取為數(shù)組第0個元素。而右邊的j下標(biāo)一直往左走，當(dāng)a[j]>a[center_index]。如果i和j都走不動了，i<=j,交換a[i]和a[j],重復(fù)上面的過程，直到i>j。交換a[j]和a[center_index]，完成一趟快速排序。在中樞元素和a[j]交換的時候，很有可能把前面的元素的穩(wěn)定性打亂，比如序列為53343891011，現(xiàn)在中樞元素5和3(第5個元素，下標(biāo)從1開始計)交換就會把元素3的穩(wěn)定性打亂，所以快速排序是一個不穩(wěn)定的排序算法，不穩(wěn)定發(fā)生在中樞元素和a[j]交換的時刻。(5)歸并排序歸并排序是把序列遞歸地分成短序列，遞歸出口是短序列只有1個元素(認(rèn)為直接有序)或者2個序列(1次比較和交換),然后把各個有序的段序列合并成一個有序的長序列，不斷合并直到原序列全部排好序?？梢园l(fā)現(xiàn)，在1個或2個元素時，1個元素不會交換，2個元素如果大小相等也沒有人故意交換，這不會破壞穩(wěn)定性。那么，在短的有序序列合并的過程中，穩(wěn)定是是否受到破壞?沒有，合并過程中我們可以保證如果兩個當(dāng)前元素相等時，我們把處在前面的序列的元素保存在結(jié)果序列的前面，這樣就保證了穩(wěn)定性。所以，歸并排序也是穩(wěn)定的排序算法。(6)基數(shù)排序基數(shù)排序是按照低位先排序，然后收集;再按照高位排序，然后再收集;依次類推，直到最高位。有時候有些屬性是有優(yōu)先級順序的，先按低優(yōu)先級排序，再按高優(yōu)先級排序，最后的次序就是高優(yōu)先級高的在前，高優(yōu)先級相同的低優(yōu)先級高的在前?；鶖?shù)排序基于分別排序，分別收集，所以其是穩(wěn)定的排序算法。(7)希爾排序(shell)希爾排序是按照不同步長對元素進行插入排序，當(dāng)剛開始元素很無序的時候，步長最大，所以插入排序的元素個數(shù)很少，速度很快;當(dāng)元素基本有序了，步長很小，插入排序?qū)τ谟行虻男蛄行屎芨?。所以，希爾排序的時間復(fù)雜度會比o(n^2)好一些。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩(wěn)定性就會被打亂，所以shell排序是不穩(wěn)定的。(8)堆排序我們知道堆的結(jié)構(gòu)是節(jié)點i的孩子為2*i和2*i+1節(jié)點，大頂堆要求父節(jié)點大于等于其2個子節(jié)點，小頂堆要求父節(jié)點小于等于其2個子節(jié)點。在一個長為n的序列，堆排序的過程是從第n/2開始和其子節(jié)點共3個值選擇最大(大頂堆)或者最小(小頂堆),這3個元素之間的選擇當(dāng)然不會破壞穩(wěn)定性。但當(dāng)為n/2-1,n/2-2,...1這些個父節(jié)點選擇元素時，就會破壞穩(wěn)定性。有可能第n/2個父節(jié)點交換把后面一個元素交換過去了，而第n/2-1個父節(jié)點把后面一個相同的元素沒有交換，那么這2個相同的元素之間的穩(wěn)定性就被破壞了。所以，堆排序不是穩(wěn)定的排序算法。20XX年軟考程序員?？贾R點復(fù)習(xí)筆記第六章10、OSI模型7層結(jié)構(gòu)，TCP/IP模型結(jié)構(gòu)?osi參考模型osi參考模型中的數(shù)據(jù)封裝過程下面的圖表試圖顯示不同的TCP/IP和其他的協(xié)議在最初OSI模型中的位置：7應(yīng)用層例如HTTP、SMTP、SNMP、FTP、Telnet、SIP、SSH、NFS、RTSP、XMPP、Whois、ENRP6表示層例如XDR、ASN.1、SMB、AFP、NCP5會話層例如ASAP、TLS、SSH、ISO8327/CCITTX.225、RPC、NetBIOS、ASP、Winsock、BSDsockets4傳輸層例如TCP、UDP、RTP、SCTP、SPX、ATP、IL3網(wǎng)絡(luò)層例如IP、ICMP、IGMP、IPX、BGP、OSPF、RIP、IGRP、EIGRP、ARP、RARP、X.252數(shù)據(jù)鏈路層例如Ethernet、Tokenring、HDLC、Framerelay、ISDN、ATM、802.11WiFi、FDDI、PPP1物理層例如wire、radio、fiberoptic、Carrierpigeontcp/ip參考模型tcp/ip參考模型分為四個層次：應(yīng)用層、傳輸層、網(wǎng)絡(luò)互連層和主機到網(wǎng)絡(luò)層：tcp/ip參考模型的層次結(jié)構(gòu)通常人們認(rèn)為OSI模型的最上面三層(應(yīng)用層、表示層和會話層)在TCP/IP組中是一個應(yīng)用層。由于TCP/IP有一個相對較弱的會話層，由TCP和RTP下的打開和關(guān)閉連接組成，并且在TCP和UDP下的各種應(yīng)用提供不同的端口號，這些功能能夠被單個的應(yīng)用程序(或者那些應(yīng)用程序所使用的庫)增加。與此相似的是，IP是按照將它下面的網(wǎng)絡(luò)當(dāng)作一個黑盒子的思想設(shè)計的，這樣在討論TCP/IP的時候就可以把它當(dāng)作一個獨立的層。4應(yīng)用層(OSI5到7層)例如HTTP、FTP、DNS(如BGP和RIP這樣的路由協(xié)議，盡管由于各種各樣的原因它們分別運行在TCP和UDP上，仍然可以將它們看作網(wǎng)絡(luò)層的一部分)3傳輸層(OSI4和5層)例如TCP、UDP、RTP、SCTP(如OSPF這樣的路由協(xié)議，盡管運行在IP上也可以看作是網(wǎng)絡(luò)層的一部分)2網(wǎng)絡(luò)互連層(OSI3層)對于TCP/IP來說這是因特網(wǎng)協(xié)議(IP)(如ICMP和IGMP這樣的必須協(xié)議盡管運行在IP上，也仍然可以看作是網(wǎng)絡(luò)互連層的一部分;ARP不運行在IP上)1網(wǎng)絡(luò)接口層(OSI1和2層)例如Ethernet、Wi-Fi、MPLS等。應(yīng)用層該層包括所有和應(yīng)用程序協(xié)同工作，利用基礎(chǔ)網(wǎng)絡(luò)交換應(yīng)用程序?qū)Ｓ玫臄?shù)據(jù)的協(xié)議。應(yīng)用層是大多數(shù)普通與網(wǎng)絡(luò)相關(guān)的程序為了通過網(wǎng)絡(luò)與其他程序通信所使用的層。這個層的處理過程是應(yīng)用特有的;數(shù)據(jù)從網(wǎng)絡(luò)相關(guān)的程序以這種應(yīng)用內(nèi)部使用的格式進行傳送，然后被編碼成標(biāo)準(zhǔn)協(xié)議的格式。一些特定的程序被認(rèn)為運行在這個層上。它們提供服務(wù)直接支持用戶應(yīng)用。這些程序和它們對應(yīng)的協(xié)議包括HTTP(TheWorldWideWeb)、FTP(文件傳輸)、SMTP(電子郵件)、SSH(安全遠(yuǎn)程登陸)、DNS(名稱<->IP地址尋找)以及許多其他協(xié)議。一旦從應(yīng)用程序來的數(shù)據(jù)被編碼成一個標(biāo)準(zhǔn)的應(yīng)用層協(xié)議，它將被傳送到IP棧的下一層。在傳輸層，應(yīng)用程序最常用的是TCP或者UDP，并且服務(wù)器應(yīng)用程序經(jīng)常與一個公開的端口號相聯(lián)系。服務(wù)器應(yīng)用程序的端口由InternetAssignedNumbersAuthority(IANA)正式地分配，但是現(xiàn)今一些新協(xié)議的開發(fā)者經(jīng)常選擇它們自己的端口號。由于在同一個系統(tǒng)上很少超過少數(shù)幾個的服務(wù)器應(yīng)用，端口沖突引起的問題很少。應(yīng)用軟件通常也允許用戶強制性地指定端口號作為運行參數(shù)。連結(jié)外部的客戶端程序通常使用系統(tǒng)分配的一個隨機端口號。監(jiān)聽一個端口并且然后通過服務(wù)器將那個端口發(fā)送到應(yīng)用的另外一個副本以建立對等連結(jié)(如IRC上的dcc文件傳輸)的應(yīng)用也可以使用一個隨機端口，但是應(yīng)用程序通常允許定義一個特定的端口范圍的規(guī)范以允許端口能夠通過實現(xiàn)網(wǎng)絡(luò)地址轉(zhuǎn)換(NAT)的路由器映射到內(nèi)部。每一個應(yīng)用層(TCP/IP參考模型的最高層)協(xié)議一般都會使用到兩個傳輸層協(xié)議之一：面向連接的TCP傳輸控制協(xié)議和無連接的包傳輸?shù)腢DP用戶數(shù)據(jù)報文協(xié)議。20XX年軟考程序員?？贾R點復(fù)習(xí)筆記第七章11、數(shù)組和鏈表的優(yōu)缺點數(shù)組，在內(nèi)存上給出了連續(xù)的空間。鏈表，內(nèi)存地址上可以是不連續(xù)的，每個鏈表的節(jié)點包括原來的內(nèi)存和下一個節(jié)點的信息(單向的一個，雙向鏈表的話，會有兩個)。數(shù)組優(yōu)于鏈表的:A.內(nèi)存空間占用的少，因為鏈表節(jié)點會附加上一塊或兩塊下一個節(jié)點的信息。但是數(shù)組在建立時就固定了。所以也有可能會因為建立的數(shù)組過大或不足引起內(nèi)存上的問題。B.數(shù)組內(nèi)的數(shù)據(jù)可隨機訪問，但鏈表不具備隨機訪問性。這個很容易理解，數(shù)組在內(nèi)存里是連續(xù)的空間，比如如果一個數(shù)組地址從100到200，且每個元素占用兩個字節(jié)，那么100-200之間的任何一個偶數(shù)都是數(shù)組元素的地址，可以直接訪問。鏈表在內(nèi)存地址可能是分散的。所以必須通過上一節(jié)點中的信息找能找到下一個節(jié)點。C.查找速度上。這個也是因為內(nèi)存地址的連續(xù)性的問題，不羅索了。鏈表優(yōu)于數(shù)組的:A.插入與刪除的操作。如果數(shù)組的中間插入一個元素，那么這個元素后的所有元素的內(nèi)存地址都要往后移動。刪除的話同理。只有對數(shù)據(jù)的最后一個元素進行插入刪除操作時，才比較快。鏈表只需要更改有必要更改的節(jié)點內(nèi)的節(jié)點信息就夠了。并不需要更改節(jié)點的內(nèi)存地址。B.內(nèi)存地址的利用率方面。不管你內(nèi)存里還有多少空間，如果沒辦法一次性給出數(shù)組所需的要空間，那就會提示內(nèi)存不足，磁盤空間整理的原因之一在這里。而鏈表可以是分散的空間地址。C.鏈表的擴展性比數(shù)組好。因為一個數(shù)組建立后所占用的空間大小就是固定的，如果滿了就沒法擴展，只能新建一個更大空間的數(shù)組;而鏈表不是固定的，可以很方便的擴展。20XX年軟考程序員?？贾R點復(fù)習(xí)筆記第八章12、C++操作符優(yōu)先級:記憶方法：去掉一個最高的，去掉一個最低的，剩下的是一、二、三、賦值;雙目運算符中，順序為算術(shù)、關(guān)系和邏輯，移位和邏輯位插入其中。--摘自《C語言程序設(shè)計實用問答》問題：如何記住運算符的15種優(yōu)先級和結(jié)合性?解答：C語言中運算符種類比較繁多，優(yōu)先級有15種，結(jié)合性有兩種。如何記憶兩種結(jié)合性和15種優(yōu)先級?下面講述一種記憶方法。結(jié)合性有兩種，一種是自左至右，另一種是自右至左，大部分運算符的結(jié)合性是自左至右，只有單目運算符、三目運算符的賦值運算符的結(jié)合性自右至左。優(yōu)先級有15種，記憶方法如下：記住一個最高的：構(gòu)造類型的元素或成員以及小括號。記住一個最低的：逗號運算符。剩余的是一、二、三、賦值——意思是單目、雙目、三目和賦值運算符。在諸多運算符中，又分為：算術(shù)、關(guān)系、邏輯。兩種位操作運算符中，移位運算符在算術(shù)運算符后邊，邏輯位運算符在邏輯運算符的前面。再細(xì)分如下：算術(shù)運算符*，/，%高于+，-。關(guān)系運算符中：>，>=，<和<=高于==，!=。邏輯運算符中，除了邏輯求反(!)是單目外，邏輯與(&&)高于邏輯或(||)。邏輯位運算符中，除了邏輯按位求反(~)外，按位與(&)高于按位半加(^)，高于按位或(|)。PrecedenceOperatorDescriptionExampleOverloadableAssociativity1::ScoperesolutionoperatorClass::age=2;nolefttoright2()Functioncallprintf(“Helloworld\n”);yeslefttoright()Memberinitalizationc_tor(intx,inty):_x(x),_y(y*10){}yes[]Arrayaccessarray[4]=2;yes->Memberaccessfromapointerptr->age=34;yes.Memberaccessfromanobjectobj.age=34;no++Post-incrementfor(inti=0;i<10;i++)cout<<i;yes--Post-decrementfor(inti=10;i>0;i--)cout<<i;yesdynamic_castRuntime-checkedtypeconversionY&y=dynamic_cast<y&>(x);</y&>nostatic_castUncheckedtypeconversionY&y=static_cast<y&>(x);</y&>noreinterpret_castReinterpretingtypeconversionintconst*p=reinterpret_cast(0x1234);noconst_castCastaway/Addconstnessint*q=const_cast(p);notypeidGettypeinformationstd::type_infoconst&t=typeid(x);no3!Logicalnegationif(!done)...yesrighttoleftnotAlternatespellingfor!~Bitwisecomplementflags=~flags;yescomplAlternatespellingfor~++Pre-incrementfor(i=0;i<10;++i)cout<<i;yes--Pre-decrementfor(i=10;i>0;--i)cout<<i;yes-Unaryminusinti=-1;yes+Unaryplusinti=+1;yes*Dereferenceintdata=*intPtr;yes&Addressofint*intPtr=&data;yessizeofSize(ofthetype)oftheoperandinbytessize_ts=sizeof(int);nonewDynamicmemoryallocationlong*pVar=newlong;yesnew[]Dynamicmemoryallocationofarraylong*array=newlong[20];yesdeleteDeallocatingthememorydeletepVar;yesdelete[]Deallocatingthememoryofarraydelete[]array;yes(type)Casttoagiventypeinti=(int)floatNum;yes4->*Memberpointerselectorptr->*var=24;yeslefttoright.*Memberobjectselectorobj.*var=24;no5*Multiplicationinti=2*4;yeslefttoright/Divisionfloatf=10.0/3.0;yes%Modulusintrem=4%3;yes6+Additioninti=2+3;yeslefttoright-Subtractioninti=5-1;yes7<<Bitwiseshiftleftintflags=33<<1;yeslefttoright>>Bitwiseshiftrightintflags=33>>1;yes8<Comparisonless-thanif(i<42)...yeslefttoright<=Comparisonless-than-or-equal-toif(i<=42)...yes>Comparisongreater-thanif(i>42)...yes>=Comparisongreater-than-or-equal-toif(i>=42)...yes9==Comparisonequal-toif(i==42)...yeslefttorighteqAlternatespellingfor==!=Comparisonnot-equal-toif(i!=42)...yesnot_eqAlternatespellingfor!=10&BitwiseANDflags=flags&42;yeslefttorightbitandAlternatespellingfor&11^BitwiseexclusiveOR(XOR)flags=flags^42;yeslefttorightxorAlternatespellingfor^12|Bitwiseinclusive(normal)ORflags=flags|42;yeslefttorightbitorAlternatespellingfor|13&&LogicalANDif(conditionA&&conditionB)...yeslefttorightandAlternatespellingfor&&14||LogicalORif(conditionA||conditionB)...yeslefttorightorAlternatespellingfor||15?:Ternaryconditional(if-then-else)inti=a>b?a:b;norighttoleft16=Assignmentoperatorinta=b;yesrighttoleft+=Incrementandassigna+=3;yes-=Decrementandassignb-=4;yes*=Multiplyandassigna*=5;yes/=Divideandassigna/=2;yes%=Moduloandassigna%=3;yes&=BitwiseANDandassignflags&=new_flags;yesand_eqAlternatespellingfor&=^=Bitwiseexclusiveor(XOR)andassignflags^=new_flags;yesxor_eqAlternatespellingfor^=|=BitwisenormalORandassignflags|=new_flags;yesor_eqAlternatespellingfor|=<<=Bitwiseshiftleftandassignflags<<=2;yes>>=Bitwiseshiftrightandassignflags>>=2;yes17throwthrowexceptionthrowEClass(“Message”);no18,Sequentialevaluationoperatorfor(i=0,j=0;i<10;i++,j++)...yeslefttoright20XX年軟考程序員?？贾R點復(fù)習(xí)筆記第九章13、B樹、B-樹、B+樹、B*樹、紅黑樹和trie樹(1)B樹:即二叉搜索樹.1.所有非葉子結(jié)點至多擁有兩個兒子(Left和Right);2.所有結(jié)點各存儲一個關(guān)鍵字;3.非葉子結(jié)點的左指針指向小于其關(guān)鍵字的子樹，右指針指向大于其關(guān)鍵字的子樹;如：B樹的搜索，從根結(jié)點開始，如果查詢的關(guān)鍵字與結(jié)點的關(guān)鍵字相等，那么就命中;否則，如果查詢關(guān)鍵字比結(jié)點關(guān)鍵字小，就進入左兒子;如果比結(jié)點關(guān)鍵字大，就進入右兒子;如果左兒子或右兒子的指針為空，則報告找不到相應(yīng)的關(guān)鍵字;如果B樹的所有非葉子結(jié)點的左右子樹的結(jié)點數(shù)目均保持差不多(平衡)，那么B樹的搜索性能逼近二分查找;但它比連續(xù)內(nèi)存空間的二分查找的優(yōu)點是，改變B樹結(jié)構(gòu)(插入與刪除結(jié)點)不需要移動大段的內(nèi)存數(shù)據(jù)，甚至通常是常數(shù)開銷;如：但B樹在經(jīng)過多次插入與刪除后，有可能導(dǎo)致不同的結(jié)構(gòu)：右邊也是一個B樹，但它的搜索性能已經(jīng)是線性的了;同樣的關(guān)鍵字集合有可能導(dǎo)致不同的樹結(jié)構(gòu)索引;所以，使用B樹還要考慮盡可能讓B樹保持左圖的結(jié)構(gòu)，和避免右圖的結(jié)構(gòu)，也就是所謂的“平衡”問題;實際使用的B樹都是在原B樹的基礎(chǔ)上加上平衡算法，即“平衡二叉樹”;如何保持B樹結(jié)點分布均勻的平衡算法是平衡二叉樹的關(guān)鍵;平衡算法是一種在B樹中插入和刪除結(jié)點的策略;(2)B-樹是一種多路搜