公共基础知识复习要点上（红色为要点）第一章一、算法：1、基本概念：是解题方案的准确而完整的描述。

有可行性，确定性，有穷性，拥有足够的情报四个基本特征。

有数据对象的运算和操作和算法的控制机构。

基本的运算和操作包括算数运算、逻辑运算、关系运算、数据传输。

算法的控制机构分为顺序、选择、循环三种基本结构。

2、复杂度：包括时间复杂度和空间复杂度。

时间复杂度是指执行算法所需要的计算工作量用算法的基本运算次数来度量。

空间复杂度指执行这个算法所需要的内存空间。

二、数据结构：1、数据逻辑结构包含数据元素的信息和各数据元素之间的前后件关系。

分为线性结构和非线性结构。

线性结构只有一个根节点，最多只有一个前件也最多有一个后件。

2、数据存储结构是逻辑结构在计算机存储空间中的存放形式。

也称数据的物理结构。

分为顺序、链接，索引。

不同的存储结构，数据处理的效率是不同的。

三、线性表及顺序存储结构1、线性表式最简单、最常用的一种数据结构。

2、顺序存储结构有存储空间是连续的和各数据元素在存储空间中按逻辑顺序依次存放的。

3、顺序存储结构插入和删除运算不太方便，平均情况下要移动一半的元素。

顺序存储结构适合小线性表和元素不常变动的线性表，不适合元素经常变动的大线性表。

四、栈和队列1、栈限定在一端进行插入和删除的线性表。

特点是先进后出或后进先出。

2、队列是允许在一端进行插入而在另一端进行删除的线性表。

特点是先进先出或后进后出。

3、队列的顺序存储结构一般是循环队列的形式。

4、循环队列中元素个数计算公式。

尾指针>头指针时尾指针-头指针例如：容量为15的循环队列中，头指针为6，尾指针为9，循环队列中共有（）个元素。

答:9-6=3尾指针<头指针时尾指针-头指针+容量.例如：容量为15的循环队列中，头指针为6，尾指针为3，循环队列中共有（）个元素。

答:3-6+15=125、栈中元素个数的计算。

栈顶-栈底+1例如：已知栈顶指针为8，栈底指针为1，栈中共有8个元素。

五、线性链表1、线性表的链式存储结构称为线性链表。

2、链式存储结构中存储空间可以不连续，存储顺序与逻辑关系可以不一致。

逻辑关系可以不一致。

3、链式存储方式既可以表示线性结构，也可以表示非线性结构。

4、带链的栈和带链的队列。

六、树与二叉树1、树：是一种简单的非线性结构。

没有前件的节点叫根结点。

没有后件的节点叫叶子结点。

一个结点拥有的后件个数称为该结点的度。

根结点在第1层，所有子结点在下一层，树的最大层次称为数的深度。

树在计算机中用多重链表表示2、二叉树：（1）基本性质：性质1：第k层上最多2k-1个结点。

例如：深度为5的满二叉树中叶子结点的个数是(16)个。

答：求第5层节点共25-1=16个性质2：深度为m的二叉树最多有2m-1个结点。

性质3：度为0的节点（叶子结点）总是比度为2的节点多一个。

例如，已知度为2的节点50个，求叶子结点数（51）已知叶子结点50个，度为1的节点50个，求总结点数（50+50+49=149个）性质4:：n个结点的二叉树，深度至少为[log2n] +1（2）满二叉树和完全二叉树：满二叉树：每一层上的节点数达到最大值，第K层上有2k-1个节点，深度为m的满二叉树有2m-1个节点。

完全二叉树：除最后一层外，每一层上的节点数达到最大值，最后一层缺右边的若干节点。

完全二叉树中已知总结点求叶子结点公式：总结点/2例如：完全二叉树共有700个结点，则有（350）个叶子结点，度为2的节点(349)个，度为1的节点（1）个完全二叉树共有701个结点，则有（351）个叶子结点，度为2的节点(350)个，度为1的节点（0）个（3）二叉树采用链式存储结构。

（4）二叉树的遍历。

前序（根左右）中序（左根右）后序（左右根）遍历方法注意上课笔记。

例:P48 选择第7题和填空第3题七、查找1、查找分为顺序查找和二分法查找。

2、二分法查找只适用于顺序存储的有序表。

最坏情况下二分查找只需要比较Log2n次，顺序查找比较n 次。

八、排序：1、冒泡排序法、简单插入排序法、简单选择排序法德比较次数为n(n-1)/2。

2、希尔排序的比较次数为n1.53、堆排序的比较次数为nLog2n第二章一、程序设计方法与风格。

1、程序设计方法经过了结构化程序设计和面向对象的程序设计阶段。

2、程序设计风格：清晰第一，效率第二3、符号名的命名要具有实际含义，注释分为序言性注释和功能性注释。

二、结构化程序设计1、原则：自顶向下、逐步求精、模块化、限制使用goto语句。

2、三种基本结构：顺序结构、选择结构（分支结构）、重复结构（循环结构）三、面向对象的程序设计1、面向对象方法已经成为主流的软件开发方法。

优点：（1）与人类习惯的思维方法一致（2）稳定性好（3）可重用性好（4）易于开发大型软件产品（5）可维护性好2、基本概念：对象：表示客观世界中的任何实体。

对象的基本特点：标示唯一性、分类性、多态性、封装性、模块独立性好。

类：具有共同属性，共同方法的对象的集合。

实例：指一个具体的对象。

消息：一个实例与另一个实例之间传递的信息。

继承：能够直接获得已有的性质和特征，而不必重复定义它们。

多态：同样的消息被不同的对象接受时可导致完全不同的行动。

公共基础知识复习要点下（红色为要点）第三章一、软件工程的基本概念：1、软件包括程序、数据和文档组成。

