2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理(4)

　　4、串

　　串一章需要攻破的主要堡壘有：

　　1. 串的基本概念，串與線性表的關(guān)系(串是其元素均為字符型數(shù)據(jù)的特殊線性表)，空串與空格串的區(qū)別，串相等的條件;

　　2. 串的基本操作，以及這些基本函數(shù)的使用，包括：取子串，串連接，串替換，求串長(zhǎng)等等。運(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)行匹配的匹配過(guò)程。

　　5、多維數(shù)組和廣義表

　　矩陣包括：對(duì)稱(chēng)矩陣，三角矩陣，具有某種特點(diǎn)的稀疏矩陣等。

　　熟悉稀疏矩陣的三種不同存儲(chǔ)方式：三元組，帶輔助行向量的二元組，十字鏈表存儲(chǔ)。

　　掌握將稀疏矩陣的三元組或二元組向十字鏈表進(jìn)行轉(zhuǎn)換的算法。

　　6、樹(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)換。

　　(1) 二叉樹(shù)的概念、性質(zhì)和存儲(chǔ)結(jié)構(gòu)

　　考查方法可有：直接考查二叉樹(shù)的定義，讓你說(shuō)明二叉樹(shù)與普通雙分支樹(shù)(左右子樹(shù)無(wú)序)的區(qū)別;考查滿二叉樹(shù)和完全二叉樹(shù)的性質(zhì)，普通二叉樹(shù)的五個(gè)性質(zhì)：

　　A.第i層的最多結(jié)點(diǎn)數(shù)，

　　B.深度為k的二叉樹(shù)的最多結(jié)點(diǎn)數(shù)，

　　C.n0=n2+1的性質(zhì)，

　　D.n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度，

　　E. 順序存儲(chǔ)二叉樹(shù)時(shí)孩子結(jié)點(diǎn)與父結(jié)點(diǎn)之間的換算關(guān)系(root從1開(kāi)始，則左為：2*i，右為：2*i+1)。

　　二叉樹(shù)的順序存儲(chǔ)和二叉鏈表存儲(chǔ)的各自優(yōu)缺點(diǎn)及適用場(chǎng)合，二叉樹(shù)的三叉鏈表表示方法。

　　(2) 二叉樹(shù)的三種遍歷算法

　　這一知識(shí)點(diǎn)掌握的好壞，將直接關(guān)系到樹(shù)一章的算法能否理解，進(jìn)而關(guān)系到樹(shù)一章的算法設(shè)計(jì)題能否順利完成。二叉樹(shù)的遍歷算法有三種：先序，中序和后序。其劃分的依據(jù)是視其每個(gè)算法中對(duì)根結(jié)點(diǎn)數(shù)據(jù)的訪問(wèn)順序而定。不僅要熟練掌握三種遍歷的遞歸算法，理解其執(zhí)行的實(shí)際步驟，并且應(yīng)該熟練掌握三種遍歷的非遞歸算法。由于二叉樹(shù)一章的很多算法，可以直接根據(jù)三種遞歸算法改造而來(lái)(比如：求葉子個(gè)數(shù))，所以，掌握了三種遍歷的非遞歸算法后，對(duì)付諸如：“利用非遞歸算法求二叉樹(shù)葉子個(gè)數(shù)”這樣的題目就下筆如有神了。

　　(3) 可在三種遍歷算法的基礎(chǔ)上改造完成的其它二叉樹(shù)算法：

　　求葉子個(gè)數(shù)，求二叉樹(shù)結(jié)點(diǎn)總數(shù)，求度為1或度為2的結(jié)點(diǎn)總數(shù)，復(fù)制二叉樹(shù)，建立二叉樹(shù)，交換左右子樹(shù)，查找值為n的某個(gè)指定結(jié)點(diǎn)，刪除值為n的某個(gè)指定結(jié)點(diǎn)，諸如此類(lèi)等等等等。如果你可以熟練掌握二叉樹(shù)的遞歸和非遞歸遍歷算法，那么解決以上問(wèn)題就是小菜一碟了。

　　(4) 線索二叉樹(shù)：

　　線索二叉樹(shù)的引出，是為避免如二叉樹(shù)遍歷時(shí)的遞歸求解。眾所周知，遞歸雖然形式上比較好理解，但是消耗了大量的內(nèi)存資源，如果遞歸層次一多，勢(shì)必帶來(lái)資源耗盡的危險(xiǎn)，為了避免此類(lèi)情況，線索二叉樹(shù)便堂而皇之地出現(xiàn)了。對(duì)于線索二叉樹(shù)，應(yīng)該掌握：線索化的實(shí)質(zhì)，三種線索化的算法，線索化后二叉樹(shù)的遍歷算法，基本線索二叉樹(shù)的其它算法問(wèn)題(如：查找某一類(lèi)線索二叉樹(shù)中指定結(jié)點(diǎn)的前驅(qū)或后繼結(jié)點(diǎn)就是一類(lèi)常考題)。

　　(5) 最優(yōu)二叉樹(shù)(哈夫曼樹(shù))：

　　最優(yōu)二叉樹(shù)是為了解決特定問(wèn)題引出的特殊二叉樹(shù)結(jié)構(gòu)，它的前提是給二叉樹(shù)的每條邊賦予了權(quán)值，這樣形成的二叉樹(shù)按權(quán)相加之和是最小的。最優(yōu)二叉樹(shù)一節(jié)，直接考查算法源碼的很少，一般是給你一組數(shù)據(jù)，要求你建立基于這組數(shù)據(jù)的最優(yōu)二叉樹(shù)，并求出其最小權(quán)值之和，此類(lèi)題目不難，屬送分題。

　　(6) 樹(shù)與森林：

　　二叉樹(shù)是一種特殊的樹(shù)，這種特殊不僅僅在于其分支最多為2以及其它特征，一個(gè)最重要的特殊之處是在于：二叉樹(shù)是有序的!即：二叉樹(shù)的左右孩子是不可交換的，如果交換了就成了另外一棵二叉樹(shù)。 樹(shù)與森林的遍歷，不像二叉樹(shù)那樣豐富，他們只有兩種遍歷算法：先根與后根(對(duì)于森林而言稱(chēng)作：先序與后序遍歷)。此二者的先根與后根遍歷與二叉樹(shù)中的遍歷算法是有對(duì)應(yīng)關(guān)系的：先根遍歷對(duì)應(yīng)二叉樹(shù)的先序遍歷，而后根遍歷對(duì)應(yīng)二叉樹(shù)的中序遍歷。二叉樹(shù)、樹(shù)與森林之所以能有以上的對(duì)應(yīng)關(guān)系，全拜二叉鏈表所賜。二叉樹(shù)使用二叉鏈表分別存放他的左右孩子，樹(shù)利用二叉鏈表存儲(chǔ)孩子及兄弟(稱(chēng)孩子兄弟鏈表)，而森林也是利用二叉鏈表存儲(chǔ)孩子及兄弟。

　　軟考程序員考試歷年真題重點(diǎn)題總結(jié)及答案

　　2011年上半年軟考報(bào)名時(shí)間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)