【正文】 ：對(duì)稱矩陣，三角矩陣，具有某種特點(diǎn)的稀疏矩陣等。明確傳統(tǒng)模式匹配算法的不足，明確next數(shù)組需要改進(jìn)。　　4. KMP算法思想。運(yùn)用串的基本操作去完成特定的算法是很多學(xué)校在基本操作上的考查重點(diǎn)?！　串　　串一章需要攻破的主要堡壘有：　　1. 串的基本概念，串與線性表的關(guān)系(串是其元素均為字符型數(shù)據(jù)的特殊線性表)，空串與空格串的區(qū)別，串相等的條件?！　?*q)front=((*q)front +1)%MAXSIZE。　　}　　int deleteQue(Quque ** q,int *pelem)　　{　　if(isEmpty(*q))　　return 0?！　　　int isEmpty(Quque *q)　　{　　if(qfront==qrear)//判空　　return 1。　　(*q)rear=((*q)rear+1)%MAXSIZE。　　}　　int insertQue(Quque **q,int elem)　　{　　if(isFull(*q))return 1?！　　　int isFull(Quque *q)　　{　　if(qfront==(qrear+1)%MAXSIZE)//判滿(空出一個(gè)元素不用) 劉勉剛　　return 1。 //定義隊(duì)頭　　int initQue(Quque **q) //初始化　　{　　(*q)front=0?！　ntfront, rear。注意，我說(shuō)的是可以不看書(shū)，并不是可以不作題哦。　　(2)少用一個(gè)元素空間，約定以“隊(duì)列頭指針front在隊(duì)尾指針rear的下一個(gè)位置上”作為隊(duì)列“滿”狀態(tài)的標(biāo)志?！　　狙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ì)滿?！　?3)棧的應(yīng)用：數(shù)值表達(dá)式的求解，括號(hào)的配對(duì)等的原理，只作原理性了解，具體要求考查此為題目的算法設(shè)計(jì)題不多。棧與遞歸的關(guān)系，以及借助棧將遞歸轉(zhuǎn)向于非遞歸的經(jīng)典算法：n!階乘問(wèn)題，fib數(shù)列問(wèn)題，hanoi問(wèn)題，背包問(wèn)題，二叉樹(shù)的遞歸和非遞歸遍歷問(wèn)題，圖的深度遍歷與棧的關(guān)系等。棧與隊(duì)列存取數(shù)據(jù)(請(qǐng)注意包括：存和取兩部分)的特點(diǎn)?！　?3)單鏈表中設(shè)置頭指針、循環(huán)鏈表中設(shè)置尾指針而不設(shè)置頭指針以及索引存儲(chǔ)結(jié)構(gòu)的各自好處。}//PostOrderUnrec線性表　　(1) 性表的鏈?zhǔn)酱鎯?chǔ)方式及以下幾種常用鏈表的特點(diǎn)和運(yùn)算：?jiǎn)捂湵?、循環(huán)鏈表，雙向鏈表，雙向循環(huán)鏈表。 p=[].ptrrchild。 //遍歷右子樹(shù) [].tag =R。 if (!StackEmpty(s)) } visite(pdata)。 p = 。 x = pop(s)。 amp。 //標(biāo)記為左子樹(shù) = L。 = p。 //遍歷左子樹(shù) while (p!=null) do p=t。 StackInit(s)。 stacknode x。 SqStack s。}SqStack。typedef struct{ tagtype tag。 Bitree ptr。}//PostOrderUnrecdefine maxsize 100typedef enum{L,R} tagtype。 p=[].ptrrchild。 //遍歷右子樹(shù) [].tag =R。 if (!StackEmpty(s)) } visite(pdata)。 p = 。 x = pop(s)。 amp。 //標(biāo)記為左子樹(shù) = L。 = p。 //遍歷左子樹(shù) while (p!=null) do p=t。 StackInit(s)。 stacknode x。 SqStack s。}SqStack。typedef struct{ tagtype tag。 Bitree ptr。 }//endwhile}//InOrderUnrecdefine maxsize 100typedef enum{L,R} tagtype。 }//endif p=prchild。 visite(pdata)。 p=pop(s)。 if (!StackEmpty(s)) }//endwhile p=plchild。 push(s,p)。 //遍歷左子樹(shù) {void InOrderUnrec(Bitree t){ int top。 Bitree Elem[maxsize]。 }//endwhile }//endif p=prchild。 p=pop(s)。 //通過(guò)下一次循環(huán)中的內(nèi)嵌while實(shí)現(xiàn)右子樹(shù)遍歷 p=plchild。 push(s,p)。 visite(pdata)。 //遍歷左子樹(shù) {void PreOrderUnrec(Bitree t){ int top。 Bitree Elem[maxsize]。overload和override的區(qū)別?　　F. 字符串有關(guān)的函數(shù)，比如讓你寫一個(gè)拷貝字符串的函數(shù)啊，或者字符串反轉(zhuǎn)啊什么的。.. . . ..?？蓟A(chǔ)必知必會(huì)　　A. 排序：排序有幾種，各種排序的比較，哪些排序是穩(wěn)定的，快排的算法?！　. 查找：哈希查找、二叉樹(shù)查找、折半查找的對(duì)比，哈希映射和哈希表的區(qū)別?　　C. 鏈表和數(shù)組的區(qū)別，在什么情況下用鏈表什么情況下用數(shù)組?　　D. 棧和隊(duì)列的區(qū)別?　　E. 多態(tài)，舉例說(shuō)明。strcpy和memcpy?　　G. 繼承、多繼承?　　H. 面向?qū)ο笥惺裁春锰?　　I. 說(shuō)說(shuō)static的與眾不同之處，如果一個(gè)變量被聲明為static，它會(huì)被分配在哪里?在什么時(shí)候分配空間等?　　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)定理?二叉樹(shù)三種遍歷的非遞歸算法　　define maxsize 100typedef struct{}SqStack。 SqStack s。 StackInit(s)。 p=t。 while (p!=null || !StackEmpty(s)) while (p!=null) { }//endwhile if (!StackEmpty(s)) { }//PreOrderUnrecdefine maxsize 100typedef struct{}SqStack。 SqStack s。 StackInit(s)。 p=t。 while (p!=null || !StackEmpty(s)) while (p!=null) { { //訪問(wèn)根結(jié)點(diǎn) //通過(guò)下一次循環(huán)實(shí)現(xiàn)右子樹(shù)遍歷 typedef struct {}stacknode。 stacknode Elem[maxsize]。 int top。//后序遍歷void PostOrderUnrec(Bitree t){ { { push(s,x)。 p=plchild。 } while (!StackEmpty(s) amp。[].tag==R) { //tag為R，表示右子樹(shù)訪問(wèn)完畢，故訪問(wèn)根結(jié)點(diǎn) { } }while (!StackEmpty(s))。typedef struct {}stacknode。 stacknode Elem[maxsize]。 int top。//后序遍歷void PostOrderUnrec(Bitree t){ { { push(s,x)。 p=plchild。 } while (!StackEmpty(s) amp。[].tag==R) { //tag為R，表示右子樹(shù)訪問(wèn)完畢，故訪問(wèn)根結(jié)點(diǎn) { } }while (!StackEmpty(s))。　　(2)單鏈表的歸并算法、循環(huán)鏈表的歸并算法、雙向鏈表及雙向循環(huán)鏈表的插入和刪除算法等都是較為常見(jiàn)的考查方式。棧與隊(duì)列　　你可以問(wèn)一下自己是不是已經(jīng)知道了以下幾點(diǎn)：　　(1)棧、隊(duì)列的定義及其相關(guān)數(shù)據(jù)結(jié)構(gòu)的概念，包括：順序棧，鏈棧，共享?xiàng)＃h(huán)隊(duì)列，鏈隊(duì)等?！　?2)遞歸算法。其中，涉及到樹(shù)與圖的問(wèn)題，多半會(huì)在樹(shù)與圖的相關(guān)章節(jié)中進(jìn)行考查?！　?4)循環(huán)隊(duì)列中判隊(duì)空、隊(duì)滿條件，循環(huán)隊(duì)列中入隊(duì)與出隊(duì)(循環(huán)隊(duì)列在插入時(shí)也要判斷其是否已滿，刪除時(shí)要判斷其是否已空)算法。　　有兩種方法處理上述問(wèn)題：　　(1)另設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)列是空還是滿。　　隊(duì)空時(shí)： front=rear，　　隊(duì)滿時(shí)： (rear+1)%maxsize=front】　　如果你已經(jīng)對(duì)上面的幾點(diǎn)了如指掌，棧與隊(duì)列一章可以不看書(shū)了?！　⊙h(huán)隊(duì)列的主要操作：　　(1)創(chuàng)建循環(huán)隊(duì)列　　(2)初始化循環(huán)隊(duì)列　　(3)判斷循環(huán)隊(duì)列是否為空　　(4)判斷循環(huán)隊(duì)列是否為滿　　(5)入隊(duì)、出隊(duì)　　//空出頭尾之間的一個(gè)元素不用　　include　　include　　define MAXSIZE 100　　typedef struct　　{　　intelem[MAXSIZE]?！　Quque?！　?*q)rear=0?！　lse　　return 0?！　?*q)elem[(*q)rear]=elem。//插入　　return0?！　lse　　return 0?！　?pelem=(*q)elem[(*q)front]?！　eturn0?！　?. 串的基本操作，以及這些基本函數(shù)的使用，包括：取子串，串連接，串替換，求串長(zhǎng)等等?！　?. 順序串與鏈串及塊鏈串的區(qū)別和聯(lián)系，實(shí)現(xiàn)方式。KMP中next數(shù)組以及nextval數(shù)組的求法?？赡苓M(jìn)行的考查方式是：求next和nextval數(shù)組值，根據(jù)求得的next或nextval數(shù)組值給出運(yùn)用KMP算法進(jìn)行匹配的匹配過(guò)程。　　熟悉稀疏矩陣的三種不同存儲(chǔ)方式：三元組，帶輔助行向量的二元組，十字鏈表存儲(chǔ)?！　?shù)與二叉樹(shù)　　樹(shù)一章的知識(shí)點(diǎn)包括：　　二叉樹(shù)的概念、性質(zhì)和存儲(chǔ)結(jié)構(gòu)，二叉樹(shù)遍歷的三種算法(遞歸與非遞歸)，在三種基本遍歷算法的基礎(chǔ)上實(shí)現(xiàn)二叉樹(shù)的其它算法，線索二叉樹(shù)的概念和線索化算法以及線索化后的查找算法，最優(yōu)二叉樹(shù)的概念、構(gòu)成和應(yīng)用，樹(shù)的概念和存儲(chǔ)形式，樹(shù)與森林的遍歷算法及其與二叉樹(shù)遍歷算法的聯(lián)系，樹(shù)與森林和二叉樹(shù)的轉(zhuǎn)換?？疾闈M二叉樹(shù)和完全二叉樹(shù)的性質(zhì)，普通二叉樹(shù)的五個(gè)性質(zhì)：　　，　　，　　=n2+1的性質(zhì)，　　，　　E. 順序存儲(chǔ)二叉樹(shù)時(shí)孩子結(jié)點(diǎn)與父結(jié)點(diǎn)之間的換算關(guān)系(root從1開(kāi)始，則左為：2*i，右為：2*i+1)?！　?2) 二叉樹(shù)的三種遍歷算法　　這一知識(shí)點(diǎn)掌握的好壞，將直接關(guān)系到樹(shù)一章的算法能否理解，進(jìn)而關(guān)系到樹(shù)一章的算法設(shè)計(jì)題能否順利完成。其劃分的依據(jù)是視其每個(gè)算法中對(duì)根結(jié)點(diǎn)數(shù)據(jù)的訪問(wèn)順序而定。由于二叉樹(shù)一章的很多算法，可以直接根據(jù)三種遞歸算法改造而來(lái)(比如：求葉子個(gè)數(shù))，所以，掌握了三種遍歷的非遞歸算法后，對(duì)付諸如：“利用非遞歸算法求二叉樹(shù)葉子個(gè)數(shù)”這樣的題目就下筆如有神了。如果你可以熟練掌握二叉樹(shù)的遞歸和非遞歸遍歷算法，那么解決以上問(wèn)題就是小菜一碟了。眾所周知，遞歸雖然形式上比較好理解，但是消耗了大量的內(nèi)存資源，如果遞歸層次一多，勢(shì)必帶來(lái)資源耗盡的危險(xiǎn)，為了避免此類情況，線索二叉樹(shù)便堂而皇之地出現(xiàn)了?！　?5) 最優(yōu)二叉樹(shù)(哈夫曼樹(shù))：　　最優(yōu)二叉樹(shù)是為了解決特定問(wèn)題引出的特殊二叉樹(shù)結(jié)構(gòu)，它的前提是給二叉樹(shù)的每條邊賦予了權(quán)值，這樣形成的二叉樹(shù)按權(quán)相加之和是最小的?！　?6) 樹(shù)與森林：　　二叉樹(shù)是一種特殊的樹(shù)，這種特殊不僅僅在于其分支最多為2以及其它特征，一個(gè)最重要的特殊之處是在于：二叉樹(shù)是有序的!即：二叉樹(shù)的左右孩子是不可交換的，如果交換了就成了另外一棵二叉樹(shù)。此二者的先根與后根遍歷與二叉樹(shù)中的遍歷算法是有對(duì)應(yīng)關(guān)系的：先根遍歷對(duì)應(yīng)二叉樹(shù)的先序遍歷，而后根遍歷對(duì)應(yīng)二叉樹(shù)的中序遍歷。二叉樹(shù)使用二叉鏈表分別存放他的左右孩子，樹(shù)利用二叉鏈表存儲(chǔ)孩子及兄弟(稱孩子兄弟鏈表)，而森林也是利用二叉鏈表存儲(chǔ)孩子及兄弟。　　2. 圖的幾種存儲(chǔ)形式：鄰接矩陣，(逆)鄰接表，十字鏈表及鄰接多重表?！　?. 考查圖的兩種遍歷算法：深度遍歷和廣度遍歷　　深度遍歷和廣度遍歷是圖的兩種基本的遍歷算法，這兩個(gè)算法對(duì)圖一章的重要性等同于“先序、中序、后序遍歷”對(duì)于二叉樹(shù)一章的重要性?！　?. 生成樹(shù)、最小生成樹(shù)的概念以及最小生成樹(shù)的構(gòu)造：PRIM算法和KRUSKAL算法。　　5. 拓?fù)渑判騿?wèn)題：