公共基础知识总结

1、第1章 数据结构与算法1、 数据的不可分割的基本单位是数据项。2、 算法的复杂度是执行算法所需要的计算工作量，取决于问题的规模和待处理数据的初态。3、 数据结构作为一门学科，主要讨论以下三方面的内容：1） 数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；2） 在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；3） 对各种数据结构进行的运算。4、 数据在计算机内存中的表示是指数据的存储结构。5、 在数据结构中，与所使用的计算机无关的数据结构是逻辑结构。6、 在数据结构中，从逻辑上可以把数据结构分成线性结构和非线性结构。7、 栈的特点：先进后出8、 队列的特点：

2、先进先出9、 树，二叉树，满二叉树，完全二叉树10、二叉树的遍历（前序，中序，后序）11、对线性表进行折半查找，要求线性表必须以顺序方式存储，且结点按关键字有序排列。12、查找技术1） 顺序查找2） 二分查找（即折半查找）13、排序技术3） 交换类排序（冒泡排序，快速排序）4） 选择类排序（简单选择排序，堆排序）5） 插入类排序（简单插入排序，西尔排序）各种排序方法时间、空间复杂度对比排序方法时间复杂度空间复杂度复杂性平均情况最坏情况最好情况简单插入（n2）（n2）（n）（1）简单冒泡（n2）（n2）（n）（1）简单西尔（nlog2n）（nlog2n）（1）较复杂快速（nlog2n）（n2）（

3、nlog2n）（nlog2n）较复杂简单选择（n2）（n2）（n2）（1）简单堆排序（nlog2n）（nlog2n）（nlog2n）（1）较复杂14、在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是选择排序。15、线性结构中元素之间存在一对一关系，树型结构中元素之间存在一对多的关系。16、在双向链表中，每个结点有两个指针域，一个指向前驱结点，一个指向后继结点。第2章 程序设计基础1、 程序设计经历了结构化设计（面向过程）和面向对象的程序设计阶段2、 良好的编程风格应注意的因素1） 源程序的文档化u 符号名的命名规则：具有一定的实际意义，便于理解程序功能u 正确的程序注释：注释分为

4、序言性注释和功能性注释。序言性注释常位于程序开头部分，它包括程序标题、程序功能说明、主要算法、接口说明、程序位置、开发简历、程序设计者、复审者、复审日期及修改日期等。功能性注释一般在源程序体之中，用于描述其后的语句或程序的主要功能。u 视觉组织：在程序中利用空格、空行、缩进等技巧使程序层次清晰。2） 数据说明的方法u 数据说明的次序规范化u 说明语句中变量安排有序化u 使用注释来说明复杂数据的结构3） 语句的结构为使程序简单易懂，应注意如下：u 一行写一条语句u 编写程序优先考虑清晰性u 程序编写要做到清晰第一，效率第二u 在保证程序正确的基础上再提高效率u 避免使用临时变量而使程序的可读性下

5、降u 避免不必要的转移u 尽量使用库函数u 避免采用复杂的条件语句u 尽量使用“否定”条件语句u 数据结构要有利于程序的简化u 要模块化，使模块功能尽可能单一u 利用信息隐蔽，确保每一个模块的独立性u 从数据出发去构造程序u 不要修补不好的程序，要重新编写4） 输入输出输入输出方式和风格应尽可能方便用户的使用，考虑如下原则：u 对输入数据要检验数据的合法性u 检查输入项的各种重要组合和合理性u 输入格式要简单，使得输入的步骤和操作尽可能简单u 输入数据时，应允许使用自由格式u 应允许缺省值u 输入一批数据时，最好使用输入结束标志u 在以交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提

6、示输入的请求，同时在数据输入过程中和输入结束时，应在屏幕上给出状态信息u 当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性3、 结构化程序设计的原则1） 自顶向下：先考虑总体后考虑细节，先考虑全局目标后考虑局部目标。2） 逐步求精：对复杂的问题，应设计一些子目标做过渡，逐步细化。3） 模块化：把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。4） 限制使用GOTO语句。4、 结构化程序的基本结构和特点1） 顺序结构2） 选择结构3） 重复结构（当型、直到型）5、 结构化程序设计原则和方法的应用结构化程序设计中，要注意把握如下要素：1）