2、软件分为应用软件、系统软件、支持软件（工具软件）3、软件危机是成本、质量、生产率的问题。

4、软件工程三要素：方法、工具和过程。

5、软件工程过程是把输入转化为输出的一组彼此相关的资源和活动。

6、软件工程过程包括软件规格说明、软件开发、软件确认、软件演进。

7、软件生命周期分为软件定义、软件开发、软件运行和维护三个大的阶段。

软件定义分为：可行性研究和计划制定、需求分析。

软件开发分为：概要设计、详细设计、实现、测试软件运行和维护分为：使用、维护、退役8、软件工程内容包括软件开发技术和软件工程管理。

9、软件工程的原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性、可验证性。

10、软件开发环境是全面支持软件开发全过程的软件工具集合。

二、结构化分析方法：1、需求分析阶段的工作：需求获取、需求分析、编写需求规格说明书、需求评审。

2、面向数据流的分析方法（SA）、面向数据结构的Jackson方法(JSD)面向数据结构的结构化数据系统开发方法(DSSD) 面向对象的分析方法(OOA)3、数据流图（DFD）：椭圆代表加工（转换）、箭头代表数据流、双横线代表存储文件、矩形代表源、潭P67面的图形。

4、数据字典是结构化分析方法的核心。

三、结构化设计方法：1、软件设计是把软件需求转换为软件表示的过程。

2、从技术观点看：软件设计分为软件结构设计、数据设计、接口设计、过程设计。

3、从工程管理角度看：软件设计分概要设计和详细设计两步。

4、软件设计的基本原理：（1）抽象（2）模块化（3）信息隐蔽（4）模块独立性5、优秀软件设计要做到：高内聚低偶合。

6、概要设计的任务：设计软件系统结构、数据结构及数据库设计、编写概要设计文档、概要设计文档评审。

7、结构图(SC) P76图3.88、数据流类型有变换型和事务型两种9、详细设计为模块实现算法和局部数据结构。

10、程序流程图P81 图3.17N-S图：避免了流程图的随意性和灵活性。

PAD图问题分析图PDL 结构化的英语和伪码。

四、软件测试：1、软件测试成本占总成本的40%以上。

2、软件测试的目的是发现错误。

3、软件测试的准则：（1）所有测试都应追溯到需求。

（2）严格执行测试计划，排除测试的随意性。

（3）充分注意测试中的群集现象（4）程序员应避免检查自己的程序。

（5）穷举测试不可能（6）妥善保存测试计划、测试用例、出错统计和最终分析报告。

这个一般是选择题哪一个是错误的。

4、软件测试从是否执行软件的角度测试分为静态测试和动态测试。

按功能分为白盒测试和黑盒测试（1）白盒测试（结构测试或逻辑驱动测试）：看成打开的盒子，利用内部逻辑结构选择测试用例。

主要方法有逻辑覆盖和基本路径测试（2）黑盒测试（功能测试或数据驱动测试）：不考虑内部逻辑结构，主要用于软件确认测试。

主要方法有等价类划分法、边界值分析法、错误推测法、因果图5、软件测试分单元测试、集成测试、验收测试（确认测试）、系统测试4个步骤。

6、驱动模块是被测模块的主程序，桩模块是一个模拟子程序。

7、确认测试是验证是否满足需求规格说明中的需求。

主要用黑盒测试方法。

五、程序调试1、程序调试是诊断和改正程序中的错误。

2、程序调试的步骤：（1）错误定位（2）修改设计和代码排除错误（3）进行回归测试，防止引进新的错误。

第四章一、数据库系统基本概念：1、数据是描述事物的符号记录。

2、数据库（DB）是数据的集合，有集成和共享的特点。

3、数据库管理系统(DBMS)是数据库系统的核心，它是一种系统软件。

4、数据定义语言(DDL)、数据操纵语言(DML)、数据控制语言(DCL)5、上面的数据语言按使用方式分为交互式语言和宿主型语言。

6、严格意义的DBMS包括Oracle、DB2、SQLServer。

小型数据库有Visual FoxPro和Access。

7、数据库管理员(DBA)的工作是（1）数据库设计（2）数据库维护（3）改善系统性能，提高系统效率。

8、数据库系统（DBS）由数据库、数据库管理系统、数据库管理员、硬件平台和软件平台五部分组成硬件平台包括计算机和网络。

网络数据库系统结构形式以客户机/服务器（C/S）和浏览器/服务器（B/S）方式为主。

软件平台包括操作系统：Unix（包括Linux）和Windows两种数据库系统开发工具：可视化开发工具VB、PB和Delphi9、数据库应用系统由数据库系统、应用软件和应用界面组成。

10、数据库系统发展经历了人工管理阶段、文件系统阶段、数据库系统阶段11、数据库系统基本特点：（1）数据集成性（2）数据的高共享性和低冗于性。

（3）数据独立性（4）数据统一管理和控制12、数据独立性分为物理独立性和逻辑独立性两级。

（1）物理独立性：是物理结构的改变不影响逻辑结构，不会引起应用程序的变化。

（2）逻辑独立性：总体逻辑结构的改变不不会引起应用程序的变化。

13、数据库系统三级模式。

（1）概念模式:是全局数据逻辑结构的描述是全体用户的公共数据视图。

（2）外模式：用户的数据视图。

（3）内模式：数据库物理存储结构和物理存取方法。

14、数据库系统两级映射。

（1）概念模式到内模式的映射：实现数据的物理独立性。

（2）外模式到概念模式的映射：实现数据的逻辑独立性。

二、数据模型：1、数据模型描述的内容：数据结构、数据操纵、数据约束。

2、数据模型按不同的应用层次分为三种类型：概念数据模型、逻辑数据模型、物理数据模型。