公共基础考点总结.doc

公共基础考点总结 二级公共基础每章考点汇总，请各位学员抄写一遍，便于加深记忆。 学苑欧老师（xx-5-17）第1章算法与数据结构考点1.算法是解题方案准确而完整的描述。 2.算法的基本特征 （1）可行性 （2）确定性 （3）有穷性 （4）拥有足够的情报3.算法的控制结构 （1）顺序结构 （2）选择结构 （3）循环结构4.算法的复杂度主要包括时间复杂度和空间复杂度。 5.算法的时间复杂度是指（执行算法所需要的计算工作，也称为基本运算次数）。 6.算法的空间复杂度是指执行这个算法程序所需要的存储空间。 包括算法程序所占的存储空间；需要处理的数据所占的存储空间；所需要的额外空间。 7.数据结构主要研究三方面内容，分别是逻辑结构、物理结构、运算。 8.逻辑结构是指反映数据元素之间逻辑关系的数据结构，其中逻辑关系是指元素之间的前后件关系。 9.存储结构（也称为物理结构）是指数据的逻辑结构在计算机存储空间中的存放形式。 10.数据的逻辑结构分为线性结构（线性表/队列/栈都是线性结构）与非线性结构（树是非线性结构）。 11.栈是特殊的线性表，插入删除仅在一端进行。 “先进后出”或“后进先出”，具有记忆功能。 主要有三种运算入栈、退栈、读栈顶元素。 12.队列是允许在一端进行插入，而在另一端进行删除的特殊线性表。 “先进先出”或“后进后出”。 循环队列是队列的一种顺序存储结构。 主要有两个运算入队和退队。 13.树的深度指的是树的层数；结点的度一个结点的后件的个数；叶子结点；父结点；根结点等概念14.二叉树的4个基本性质 （1）在二叉树的第K层上，最多有2K-1（K=1）个结点。 （2）深度为m的二叉树最多2M-1个结点 （3）在任意一棵二叉树中，度为0的结点总是比度为2的结点多一个 （4）具有n个结点的二叉树，其深度至少为log2n+115.满二叉树、完全二叉树16.二叉树的3种遍历方法 （1）前序遍历 （2）中序遍历 （3）后序遍历17.查找技术 （1）顺序查找 （2）二分查找重点注意列出的4个要点18.排序技术 （1）交换类排序（冒泡/快速） （2）插入类排序（简单插入/希尔） （3）选择类排序（简单选择/堆排序）重点注意各种方法最坏情况下需要比较次数第2章程序设计基础考点1.程序设计方法主要两种 （1）结构化程序设计方法（又称为面向过程）； （2）面向对象程序设计方法2.结构化程序设计原则4点 （1）自顶向下 （2）逐步求精 （3）模块化 （4）限制使用goto语句3.对象基本特征5个 （1）标识唯一性 （2）分类性 （3）多态性 （4）封装性 （5）模块独立性4.面对对象的常用概念 （1）对象对象是由对象名、属性、操作3部分组成；对象的静态特殊称为属性；对象的动态行为称为方法；对象能识别到用户或系统的动作而做出响应称为事件 （2）类和实例； （3）封装； （4）消息； （5）继承 （6）多态性第3章软件工程考点1.软件的概念是包括程序、数据及相关文档的完整集合。 2.软件的分类 （1）应用软件（如Office、教务管理系统） （2）系统软件（如OS、DBMS） （3）支撑软件3.软件三要素 （1）工具（支持软件的开发、管理、文档生成）； （2）方法（是完成软件工程项目的技术手段）； （3）过程（支持软件开发的各个环节的控制与管理）4.软件研究的内容软件开发技术和软件工程管理5.软件生命周期（三大阶段）定义期（可行性研究/需要分析）；开发期（概要设计/详细设计/实现/测试与调试）；维护期（使用/维护/退役）6.需求分析阶段主要任务构画出软件系统基本模型；工具DFD、DD、结构化英语、判定树、判定表；本阶段产生的主要文档软件需求规格说明书（SRS）7.概要设计阶段主要任务设计模块及模块间联系；工具SC；本阶段产生的主要文档是概要设计说明书8.详细设计阶段的主要任务定义模块内部的算法、实现细节。 工具PFD、N-S图、判定表、PDL；本阶段产生的主要文档是详细设计说明书9.软件测试的任务尽可能多的发现错误；依据是软件需求规模说明书（SRS）10.软件调试的目的改正程序中的错误。 11.软件测试的方法静态测试和动态测试（按软件是否执行）；白盒与黑盒（按内外部功能进行分类）12.测试的实施4个步骤 （1）单元测试（对模块进行正确性检验的测试）； （2）集成测试（是测试和组装软件的过程）； （3）确认测试（依据软件需求规格说明书进行功能及特性测试）； （4）系统测试（在真实环境中试运行）13.设计出模块评价标准藕合性（模块与模块间联系的紧密程度）和内聚性（衡量一个模块内部语句间紧密程序）。 要求达到的目标是高内聚，低耦合。 第4章数据库设计考点1.数据库（DB）是数据的集合，具有统一的组织结构形式。 2.数据库管理系统（DBMS）是DB的管理机构，负责组织/操纵/维护/控制/服务等。 3.数据定义语言（DDL）负责数据库模式定义及物理构建。 4.数据操纵语言（DML）负责数据操纵功能5.数据控制语言（DCL）负责数据安全性定义、完整性定义、并发控制与故障恢复。 6.数据管理发展三个阶段人工管理、文件系统、数据库系统7.概念数据模型阶段用到的主要工具是E-R图（矩形表示实体集，菱形表示联系，椭圆表示属性）8.逻辑数据模型分为三种层次模型(用树形结构来表示)、网状模型(用网状结构图来表示)、关系模型(用二维表来表示)9.关系代数并、差、交、选择、投影、笛卡尔积、连接、自然连