2012年软件水平考试程序员考点整理（4）

会计考友

4、串
　　串一章需要攻破的首要碉堡有：
6 v; b' R" g9 e6 I3 F* u0 G　　1. 串的根基概念，串与线性表的关系(串是其元素均为字符型数据的非凡线性表)，空串与空格串的区别，串相等的前提;
　　2. 串的根基操作，以及这些根基函数的使用，搜罗：取子串，串毗连，串替代，求串长等等。运用串的根基操作去完成特定的算法是良多黉舍在根基操作上的考绩重点。
; ?- y* G7 V2 r" Z　　3. 挨次串与链串及块链串的区别和联系，实现体例。
) n; k- U6 Z5 P* e- N　　4. KMP算法思惟。KMP中next数组以及nextval数组的求法。明晰传统模式匹配算法的不足，明晰next数组需要改良。可能进行的考绩体例是：求next和nextval数组值，按照求得的next或nextval数组值给出运用KMP算法进行匹配的匹配过程。
. R  X* w% Z0 N. [' O6 Z% E5、多维数组和广义表
　　矩阵搜罗：对称矩阵，三角矩阵，具有某种特点的稀少矩阵等。
　　熟悉稀少矩阵的三种分歧存储体例：三元组，带辅助行向量的二元组，十字链表存储。
' E% B$ p" s3 N: ^2 ?
- a; r' Q8 C. }: X　　把握将稀少矩阵的三元组或二元组向十字链表进行转换的算法。

会计考友

</p>6、树与二叉树
! ^# W; W) j5 Q　　树一章的常识点搜罗：
5 q0 O) E4 O( C) ?2 c6 e( M- O* y　　二叉树的概念、性质和存储结构，二叉树遍历的三种算法(递归与非递归)，在三种根基遍历算法的基本上实现二叉树的其它算法，线索二叉树的概念和线索化算法以及线索化后的查找算法，最优二叉树的概念、组成和应用，树的概念和存储形式，树与森林的遍历算法及其与二叉树遍历算法的联系，树与森林和二叉树的转换。
　　(1) 二叉树的概念、性质和存储结构
8 y1 p: S0 E( X  V  K　　考绩体例可有：直接考绩二叉树的界说，让你声名二叉树与通俗双分支树(摆布子树无序)的区别;考绩满二叉树和完全二叉树的性质，通俗二叉树的五个性质：
　　A.第i层的最多结点数，
4 I; M* d! g1 l/ \　　B.深度为k的二叉树的最多结点数，
# k0 l0 n0 A% H, j　　C.n0=n2+1的性质，
　　D.n个结点的完全二叉树的深度，
9 i& H$ a9 v4 A8 G3 b: z　　E. 挨次存储二叉树时孩子结点与父结点之间的换算关系(root从1起头，则左为：2*i，右为：2*i+1)。
　　二叉树的挨次存储和二叉链表存储的各自优错误谬误及合用场所，二叉树的三叉链表暗示体例。
7 g4 Y2 B, _9 y$ _2 D# W　　(2) 二叉树的三种遍历算法
9 X% q  m0 c* m0 j! A　　这一常识点把握的口角，将直接关系到树一章的算法能否理解，进而关系到树一章的算法设计题能否顺遂完成。二叉树的遍历算法有三种：先序，中序和后序。其划分的依据是视其每个算法中对根结点数据的访谒挨次而定。不仅要谙练把握三种遍历的递归算法，理解其执行的现实轨范，而且应该谙练把握三种遍历的非递归算法。因为二叉树一章的良多算法，可以直接按照三种递归算法刷新而来(好比：求叶子个数)，所以，把握了三种遍历的非递归算法后，对于诸如：“操作非递归算法求二叉树叶子个数”这样的问题问题就下笔若有神了。
　　(3) 可在三种遍历算法的基本上刷新完成的其它二叉树算法：
　　求叶子个数，求二叉树结点总数，求度为1或度为2的结点总数，复制二叉树，成立二叉树，交流摆布子树，查找值为n的某个指定结点，删除值为n的某个指定结点，诸如斯类等等等等。如不美观你可以谙练把握二叉树的递归和非递归遍历算法，那么解决以上问题就是小菜一碟了。
& k0 L* W) f7 K% |; N　　(4) 线索二叉树：
　　线索二叉树的引出，是为避免如二叉树遍历时的递归求解。众所周知，递归虽然形式上斗劲好理解，可是耗损了大量的内存资本，如不美观递归条理一多，势必带来资本耗尽的危险，为了避免此类情形，线索二叉树便冠冕堂皇地呈现了。对于线索二叉树，应该把握：线索化的本色，三种线索化的算法，线索化后二叉树的遍历算法，根基线索二叉树的其它算法问题(如：查找某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题)。
　　(5) 最优二叉树(哈夫曼树)：
　　最优二叉树是为体味决特定问题引出的非凡二叉树结构，它的前提是给二叉树的每条边赋予了权值，这样形成的二叉树按权相加之和是最小的。最优二叉树一节，直接考绩算法源码的很少，一般是给你一组数据，要求你成立基于这组数据的最优二叉树，并求出其最小权值之和，此类问题问题不难，属送分题。
' R8 l0 u& p' q+ m- Y　　(6) 树与森林：
　　二叉树是一种非凡的树，这种非凡不仅仅在于其分支最多为2以及其它特征，一个最主要的非凡之处是在于：二叉树是有序的!即：二叉树的摆布孩子是不成交流的，如不美观交流了就成了此外一棵二叉树。 树与森林的遍历，不像二叉树那样丰硕，他们只有两种遍历算法：先根与后根(对于森林而言称作：先序与后序遍历)。此二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，尔后根遍历对应二叉树的中序遍历。二叉树、树与森林之所以能有以上的对应关系，全拜二叉链表所赐。二叉树使用二叉链表分袂存放他的摆布孩子，树操作二叉链表存储孩子及兄弟(称孩子兄弟链表)，而森林也是操作二叉链表存储孩子及兄弟。