7、 使用程序设计语言中的顺序、选择、循环等有限控制结构表示程序的控制逻辑2） 选用的控制结构只准许有一个入口和一个出口3） 程序语言组成容易识别的块，每块只有一个入口和一个出口4） 复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现5） 语言中所没有的控制结构，应该采用前后一致的方法来模拟6） 尽量避免GOTO语句的使用6、 面向对象的方法从计算机的角度来看，一个对象应包括两个要素：一是数据，二是需要进行的操作。对象就是一个包含数据以及与这些数据相关的操作的集合。7、 面向对象的优点：1） 与人类习惯的方法一致2） 稳定性好3） 可重用性好4） 易于开发大型软件产品5） 可维护性好8、 面向对象

8、方法的基本概念1） 对象具有属性（数据）和方法（行为方式）的实体叫对象。2） 类和实例属性、操作相似的对象归为类，类是具有共同属性、共同操作性质的对象集合，类是对象的抽象，而一个对象则是其对应类的一个实例。3） 消息对象之间进行通信的构造叫做消息，一个消息由下述三部分组成：接收消息的对象的名称消息标志符（消息名）零个或多个参数4） 继承（单继承，多继承）5） 多态性9、 信息隐蔽是通过封装性来实现的。10、类包括属性和行为两个主要部分，通过接口与外界发生关系。第3章 软件工程基础1、 软件的组成软件指的是计算机系统中与硬件相互依赖的另一部分，包括程序、数据和有关的文档。软件由两部分组成：1）

9、机器可执行的程序和数据2） 与软件开发、运行、维护及使用等有关的文档。2、 软件的特点1） 软件是逻辑产品，而不是物理实体，它具有无形性，通过计算机的执行才能体现它的功能和作用2） 没有明显的制作过程，其成本主要体现在软件的开发和研制上，可进行大量的复制3） 不存在磨损和消耗问题4） 软件的开发、运行对计算机系统具有依赖性5） 开发和维护成本高6） 软件开发涉及诸多社会因素3、 软件的分类：应用软件，系统软件，支撑软件4、 软件的产生和发展：程序设计时代，程序系统时代，软件工程时代5、 软件危机随着计算机软件规模的扩大，软件本身的复杂性不断增加，研制周期显著变长，正确性难以确保，软件开发费用上

10、涨，生产效率急剧下降，从而出现了人们难以控制软件发展的局面，既所谓的“软件危机”。6、 软件工程的产生为摆脱软件危机，提出“软件工程”的概念。软件工程三要素：方法，工具和过程。7、 软件工程过程：把输入转换成输出的一组彼此相关的资源和活动。包含：1） 软件规格说明 2）软件开发 3）软件确认 4）软件演进8、 软件生命周期：软件产品从提出、实现、使用维护到停止使用退役的过程。包括8个阶段：可行性研究与计划，需求分析，概要设计，详细设计，实现，综合测试，确认测试，使用与维护。10、软件工程的目标与原则软件工程研究的内容主要包括软件开发技术：软件开发方法学、开发过程、开发工具和软件工程环境软件工程

11、管理：软件管理学、软件工程经济学、软件心理学等内容软件工程原则包括：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。11、软件开发工具与软件开发环境1） 软件开发工具：协助开发人员进行软件开发活动所使用的软件或环境，包括需求分析工具，设计工具、编码工具、排错工具、测试工具等。2） 软件开发环境：支持软件产品开发的软件系统，由软件工具集和环境集成机制构成。12、可行性研究1） 经济可行性研究 2）技术可行性研究（风险分析、资源分析和技术分析）3） 法律可行性分析 4）开发方案的选择性研究13、需求分析方法需求分析工作：需求获取、需求分析、编写需求规格说明书、需求审评需求分析方法

