二级公共基础知识考点总结.doc

二级公共基础知识考点总结第一章 数据结构与算法考点1：算法的概念和基本特征算法是指解题方案的准确而完整的描述。算法的基本特征包括：（1）可行性：针对实际问题设计的算法，总是在某个特定计算工具上执行，往往要受到计算工具的限制，使执行结果产生偏差。（2）确定性：算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性。（3）有穷性：算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义。（4）拥有足够的情报：拥有足够的输入。考点2：算法复杂度算法的复杂度主要包括时间复杂度和空间复杂度算法的时间复杂度是指执行算法所需要的计算工作量(即算法执行过程中所需基本运算的执行次数)。算法的空间复杂度是指执行这个算法所需要的内存空间。特别注意：时间复杂度与空间复杂度没有必然的正比或反比的关系。考点3：数据的逻辑结构与存储结构数据的逻辑结构是反映数据元素之间逻辑关系的数据结构，与它们在计算机中的存储位置无关。数据的存储结构（也称物理结构）是指数据的逻辑结构在计算机存储空间中的存放形式。一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等（包括线性结构和非线性结构）。而采用不同的存储结构，其数据处理的效率是不同的。考点4：线性表的顺序存储结构线性表的顺序存储结构具有以下两个基本特点：1) 线性表中所有元素所占的存储空间是连续的2) 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间考点5：栈与队列(属于线性结构)1、栈栈是限定在一端进行插入与删除的线性表。在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。通常用指针top指示栈顶的位置，用指针bottom指向栈底。top-bottom的绝对值加1即为当前栈中元素的个数。栈是按照“先进后出”或“后进先出”的原则组织数据的，用栈顶指针top动态反映了栈中元素的变化情况，而不须改变指针bottom的位置。栈具有记忆作用。2、队列队列是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个尾指针rear指向队尾元素，允许删除的一端称为排头（也称队头），通常用一个排头指针front指向排头元素的前一个位置。队列按照“先进先出”或“后进后出”的原则组织数据，队尾指针rear和排头指针front共同反映了队列中元素动态变化情况。在实际应用中，队列的顺序存储结构一般采用循环队列的形式，循环队列是逻辑上的环状空间，但物理上仍然是线性结构。从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。在普通队列中，rear指针位置减去front指针位置的差值即为队列中元素的个数。但在循环队列中，rear指针的位置可能大于front指针的位置，也可能小于front指针的位置，所以循环队列的元素个数计算方法如下：设循环队列总容量为m如果rearfront，则循环队列的元素个数为rear-front如果rearfront，则循环队列的元素个数为m+(rear-front)栈与队列的共同点：皆为线性结构，只允许在端点处插入与删除，而且不须移动其他元素。考点6：线性链表线性表的链式存储结构称为线性链表在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。链式存储结构即可用于表示线性结构，也可用于表示非线性结构，栈与队列也可以采用链式存储结构。 考点7：二叉树的基本性质树是典型的非线性结构，在树中，每个结点的前件称为父结点，没有父结点的只有一个，称为根结点（有且仅有一个）。每个结点拥有的后件称为子结点，没有子结点的称为叶子结点。一个结点所拥有的子结点的个数称为该结点的度，叶子结点的度为0。树的最大层次称为树的深度。二叉树：每个结点最大的度为2，如下图所示性质1：在二叉树的第k层上，最多有2k-1个结点性质2：深度为m的二叉树最多有2m-1个结点性质3：在任意一棵二叉树中，度为0的结点（叶子结点）总是比度为2的结点多一个。满二叉树：每一层上的结点数都达到最大值，即第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。当完全二叉树有n个结点，若n为偶数，则有n/2个叶子结点；若n为奇数，则有n/2+1个叶子结点（ 表示只取整数部分）。考点8：二叉树的遍历（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树；（3）后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。考点9：查找技术对于长度为n的线性表：顺序查找在最坏情况下，需要比较n次。二分法查找只适用于顺序存储的有序表，在最坏情况下只需要比较log2n次。考点10：排序技术在最坏情况下，对于长度为n的线性表，冒泡排序法、快速排序法、简单插入排序法、简单选择排序法都需要比较n(n-1)/2次；希尔排序法需要比较O(n1.5)次；堆排序法需要比较O(nlog2n)次。在各种排序法中，冒泡排序法最简单，比较次数最少（通常少于n(n-1)/2次）。第二章 程序设计基础考点1：程序设计风格主要风格：清晰第一，效率第二形成良好的程序设计风格应注重的因素：1. 源程序的文档化：要包含必要的程序注释2. 数据说明的方法：数据说明的次序规范化3. 语句的结构4. 输入与输出考点2：结构化程序设计的原则1. 自顶向下2. 逐步求精3. 模块化4. 限制使用goto语句结构化程序设计的基本结构包括顺序结构、选择结构和循环结构。考点3：面向对象的基本概念1、 对象的特点：标识唯一性、分类性、多态性、封装性（实现信息隐蔽）、模块独立性2、 类是具有共同属性、共同方法的对象的集合，类具有继承性3、类与对象的关系：类是对象的抽象，对象则是其对应类的一个实例第三章 软件工程基础考点1：软件的定义及特点计算机软件是包括程序、数据及相关文档的完整集合。软件的特点包括：（1）软件是一种逻辑实体，而不是物理实体。（2）软件的生产与硬件不同，它没有明显的制作过程；（3）软件在运行、使用期间不存在磨损、老化问题；（4）软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题；（5）软件复杂性高，成本昂贵；（6）软件开发涉及诸多的社会因素。软件按功能可以分为：应用软件、系统软件和支撑软件或工具软件。考点2：软件工程的定义软件工程强调在软件开发过程中应用工程化原则软件工程包括3个要素：方法、工具和过程。方法是完成软件工程项目的技术手段；工具支持软件开发、管理、文档生成；过程支持软件开发的各个环节的控制、管理考点3：软件生命周期1. 定义阶段：可行性研究、需求分析2. 开发阶段：概要设计、详细设计、实现、测试3. 维护阶段：使用、维护、退役考点4：结构化分析方法1、结构化分析的常用工具(1) 数据流图（DFD）源、潭存储文件(数据源)数据流加工(2) 数据字典：作用是对DFD中出现的被命名的图形元素的确切解释(3) 判定树(4) 判定表2、软件需求规格说明书：是需求分析阶段的最后成果。其最重要的特点是无歧义性。考点5：结构化设计方法1、软件设计的分类从技术观点来看，软件设计包括软件结构设计、数据设计、接口设计、过程设计从工程管理角度来看，软件设计分两步完成：概要设计和详细设计2、衡量软件模块独立性的两个标准内聚性：是一个模块内部各个元素间彼此结合的紧密程度的度量耦合性：是模块间互相连接的紧密程度的度量在程序结构中，各模块的内聚性越强，则耦合性越弱。优秀的软件设计应尽量做到高内聚、低耦合。3、概要设计（软件结构设计）概要设计的常用工具是结构图（SC）结构图的有关术语：1) 深度：结构图的最大层次数2) 宽度：结构图横向上最大模块数3) 扇出：一个模块拥有的下级从属模块的个数4) 扇入：一个模块拥有的上级模块的个数注意：软件模块的规模要适中4、详细设计（软件过程设计）常用的过程设计工具有：l 图形工具：程序流程图、N-S图、PAD图、HIPO图l 表格工具：判定表l 语言工具：PDL（伪代码）程序流程图的基本图符逻辑条件加工步骤控制流考点6：软件测试1、软件测试的目的：尽可能多的发现错误，而不是证明程序是否正确。2、软件测试的准则1) 所有测试都应回溯到需求2) 严格执行计划，排除随意性3) 充分注意测试中的群集现象4) 程序员应避免检查自己的程序5) 穷举测试不可能6) 妥善保存测试计划3、软件测试的方法(1)静态测试：包括代码走查、静态结构分析、代码质量度量等，可以由人工进行。(2)动态测试：是基于计算机的测试，设计合理的测试用例去运行程序，以便发现错误。测试用例的格式为 （输入值集），输出值集 常用的动态测试方法又分为：l 白盒测试：针对软件程序内部逻辑结构进行测试，其基本原则是保证所测模块中每一独立路径至少执行一次。白盒测试的主要方法有逻辑覆盖、基本路径测试。l 黑盒测试：完全不考虑程序内部的逻辑结构和内部特性，只是对软件已经实现的功能是否满足需求进行测试，检查程序的功能是否符合它的功能说明。黑盒测试方法主要有等价类划分法、边界值分析法、错误推测法、因果图等。4、软件测试的实施软件测试分4个步骤：单元测试、集成测试、验收测试（确认测试）和系统测试特别注意4个步骤的次序考点7：程序的调试(debug)程序调试的任务是诊断和改正程序中的错误程序调试的基本步骤：1. 错误定位2. 修改设计和代码，以排除错误3. 进行回归测试，防止引进新的错误第四章 数据库设计基础考点1：数据库系统的基本概念(1)数据库设计的根本目标：实现数据共享(2)数据库管理系统（DBMS）：是数据库系统的核心，是实现各种数据管理功能的核心软件。是在操作系统支持下的系统软件。数据库管理系统通过提供数据语言完成各项功能，主要包括：l 数据定义语言（DDL）：负责数据的模式定义与数据的物理存取构建l 数据操纵语言（DML）：负责数据的操纵，包括查询及增、删、改等操作l 数据控制语言（DCL）：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等功能(3)数据库系统（DBS）由五部分组成：数据库、数据库管理系统、数据库管理员、硬件平台、软件平台数据库系统需要操作系统（OS）的支持考点2：数据库系统的发展分三个阶段：人工管理、文件系统、数据库系统。其中数据库系统阶段实现的数据共享程度最大，数据独立性最高。考点3：数据库系统的基本特点（1）数据的集成性 如在关系数据库中采用二维表作为统一的结构方式。（2）数据的高共享性与低冗余性 数据一致性是指在系统中同一数据的不同出现应保持相同的值。（3）数据独立性 数据独立性是数据与程序间的互不依赖性，即数据库中数据独立于应用程序而不依赖于应用程序。分为物理独立性和逻辑独立性。u 物理独立性：数据的物理结构（包括存储结构、存取方式等）的改变，不影响数据库的逻辑结构，从而不致引起应用程序的变化。u 逻辑独立性：数据库总体逻辑结构的改变，不需要相应修改应用程序。（4）数据统一管理与控制v 数据的完整性检查v 数据的安全性保护v 并发控制考点4：数据库系统的内部结构体系数据库系统具有三级模式：（1）概念模式：数据库系统中全局数据逻辑结构的描述，全体用户公共数据视图；（2）外模式：也称子模式与用户模式。是用户的数据视图，也就是用户所见到的数据模式；一个概念模式可以推导出多个外模式。（3）内模式：又称物理模式，它给出了数据库物理存储结构与物理存取方法。(如索引等)考点5：E-R模型E-R模型的三个要素：1. 实体：现实世界中的事物。 在E-R图中用矩形框表示。2. 属性：事物的特性； 在E-R图中用椭圆表示。3. 联系：现实世界中事物间的关系。在E-R图中用菱形框表示。联系类型有3种：1对1，1对多，多对多。特别注意实体间联系的举例，如学校与校长、学生与宿舍、学生与课程等。考点6：关系模型的特点关系模型采用二维表（也称为关系）表示，二维表中列称为属性，行称为元组，凡能惟一标识元组的最小属性集称为该表的键或码。二维表应满足7个性质：l 二维表中元组个数是有限的元组个数有限性l 二维表中元组均不相同元组的惟一性l 二维表中元组的次序可以任意交换元组的次序无关性l 二维表中元组的分量是不可分割的基本数据项元组分量的原子性l 二维表中属性名各不相同属性名惟一性l 二维表中属性与次序无关，可任意交换属性的次序无关性l 二维表属性的分量具有与该属性相同的值域分量值域的同一性考点7：关系运算（看图题）l 选择运算、投影运算、笛卡尔积运算l 并运算、交运算、差运算 l 自然连接运算 | |设有关系R与S R SABC123456789ABC456789101112R S（并运算） R S(交运算)ABC123456789101112ABC456789 R S(差运算)ABC123 设有关系R与S: R SR1R2R3abcdefghiS1S2S3jklmnopqr R S(笛卡尔积)R1R2R3S1S2S3abcjklabcmnoabcPqrdefj