全国二级考试公共基础部分重点与难点.doc

全国二级考试公共基础部分重点与难点1. 顺序存储结构与链式存储结构25 34 57 16 48 091 2 3 4 5 6 data 图1 线性表的顺序存储示意 图2 线性单链表的存储结构示意顺序存储结构链式存储结构优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑，存储密度 =1 插入、删除操作不需要移动大量的元素，修改指针即可 存储空间动态分配，表容量容易扩充 存储空间可以不必连续缺点 插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配，利用不充分 表容量难以扩充 指针需要占用额外的存储空间，存储密度 front 的时候， num = rear front；rear 1，则其双亲是i/2 如果2in，则结点i无左孩子；如果2in，则其左孩子是2i 如果2i+1n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1【常考题型】 计算二叉树的结点个数例如：1）某二叉树共有530个结点，其中度为2的结点有250个，则度为1的结点数为？解题思路： 已知 n=n0+n1+n2 n0=n2+1则： N0=n2+1=250+1=251, n1=n-n0-n2=530-250-251=292）某二叉树共有400个结点，其中有99个度为1的结点，则该二叉树中的叶子结点数为？解题思路： 根据性质3可知：n2=n0-1, 代入公式：n=n0+n1+n2=n0+n1+n0-1=2n0+n1-1 则： N0=(n-n1+1)/2=(400-99+1)/2=151u 二叉树的遍历 先序遍历(DLR)：先访问根结点，然后分别先序遍历左子树、右子树 中序遍历(LDR)：先中序遍历左子树，然后访问根结点，最后中序遍历右子树 后序遍历(LRD)：先后序遍历左、右子树，然后访问根结点 按层次遍历：从上到下、从左到右访问各结点图 10 二叉树的各种遍历方法示意【常考题型】根据先序遍历和中序遍历结果求后序遍历结果例如：解题思路：根据先序遍历和中序遍历的结果可以唯一的确定一颗二叉树的结构，求解方法如下：（1）找到并画出二叉树的根结点：即先序遍历结果中的第一个元素；（2）画出该根结点的左右子树：在中序遍历结果中，根结点前面的元素皆为二叉树左子树上的结点，根结点后面的元素皆为二叉树右子树上的结点。注意：如果中序遍历结果的第一个元素和先序遍历结果的第一个元素相同，说明该二叉树没有左子树；如果中序遍历结果的最后一个元素和先序遍历结果的第一个元素相同，说明该二叉树没有右子树。（3）从先序遍历结果中的第二个元素（左子树的根）开始重复（1）、（2），直至画出根的整个左子树；（4）根据画出的二叉树，进行后序遍历。6. 查找方法比较基于线性表的查找方法比较顺序查找二分（折半）查找分块查找ASL（平均查找长度）最大(n+1)/2最小ASL=log2（n+1）-1两者之间对表结构的要求有序表、无序表有序表分块有序表对存储结构的要求顺序存储、线性链表顺序存储顺序存储、线性链表7. 各种排序方法对比8. 软件开发中的各种图数据流图（DFD图）：用于需求分析阶段，是描述数据处理过程的工具，是需求理解的逻辑模型的图形表示。数据流图所用主要图形元素符号意义加工(转换)数据流存储文件源实体联系图（E-R图）：用于数据库概念设计，E-R模型由实体、联系、属性三个概念组成， 实体之间的联系可分为1:1,1:N，M:N三种。 E-R模型的五种图示法N-S图：用于描述详细设计，其选择结构如下图：问题分析图（PAD图）：用于描述详细设计，其选择结构如下图：程序流程图：用于描述详细设计，其选择结构如下图：构成程序流程图的最基本图符有：控制流（或）、加工步骤（）、逻辑条件（）9. 模块间的内聚与耦合从弱到强分为7级：非直接耦合、数据耦合、标记耦合、控制耦合、外部耦合、公共耦合和内容耦合。10. 关系运算关系的基本运算有两类：一类是传统的集合运算（并、差、交等），另一类是专门的关系运算（选择、投影、连接、除法等）。1 传统的集合运算（针对两个具有相同结构关系的R和S）1并（UNION）（or，或） R和S的并是由属于R或属于S的元组组成的集合，运算符为。记为TRS。 2差（DIFFERENCE）R和S的差是由属于R但不属于S的元组组成的集合，运算符为。记为TRS。 3交（INTERSECTION） （and，与）R和S的交是由既属于R又属于S的元组组成的集合，运算符为。记为TRS。RSR（RS）。 二 专门的关系运算1选择运算（针对一个关系）从关系中找出满足给定条件的那些元组（行）称为选择。这种运算是从水平方向抽取元组。 2投影运算 （针对一个关系）从关系中挑选若干属性（列）组成新的关系称为投影。这是从列的角度进行的运算，相当于对关系进行垂直分解。 例：3. 笛卡尔积运算（针对两个关系，结构可以不同）设A,B为集合，用A中元素为第一元素，B中元素为第二元素构成的有序对，所有这样的有序对组成的集合叫做A与B的笛卡尔积，记作AxB。例如，A=a,b,B=0,1,2,则AxB=,BxA=,4. 连接与自然连接运算（针对两个关系，结构可以不同，但必须有公共域）连接运算是从两个关系的笛卡尔积中选择属性间满足一定条件的元组。连接是将两个关系通过公共的属性名拼接成一个更宽的关系模式，生成的新关系中包含满足连接条件的元组。自然连接是去掉重复属性的等值连接。它属于连接运算的一个特例，是最常用的连接运算，在关系运算中起着重要作用。例：5. 除法运算在关系代数中，除法运算可理解为笛卡尔积的逆