12、：结构化分析方法（包括面向数据流的结构化分析方法、面向数据结构的Jackson方法、面向数据结构的结构化数据系统开发方法）和面向对象的分析方法14、结构化分析方法的步骤：1） 通过对用户的调查，以软件的需求为线索，获得当前系统的具体模型2） 去掉具体模型中的非本质因素，抽象出当前系统的逻辑模型3） 根据计算机的特点分析当前系统与目标系统的差别，建立目标系统的逻辑模型4） 完善目标系统并补充细节，写出目标系统的软件需求规格说明5） 评审直到确认完全15、结构化分析常用工具1） 数据流图 2）数据字典 3）判定树 4）判定表16、结构化方法开发过程：计划期、开发期、运行期计划期：主要任务是分析新系

13、统应设定的目标、分析用户的基本需求。开发期：包括分析、设计和实施两类任务。其中分析、设计包括需求分析、总体设计和详细设计3个阶段，实施则包括编码和测试两个阶段。运行期：主要任务是软件维护。17、软件需求规格说明书1） 软件需求规格说明书的作用u 便于用户、开发人员进行理解和交流u 反映出用户问题的结构，可以作为软件开发工作的基础和依据u 作为确认测试和验收的依据2） 软件需求规格说明书的内容概述数据描述功能描述性能描述参考文献3） 软件需求规格说明书的特点正确性无歧异性完整性可验证性一致性可理解性可修改性可追踪性18、软件设计的基本原理（抽象，模块化，信息隐蔽，模块独立性）内聚性：度量一个模块

14、功能强度的一个相对指标；耦合性：度量模块之间的相互联系程度。19、概要设计任务1）设计软件系统结构 2）数据结构和数据库设计 3）编写概要设计文档 4）评审20、面向数据流的设计方法数据流类型：变换型和事物型21、程序流程图的5种控制结构：1）顺序型 2）选择型 3）先判断重复型 4）后判断重复型 5）多分支选择型22、软件测试技术与方法白盒测试：即结构测试，与程序内部结构相关，要利用程序结构的实现细节设计测试实例。黑盒测试：不关心程序内部的逻辑，只是根据程序的功能说明来设计测试用例。23、软件测试的过程(单元测试、集成测试、确认测试、系统测试)24、程序调试的步骤：1） 错误定位2） 修改设

15、计和代码，以排除错误3） 进行回归测试，防止引进新的错误25、程序调试的原则：确定错误的性质和位置时的注意事项：1）分析思考与错误征兆有关的信息2）避开死胡同3）只把调试工具当作辅助手段来使用4）避免用试探法，最多只能把它当作最后手段修改错误的原则： 1）在出现错误的地方，很可能有别的错 2）修改错误的一个常见失误是只修改错误征兆，而没有修改错误本身 3）注意修正一个错误的同时有可能会引入新的错误 4）修改错误的过程将迫使人们暂时回到程序设计阶段 5）修改源代码程序，不要改变目标代码26、程序调试方法1）强行排错法 2）回溯法 3）原因排除法27、在进行软件结构设计时应该遵循的最主要的原理是模

16、块独立。28、软件调试的目的是改正错误。29、概要设计的结果是提供一份模块说明书。第4章 数据库设计基础1、 数据库：长期存储在计算机内、有组织的、可共享的大量数据的集合。数据库管理系统：是一种系统软件，负责数据库中的数据组织、数据操作、数据维护、数据控制及保护和数据服务等。数据库管理系统提供相应的数据语言：数据定义语言，数据操纵语言，数据控制语言。数据库系统构成：数据、数据库管理系统、应用系统、数据库管理员、硬件平台、软件平台。2、 数据库系统的发展1）人工管理阶段 2）文件系统阶段 3）数据库系统阶段3、 数据库系统的特点1） 数据的集成性2） 数据的高共享和低冗余性3） 数据的独立性4） 数据的统一管理与控制4、 数据库系统的内部结构体系3级模式：概念模式（逻辑模式，1个）、外模式（子模式，多个）、内模式（物理模式，1个）两级映射：概念模式到内模式的映射，外模式到概念模式的映射5、 ER模型的基本概念1） 实体：客观存在又能相互区别的事物2） 属性：事物的特性，刻画实体的特征3） 码：惟一标志实体的属性集4） 域：属性的取值范围5） 实体型：用实体名及其属性名集合来抽象和刻画同类实体6） 实体集：同类实体的集合7） 联系：实体集间的一定关系（一对一，一对多，多对多）6、 层次模型、网状模型、关系模型1） 关系模型采用二