笔试小结公共基础

总复习公共基础部分考点分析1数据的逻辑结构

数据的存储结构

数据的运算：插入、删除、查找、排序。线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构数据结构的三个方面：2考点1算法算法定义算法的5个基本特征算法的3种控制结构算法的6种设计方法时间复杂度空间复杂度3考点2：逻辑结构与存储结构逻辑结构定义分类：线性、非线性存储结构定义分类：顺序、链式两者关系：任何一种逻辑结构均可用任何一种存储结构实现存储。例如：顺序表、顺序栈、顺序队列、链表、链栈、循环队列；树的顺序存储、树的链式存储、图的顺序存储、图的；链式存储4考点3：线性结构与非线性结构以前件和后件的个数区分结构。线性结构顺序存储特点：逻辑相邻的存储位置也相邻。链式存储：逻辑相邻，存储位置不一定相邻。非线性结构顺序存储：链式存储5考点4：栈定义：后进先出（LIFO）。是一种特殊的线性表。元素计算：根据题目给出的栈顶指针位置计算。存储结构顺序存储的栈：一维数组链式存储的栈：链栈（链表）6考点5：队列定义：先进先出（FIFO），是一种特殊的线性表。记住：栈和队列均为线性表的特例，限定操作的线性表。存储结构：顺序存储：一维数组实现(循环队列)。链式存储：链队列。元素计数：尾指针-头指针。（若为负数则加上队列容量）7考点6：链表插入：删除：查找：*考查指针的移动题目较多p=p->next。8考点7：二叉树定义：考查度的问题；左右子树顺序是否能颠倒的问题。性质：最多结点个数；最后一层最多结点个数（叶子）；叶子-1=度为2结点数。满二叉树和完全二叉树的概念综合使用：二叉树中只有三类结点：度为2的+度为1的+度为0的。

三种遍历：前序、中序、后序9考点8：查找顺序查找1.适用范围：无序的顺序表、链表；有序的顺序表、链表均可。2.对长度为n的表，最坏情况下查找成功的时间复杂度是n，失败是n.二分法查找：适用范围：有序且采用顺序存储的表。时间复杂度：O(log2n)10考点9：排序最坏情况下比较次数、时间复杂度交换类：冒泡法：n(n-1)/2O(n2)快速法:n(n-1)/2O(n2)插入类：插入排序:n(n-1)/2O(n2)希尔排序:O(n1.5)选择类简单选择:n(n-1)/2O(n2)堆排序:O(nlog2n)最快11考点1:程序设计方法与风格清晰第一，效率第二源程序文档化；数据说明的方法；语句结构简单明了；输入输出易读；12考点2：结构化程序设计原则：自顶向下逐步求精模块化限制使用goto语句基本结构顺序结构选择结构循环结构13考点3：面向对象方法对象的特征：标识唯一性、分类性、多态性、封装性、模块独立性。类：具有共同属性、共同方法的对象的集合。一个对象是其类的一个实例。消息：实例之间传递的信息，类似函数调用。由三部分构成：接收消息的对象名、消息名、参数例：MyCircle.Show(GREEN);14考点1：软件工程基本概念软件：程序+数据+文档分类：系统软件+应用软件+工具软件软件工程：用工程的概念、原理、技术和方法指导软件开发。软件工程三要素：方法+工具+过程15考点2：软件的生命周期定义阶段问题定义、可行性研究、需求分析开发阶段概要设计、详细设计、编码、测试运行维护阶段使用、维护明确各阶段的任务。16考点3：需求分析阶段结构化分析方法：实质：着眼于数据流进行处理。结构化分析工具：数据流图（DFD)、数据字典（DD）、判定表、判定树等。最终文档：软件需求规格说明书（确定性最关键）。17考点4：软件设计概念：从技术上划分：结构设计、数据设计、接口设计、过程设计；从工程管理角度划分：概要设计、详细设计原则：

抽象、信息隐蔽、模块化、模块独立性。模块独立性标准度量：

高内聚、低耦合18考点4：软件设计概要设计

工具：SC（结构图）处理数据流（事务型、变换型）详细设计

工具：程序流程图、N-S图、PAD（问题分析图）、PDL（过程设计语言）。19考点5：软件测试目的：发现错误。准则：6条方法：以功能划分：白盒法（结构）、黑盒法（功能）以是否运行软件划分：静态测试、动态测试实施：单元测试、集成测试、确认测试、系统测试20考点6：程序的调试（Debug）任务：诊断并改正错误。主要在开发阶段进行。基本步骤：错误定位、修改、回归测试方法：强行排错法、回溯法、原因排除法21考点1：数据库基本概念数据数据库目标：解决数据共享问题数据库管理系统DBMS（核心）提供3种语言：数据定义语言、数据操纵语言、数据控制语言数据库系统DBS=DB+DBMS+DBA+硬件+软件22考点2：数据库系统发展及特点发展：人工管理阶段、文件系统阶段、数据库系统阶段（共享）特点：

共享；数据独立性：相对应用程序而言的。逻辑独立、物理独立23考点3：数据库系统的体系结构三级模式概念模式（逻辑模式）：一个数据库只有一个外模式（子模式）：一个概念模式可有多个外模式内模式：（物理模式），存储结构二级映射概念模式到内模式概念模式到外模式24考点4：数据模型数据模型：数据结构、数据操作、数据约束三部分组成。层次数据模型：树型结构。网状数据模型：网状结构。关系模型：二维表。一张表称一个关系。25考点5：关系模型概念：一个关系是一张二维表，但一张二维表不一定是一个关系。当二维表满足7条性质时才为一个关系：元组（有限、唯一、次序无关）、属性（名唯一、次序无关、分量值域统一）、元组分量具有原子性。四种操作：数据的插入、删除、查询、修改三种约束：实体完整性约束、参照完整性约束、用户自定义约束26考点6：E-R模型实体：矩形表示属性：椭圆表示联系：菱形一对一、一对多、多对多27考点7：关系代数五种基本运算：选择、投影、笛卡尔积、并、差扩充运算交：R交S=R-（R-S）28考点8：数据库设计两种方法：面向数据的方法：以信息需求为主（主流）面向过程的方法：以处理需求为主数据库设计的生命周期法：需求分析阶段概念设计阶段（设计E-R模型）逻辑设计阶段（将E-R模型