2011年軟考程序員考試復習筆試知識點整理(4)

　　4、串

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

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

　　2. 串的基本操作，以及這些基本函數的使用，包括：取子串，串連接，串替換，求串長等等。運用串的基本操作去完成特定的算法是很多學校在基本操作上的考查重點。

　　3. 順序串與鏈串及塊鏈串的區(qū)別和聯系，實現方式。

　　4. KMP算法思想。KMP中next數組以及nextval數組的求法。明確傳統(tǒng)模式匹配算法的不足，明確next數組需要改進。可能進行的考查方式是：求next和nextval數組值，根據求得的next或nextval數組值給出運用KMP算法進行匹配的匹配過程。

　　5、多維數組和廣義表

　　矩陣包括：對稱矩陣，三角矩陣，具有某種特點的稀疏矩陣等。

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

　　掌握將稀疏矩陣的三元組或二元組向十字鏈表進行轉換的算法。

　　6、樹與二叉樹

　　樹一章的知識點包括：

　　二叉樹的概念、性質和存儲結構，二叉樹遍歷的三種算法(遞歸與非遞歸)，在三種基本遍歷算法的基礎上實現二叉樹的其它算法，線索二叉樹的概念和線索化算法以及線索化后的查找算法，最優(yōu)二叉樹的概念、構成和應用，樹的概念和存儲形式，樹與森林的遍歷算法及其與二叉樹遍歷算法的聯系，樹與森林和二叉樹的轉換。

　　(1) 二叉樹的概念、性質和存儲結構

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

　　A.第i層的最多結點數，

　　B.深度為k的二叉樹的最多結點數，

　　C.n0=n2+1的性質，

　　D.n個結點的完全二叉樹的深度，

　　E. 順序存儲二叉樹時孩子結點與父結點之間的換算關系(root從1開始，則左為：2*i，右為：2*i+1)。

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

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

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

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

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

　　(4) 線索二叉樹：

　　線索二叉樹的引出，是為避免如二叉樹遍歷時的遞歸求解。眾所周知，遞歸雖然形式上比較好理解，但是消耗了大量的內存資源，如果遞歸層次一多，勢必帶來資源耗盡的危險，為了避免此類情況，線索二叉樹便堂而皇之地出現了。對于線索二叉樹，應該掌握：線索化的實質，三種線索化的算法，線索化后二叉樹的遍歷算法，基本線索二叉樹的其它算法問題(如：查找某一類線索二叉樹中指定結點的前驅或后繼結點就是一類�？碱})。

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

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

　　(6) 樹與森林：

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

　　軟考程序員考試歷年真題重點題總結及答案

　　2011年上半年軟考報名時間及方式匯總

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