【正文】 章可以不看書(shū)了?！　?4)循環(huán)隊(duì)列中判隊(duì)空、隊(duì)滿條件，循環(huán)隊(duì)列中入隊(duì)與出隊(duì)(循環(huán)隊(duì)列在插入時(shí)也要判斷其是否已滿，刪除時(shí)要判斷其是否已空)算法?！　?2)遞歸算法?！　?2)單鏈表的歸并算法、循環(huán)鏈表的歸并算法、雙向鏈表及雙向循環(huán)鏈表的插入和刪除算法等都是較為常見(jiàn)的考查方式。 } { {[].tag==R) } p=plchild。 push(s,x)。 int top。 stacknode Elem[maxsize]。}stacknode。typedef struct { } { {[].tag==R) } p=plchild。 push(s,x)。 int top。 stacknode Elem[maxsize]。}stacknode。typedef struct { //通過(guò)下一次循環(huán)實(shí)現(xiàn)右子樹(shù)遍歷 { { while (p!=null || !StackEmpty(s)) p=t。 StackInit(s)。 SqStack s。}SqStack。 }//PreOrderUnrecdefine maxsize 100typedef struct{ if (!StackEmpty(s)) while (p!=null)　　B. 查找：哈希查找、二叉樹(shù)查找、折半查找的對(duì)比，哈希映射和哈希表的區(qū)別?　　C. 鏈表和數(shù)組的區(qū)別，在什么情況下用鏈表什么情況下用數(shù)組?　　D. 棧和隊(duì)列的區(qū)別?　　E. 多態(tài)，舉例說(shuō)明。overload和override的區(qū)別?　　F. 字符串有關(guān)的函數(shù)，比如讓你寫(xiě)一個(gè)拷貝字符串的函數(shù)啊，或者字符串反轉(zhuǎn)啊什么的。 Bitree Elem[maxsize]。 int top。 { visite(pdata)。 push(s,p)。 p=plchild。 p=pop(s)。 p=prchild。 }//endwhilevoid InOrderUnrec(Bitree t){ //遍歷左子樹(shù) if (!StackEmpty(s)) p=prchild。typedef struct{}SqStack。 SqStack s。 stacknode x。 StackInit(s)。 p=t。 while (p!=null) = p。 = L。 //標(biāo)記為左子樹(shù) if (!StackEmpty(s)) p=[].ptrrchild。 typedef struct{}SqStack。 SqStack s。 stacknode x。 StackInit(s)。 p=t。 while (p!=null) = p。 = L。 //標(biāo)記為左子樹(shù) if (!StackEmpty(s)) p=[].ptrrchild。 　　(3)單鏈表中設(shè)置頭指針、循環(huán)鏈表中設(shè)置尾指針而不設(shè)置頭指針以及索引存儲(chǔ)結(jié)構(gòu)的各自好處。棧與遞歸的關(guān)系，以及借助棧將遞歸轉(zhuǎn)向于非遞歸的經(jīng)典算法：n!階乘問(wèn)題，fib數(shù)列問(wèn)題，hanoi問(wèn)題，背包問(wèn)題，二叉樹(shù)的遞歸和非遞歸遍歷問(wèn)題，圖的深度遍歷與棧的關(guān)系等?！　　狙h(huán)隊(duì)列的隊(duì)空隊(duì)滿條件　　為了方便起見(jiàn)，約定：初始化建空隊(duì)時(shí)，令　　front=rear=0,　　當(dāng)隊(duì)空時(shí)：front=rear，　　當(dāng)隊(duì)滿時(shí)：front=rear 亦成立，　　因此只憑等式front=rear無(wú)法判斷隊(duì)空還是隊(duì)滿。注意，我說(shuō)的是可以不看書(shū)，并不是可以不作題哦。 //定義隊(duì)頭　　int initQue(Quque **q) //初始化　　{　　(*q)front=0。　　}　　int insertQue(Quque **q,int elem)　　{　　if(isFull(*q))return 1?！　　　int isEmpty(Quque *q)　　{　　if(qfront==qrear)//判空　　return 1?！　?*q)front=((*q)front +1)%MAXSIZE。運(yùn)用串的基本操作去完成特定的算法是很多學(xué)校在基本操作上的考查重點(diǎn)。明確傳統(tǒng)模式匹配算法的不足，明確next數(shù)組需要改進(jìn)。　　掌握將稀疏矩陣的三元組或二元組向十字鏈表進(jìn)行轉(zhuǎn)換的算法?！　《鏄?shù)的順序存儲(chǔ)和二叉鏈表存儲(chǔ)的各自優(yōu)缺點(diǎn)及適用場(chǎng)合，二叉樹(shù)的三叉鏈表表示方法。不僅要熟練掌握三種遍歷的遞歸算法，理解其執(zhí)行的實(shí)際步驟，并且應(yīng)該熟練掌握三種遍歷的非遞歸算法?！　?4) 線索二叉樹(shù)：　　線索二叉樹(shù)的引出，是為避免如二叉樹(shù)遍歷時(shí)的遞歸求解。最優(yōu)二叉樹(shù)一節(jié)，直接考查算法源碼的很少，一般是給你一組數(shù)據(jù)，要求你建立基于這組數(shù)據(jù)的最優(yōu)二叉樹(shù)，并求出其最小權(quán)值之和，此類題目不難，屬送分題。二叉樹(shù)、樹(shù)與森林之所以能有以上的對(duì)應(yīng)關(guān)系，全拜二叉鏈表所賜。在考查時(shí)，有的學(xué)校是給出一種存儲(chǔ)形式，要求考生用算法或手寫(xiě)出與給定的結(jié)構(gòu)相對(duì)應(yīng)的該圖的另一種存儲(chǔ)形式?！　】疾闀r(shí)，一般不要求寫(xiě)出算法源碼，而是要求根據(jù)這兩種最小生成樹(shù)的算法思想寫(xiě)出其構(gòu)造過(guò)程及最終生成的最小生成樹(shù)?！　?. 關(guān)鍵路徑問(wèn)題：　　這個(gè)問(wèn)題是圖一章的難點(diǎn)問(wèn)題?！　『?jiǎn)單地說(shuō)，最早時(shí)間是通過(guò)“從前向后”的方法求的，而最晚時(shí)間是通過(guò)“從后向前”的方法求解的，并且，要想求最晚時(shí)間必須是在所有的最早時(shí)間都已經(jīng)求出來(lái)之后才能進(jìn)行。概念理解是比較容易的，關(guān)鍵是算法的理解。解決第一個(gè)問(wèn)題用DIJSKTRA算法，解決第二個(gè)問(wèn)題用FLOYD算法，注意區(qū)分?！　∫话銓earch分為三類：在順序表上的查找。　　有序順序表——二分查找法(注意適用條件以及其遞歸實(shí)現(xiàn)方法)。其中，尤以前兩種結(jié)構(gòu)為重，也有部分名校偏愛(ài)考B樹(shù)的。對(duì)于二叉排序樹(shù)，“判斷某棵二叉樹(shù)是否二叉排序樹(shù)”這一算法經(jīng)常被考到，可用遞歸，也可以用非遞歸。 鍵樹(shù)(keywordtree)，又稱數(shù)字搜索樹(shù)(digitalsearch tree)或字符樹(shù)。　　(3) 基于哈希表的查找算法：　　哈希譯自“hash”一詞，意為“散列”或“雜湊”?！　∨判蚍椒ǚ诸愑校翰迦搿⑦x擇、交換、歸并、計(jì)數(shù)等五種排序方法?！　?2)交換排序，又稱冒泡排序，在交換排序的基礎(chǔ)上改進(jìn)又可以得到快速排序。這三種方法的不同點(diǎn)是，根據(jù)什么規(guī)則選取最小的數(shù)。堆排序中的堆建立、堆調(diào)整是重要考點(diǎn)?！　?5)基數(shù)排序，是一種很特別的排序方法，也正是由于它的特殊，所以，基數(shù)排序就比較適合于一些特別的場(chǎng)合，比如撲克牌排序問(wèn)題等?！　?/////////////////////////////////////////////穩(wěn)定性分析////////////////////////////////////////////////　　排序算法的穩(wěn)定性，通俗地講就是能保證排序前2個(gè)相等的數(shù)其在序列的前后位置順序和排序后它們兩個(gè)的前后位置順序相同?！　》治鲆幌鲁Ｒ?jiàn)的排序算法的穩(wěn)定性，每個(gè)都給出簡(jiǎn)單的理由。如果兩個(gè)相等的元素沒(méi)有相鄰，那么即使通過(guò)前面的兩兩交換把兩個(gè)相鄰起來(lái)，這時(shí)候也不會(huì)交換，所以相同元素的前后順序并沒(méi)有改變，所以冒泡排序是一種穩(wěn)定排序算法?！　?3) 插入排序　　插入排序是在一個(gè)已經(jīng)有序的小序列的基礎(chǔ)上，一次插入一個(gè)元素。所以，相等元素的前后順序沒(méi)有改變，從原無(wú)序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的。交換a[j]和a[center_index]，完成一趟快速排序。那么，在短的有序序列合并的過(guò)程中，穩(wěn)定是是否受到破壞?沒(méi)有，合并過(guò)程中我們可以保證如果兩個(gè)當(dāng)前元素相等時(shí)，我們把處在前面的序列的元素保存在結(jié)果序列的前面，這樣就保證了穩(wěn)定性。依次類推，直到最高位。當(dāng)元素基本有序了，步長(zhǎng)很小，插入排序?qū)τ谟行虻男蛄行屎芨?。在一個(gè)長(zhǎng)為n 的序列，堆排序的過(guò)程是從第n/2開(kāi)始和其子節(jié)點(diǎn)共3個(gè)值選擇最大(大頂堆)或者最小(小頂堆),這3個(gè)元素之間的選擇當(dāng)然不會(huì)破壞穩(wěn)定性。冒泡排序 插入排序 二路插入排序 希爾排序 快速排序 選擇排序 歸并排序 堆排序算法的C/C++實(shí)現(xiàn)　　include 　　using namespace std?！　mp=a。 p 　　for (int i = 0 ?！　r(shí)間復(fù)雜度 o(n^2)　　空間復(fù)雜度 o(1)　　比較次數(shù) n(n+1)/2　　*/　　void bubble_sort(int array[],int len)　　{　　for (int i = len1 。j++)　　if(array[j] array[j+1])　　swap(array[j],array[j+1])。i len。j = 0?！　　　}　　if(j == 1)　　array[j+1] = tmp?！　rr_d[0] = array[0]。 i++ )　　{　　if (array[i] arr_d[0])　　{　　int j?！　lse　　break?！　ead =len1。j++)　　{　　if (array[i] arr_d[j])　　arr_d[j1] =arr_d[j]。　　}　　}　　}　　for (int i = 0。　　array[i] = arr_d[pos]。i len?！　 = j d?！　rray[j+d] = tmp?！　 while (inc 1)?！　uick_sort(array,low,pivotloc1)。amp。amp?！　eturn low。 i++)　　{　　if (array[ret] array[i])　　{　　ret = i。 i++)　　{　　int j =SelectMinKey(array,i,len)?！　nt iStart = i, iEnd = n。amp?！　　　if (i = m)　　for (。k = n。 j++)　　array[j] = arrayDest[j]。　　merge_sort(array,m+1,t)。　　時(shí)間復(fù)雜度 o(nlogn)　　空間復(fù)雜度 o(1)　　比較次數(shù)：較多　　*/　　void heap_adjust(int array[],int i,int len)　　{　　int rc = array[i]。 array[j] array[j+1]) j++?！　　　array[i] = rc。 i)　　heap_adjust(array,i,len)。 //彈出最大值，重新對(duì)i1個(gè)元素建堆　　heap_adjust(array,0,i1)。 //冒泡排序　　/*insert_sort(array,len)。*/ //快速排序　　/*select_sort(array,len)?！　eturn 0?！　?4)線性階(O(n))排序　　如桶、箱和基數(shù)排序?！　、坳P(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài)?！　、邥r(shí)間和輔助空間復(fù)雜度等?！　?2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插人、冒泡或隨機(jī)的快速排序?yàn)橐?。這兩種排序都是不穩(wěn)定的。因?yàn)橹苯硬迦肱判蚴欠€(wěn)定的，所以改進(jìn)后的歸并排序仍是穩(wěn)定的?！　?應(yīng)用層　　(OSI5 到 7層)例如HTTP、FTP、DNS　　(如BGP和RIP這樣的路由協(xié)議，盡管由于各種各樣的原因它們分別運(yùn)行在TCP和UDP上，仍然可以將它們看作網(wǎng)絡(luò)層的一部分)　　3傳輸層　　(OSI4 和 5層)例如TCP、UDP、RTP、SCTP　　(如OSPF這樣的路由協(xié)議，盡管運(yùn)行在IP上也可以看作是網(wǎng)絡(luò)層的一部分)　　2網(wǎng)絡(luò)互連層　　(OSI3層)對(duì)于TCP/IP來(lái)說(shuō)這是因特網(wǎng)協(xié)議(IP)　　(如ICMP和IGMP這樣的必須協(xié)議盡管運(yùn)行在IP上，也仍然可以看作是網(wǎng)絡(luò)互連層的一部分。這個(gè)層的處理過(guò)程是應(yīng)用特有的。這些程序和它們對(duì)應(yīng)的協(xié)議包括HTTP(The WorldWide Web)、FTP(文件傳輸)、SMTP(電子郵件)、SSH(安全遠(yuǎn)程登陸)、DNS(名稱 IP 地址尋找)以及許多其他協(xié)議。由于在同一個(gè)系統(tǒng)上很少超過(guò)少數(shù)幾個(gè)的服務(wù)器應(yīng)用，端口沖突引起的問(wèn)題很少?！　∶恳粋€(gè)應(yīng)用層(TCP/IP參考模型 的最高層)協(xié)議一般都會(huì)使用到兩個(gè)傳輸層協(xié)議之一：面向連接的TCP傳輸控制協(xié)議和無(wú)連接的包傳輸?shù)腢DP用戶數(shù)據(jù)報(bào)文協(xié)議 ?！　OP3(PostOffice Protocol, version 3，郵局協(xié)議)，收郵件用?！　∵\(yùn)行在UDP協(xié)議上的協(xié)議：　　BOOTP(BootProtocol，啟動(dòng)協(xié)議)，應(yīng)用于無(wú)盤(pán)設(shè)備。　　SNMP(SimpleNetwork Management Protocol，簡(jiǎn)單網(wǎng)絡(luò)管理協(xié)議)，用于網(wǎng)絡(luò)信息的收集和網(wǎng)絡(luò)管理。在TCP/IP協(xié)議組中，傳輸協(xié)議也包括所給數(shù)據(jù)應(yīng)該送給哪個(gè)應(yīng)用程序。TCP盡量連續(xù)不斷地測(cè)試網(wǎng)絡(luò)的負(fù)載并且控制發(fā)送數(shù)據(jù)的速度以避免網(wǎng)絡(luò)過(guò)載。它是面向紀(jì)錄而不是面向字節(jié)的，它在一個(gè)單獨(dú)的連結(jié)上提供了通過(guò)多路復(fù)用提供的多個(gè)子流。它是一個(gè)“best effort”或者“不可靠”協(xié)議——不是因?yàn)樗貏e不可靠，而是因?yàn)樗粰z查數(shù)據(jù)包是否已經(jīng)到達(dá)目的地，并且不保證它們按順序到達(dá)。它提供TCP流動(dòng)控制語(yǔ)義，但對(duì)于用戶來(lái)說(shuō)保留了UDP的數(shù)據(jù)報(bào)服務(wù)模型。