主要参考：
全国计算机等级考试二级教程-公共基础知识（2020年版）
全国计算机等级考试二级公共基础知识考试大纲（2020年版）
１． 掌握计算机系统的基本概念，理解计算机硬件系统和计算机操作系统。 ２． 掌握算法的基本概念。 ３． 掌握基本数据结构及其操作。 ４． 掌握基本排序和查找算法。 ５． 掌握逐步求精的结构化程序设计方法。 ６． 掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。 ７． 掌握数据库的基本知识，了解关系数据库的设计。
算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。
算法：解题方案的准确而完整的描述 算法的基本特征：1.可行性；2.确定性；3.有穷性；4.拥有足够的情报
算法的时间复杂度：执行算法所需的计算工作量 算法的空间复杂度：执行算法所需的内存空间
数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。
数据结构：反映数据元素之间关系的数据元素集合的表示；
数据的逻辑机构：反映数据元素之间逻辑关系的数据结构； 数据的存储结构：数据的逻辑结构在计算机存储空间中的存放形式；
线性结构（线性表）： 一个非空的数据结构满足下列两个条件： 1.有且只有一个根结点； 2.每一个结点最多只有一个前件，也最多只有一个后件； 非线性结构：不是线性结构，则为非线性结构
线性表的定义；线性表的顺序存储结构及其插入与删除运算。
数据元素可以是简单向，也可以由若干数据组成，即复杂线性表。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录（record），而由多个记录构成的线性表又称为文件（file）。 线性表中，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。
线性表的顺序存储结构（顺序分配）两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 线性表的顺序存储结构适用于小线性表，但对于元素经常需要变动的大线性表不适用，因为插入与删除操作效率较低。
栈和队列的定义；栈和队列的顺序存储结构及其基本运算。
栈 （中文zhan四声，英文stack）：限定在一端进行插入与删除的线性表。 栈顶：允许插入与删除的一端，指针top来指示栈顶； 栈底：不允许插入与删除的一端，bottom指向栈底； 又称LIFO（先进后出表）或FILO（后进先出表），栈具有记忆作用。 栈的基本运算 入栈运算：在栈顶位置中插入一个新元素； 退栈运算：取出栈顶元素并赋给一个指定变量； 读栈顶元素：将栈顶元素赋给一个指定变量。
队列（Queue）：允许在一端进行插入、而在另一端进行删除的线性表。 队尾：允许插入的一端，由尾指针（rear）指向队尾元素 队头（排头）：允许删除的一端，由排头指针（front）指向排头元素的前一个位置 又称“先进先出”（first in first out ，FIFO）或“后进后出”(last in last out , LILO)的线性表 循环队列：将队列存储位置的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。 入队运算（enqueue）：在循环队列的队尾加入一个新元素 退队运算（dequeue）：在循环队列的排头位置退出一个元素并赋值给指定的变量 s = 0 表示队列空 s = 1 表示队列非空 判断队列空与队列满的条件： 队列空： s=0 队列满： s=1 且 front = rear
存储结点（结点）：数据结构中每一个数据结点对应的存储单元 链式存储结构：在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的) 每个存储单元由数据域和指针域两部分组成： 数据域：用于存放数据的元素值 指针域：用于存放指针 指针：用于指向该结点的前一个或后一个结点（即前件或后件） 在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。 链式存储方式即可用于表示线性结构，也可用于表示非线性结构。
线性链表：线性表的链式存储结构 头指针：HARD，指向线性链表中第一个数据元素的结点； 线性链表的最后一个结点的指针域为空（用NULL或0表示），表示链表终止。 线性单链表：每一个结点只有一个指针域，由这个指针只能找到后结点，但不能找到前件结点。 双向链表：每个结点有两个指针，一个左指针（Llink），用以指向其前件结点；另一个成为右指针（Rlink），用以指向其后件结点。
带链的栈： 可利用栈：实际应用中可以用来收集计算机存储空间中所有空闲的存储结点。 带链栈的基本操作 栈的初始化：即建立一个空栈 入栈运算 退栈运算 读栈顶元素
带链的队列
循环链表统一空表和非空表的运算 特点： 1.增加表头结点，指针域指向第一元素结点； 2.最后一个结点指针域不是空，而是指向表头结点。 优势： 1.只要指出任意一个结点的位置，就可以从它出发的访问到表中其他所有结点 2.至少有一个结点存在，从而使空表与非空表运算统一。
树： 父结点：每个结点只有一个前件； 根结点（树的根)：没有前件的结点； 子结点：结点的多个后件； 叶子结点：没有后件的结点； 度：一个结点所拥有的后件个数； 树的度：所有结点中最大的度； 树的深度：树的最大层次； 子树以某结点为根构成的树； 表达式树：表示表达式的树； 可以用树结构表示算术表达式
二叉树的特点： 1.非空二叉树只有一个跟结点； 2.每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
二叉树的基本性质 性质1：在二叉树的第k层上，最多有2^(k-1)(k>=1)个结点； 性质2：深度为m的二叉树最多有2^m-1个结点； 性质3：任意一颗二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个; 性质4：具有n个结点的二叉树，其深度至少为[log2 n]+1,其中[log2 n]表示[log2 n]以2为底的n的整数部分。
满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。 完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点；
性质5：具有n个结点的完全二叉树的深度为[log2 n]+1 性质6：设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1,2，...，n结点进行编号，则对于编号为k（k=1,2,3，...,n）的结点有以下结论： （1）若k=1，则1.若k=1，则该结点为根结点，它没有父结点；若k>1,则该结点的父结点编号为INT（k/2) （2）若2k<=n，则编号为k的结点的左子结点编号为2k；否则该结点无右子结点。 （3）若2k+1<n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。
二叉树的存储结构 通常采用链式存储结构。
二叉树的遍历：不重复地访问二叉树中的所有结点。 前序遍历（DLR）：访问根结点；前序遍历左子树；前序遍历右子树 中序遍历（LDR）：中序遍历左子树；访问根结点；中序遍历左子树 后序遍历（LRD）：后序遍历左子树；后序遍历右子树；访问根结点 已知前序、中序遍历或者后序、中序遍历可以唯一恢复该二叉树，但是已知前序和后序序列不能唯一恢复二叉树。
查找：在一个给定的数据结构中查找某个特定元素。 顺序查找（顺序搜索）： 只能采用顺序查找的情况： 1.线性表为无序表 2.采用链式存储结构的有序线性表
二分法查找（对分查找）： 只适用于顺序存储的有序表
交换类排序：通过数据元素的交换逐步消除逆序 冒泡排序 快速排序 最坏情况需要n(n-1)/2次比较，实际效率比冒泡排序高
选择类排序： 简单选择排序法：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用相同的方法，直至子表空为止。 堆排序法：
插入类排序：将无序序列中的各元素一次插入到已经有序的的线性表中 简单插入排序：只包含一个元素的字表可以看成是有序表，从线性表的第2个元素开始逐次将其中每一个元素插入到前面已经有序的子表中。 希尔排序法：将整个无序序列分割成若干小的子序列分别进行插入排序 子序列的分割方法：将相隔n个增量h的元素构成一个子序列。在排序过程中，逐次减少这个增量，最后当h减少到1时，进行一次插入排序，排序就完成了。
考虑以下因素： （1）源程序文档化 （2）数据说明方法 （3）语句的结构 （4）输入和输出
1.自顶向下 2.逐步求精 3.模块化 4.限制使用goto语句
1.顺序结构 2.选择结构（分支结构） 3.循环结构：当型循环和直到型循环
优点： 1.与人类习惯的思维方式一致 2.稳定新好 3.可重用性好 4.易于开发大型软件 5.可维护性好
对象（object）：由描述该对象属性的数据以及可以对这些数据施加的所有操作封装在一起构成的统一体。 对象的基本特征：标识唯一性、分类性、多态性、封装性、模块独立性好 类（class）：具有共同属性、共同方法的对象集合 实例（instance）： 消息（message）：一个实例与另一个实例之间传递的信息。 继承（inheritance）：能够直接获得已有的性质和特征，而不必重复定义他们。 继承具有传递性。 单继承：一个类只允许有一个父类； 多重继承：一个类允许有多个父类 多态性（polymorphism）：对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时可导致完全不同的行动
软件：与计算机系统的操作有关的计算机程序、规程及可能的相关文档的完整集合 应用软件：为解决特定领域的应用而开发的软件 系统软件：计算机管理自身资源，提高计算机使用效率并服务于其他程序的软件 支撑软件：介于系统软件和应用软件之间，协助用户开发软件的工具性软件。
软件工程：应用计算机科学理论和技术以及工程管理原则和方法，按照预算和进度，实现满足用户要求的软件产品的定义、开发、发布和维护的工程或进行研究的学科
软件工程三要素：方法、工具和过程。
以下选项中描述正确的是 A、软件工程主要解决软件产品的生产率问题 B、软件工程的主要思想是强调软件开发过程中需要应用工程化原则 C、软件工程只是解决软件项目的管理问题 D、软件工程只是解决软件开发中的技术问题 正确答案 B
软件生命周期 定义阶段 开发阶段 维护阶段
实质是着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。
关于结构化程序设计方法原则的描述，以下选项中错误的是 A、模块化 B、多态继承 C、逐步求精 D、自顶向下 正确答案 B
例题：为了避免流程图在描述程序逻辑时的灵活性，提出了用方框图来代替传统的程序流程图，这种图的名称是 A、PAD图 B、结构图 C、数据流图 D、N-S图
正确答案 D
是需求分析阶段得出的最主要的文档。 软件需求规格说明书的作用：
- 便于用户、开发人员进行理解
- 反映出用户问题的结构，可以作为软件开发工作的基础和依据。
- 作为确认测试和验收测试的依据
- 为成本估算和编制计划进度提供基础
- 软件不断改进的基础
例题：软件需求规格说明书的作用不包括 A、便于用户、开发人员进行理解和交流 B、作为确认测试和验收的依据 C、反映出用户问题的结构，可以作为软件开发工作的基础和依据 D、只便于开发人员进行需求分析
正确答案 D
软件需求规格说明书的特点：有正确性、无歧义性、完整性、可验证性、一致性、可理解性、可修改性和可追踪性。其中最重要的是无歧义性。
软件设计基本原理：
-
抽象
-
逐步求精和模块化
-
信息隐蔽和局部化
信息隐蔽是指所设计的模块是的
-
模块独立性
从技术观点上看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。 （1）结构设计定义软件系统各主要部件之间的关系； （2）数据设计将分析时创建的模型转化为数据结构的定义； （3）接口设计是描述软件内部、软件和协作系统之间以及软件与人之间如何通信； （4）过程设计则是把系统结构部件转换为软件的过程性描述。
从工程管理角度来看，软件设计分两步完成：概要设计和详细设计。 （1）概要设计将软件需求转化为软件体系结构、确定系统级接口、全局数据结构或数据库模式； （2）详细设计确立每个模块的实现算法和局部数据结构，用适当方法表示算法和数据结构的细节。
软件设计包括软件的结构、数据接口和过程设计，其中软件的过程设计是指 A、软件开发过程 B、模块间的关系 C、软件层次结构 D、系统结构部件转换成软件的过程描述
正确答案 D
软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。
软件测试的准则：
- 所有测试都应追溯到需求
- 严格执行测试计划，排除测试的随意性
- 充分注意测试中的群集现象。程序中存在错误的概率与该程序中已发现的错误数成正比。为了提高测试效率，测试人员应该集中对付哪些错误群集的程序。
- 程序员应避免检查自己的程序
- 穷举测试不可能。穷举测试是把程序所有可能的执行路径都进行检查，即使小规模的程序的执行路径数也相当大，不可能穷尽，说明测试只能证明程序有错，不能证明程序中无错。
- 妥善保存测试计划，测试用例、出错统计和最终分析报告，为维护提供方便。
为了提高测试的效率，应该 A、集中对付那些错误群集的程序 B、在完成编码以后制定软件的测试计划 C、随机选取测试数据 D、取一切可能的输入数据作为测试数据
正确答案 A
白盒测试（结构测试或逻辑驱动测试）
白盒测试的基本原则：
（1）保证所测模块中每一独立路径至少执行一次。
（2）保证所测模块所有判断的每一分支至少执行一次。
（3）保证所测模块每一循环都在边界条件和一般条件下至少各执行一次。
（4）验证所有内部数据结构的有效性。
按照白盒测试的基本原则，“白盒”法是穷举路径测试。
白盒测试的主要方法：逻辑覆盖，基本路经测试。
例题：在软件工程中，白盒测试法可用于测试程序的内部结构。下列选项中描述正确的是 白盒测试法将程序看作地址的集合 白盒测试法将程序看作目标的集合 白盒测试法将程序看作循环的集合 白盒测试法将程序看作路径的集合
正确答案 D
黑盒测试（功能测试或数据驱动测试）
是把程序看成一只黑盒子，测试者完全不了解，或不考虑程序的结构和处理过程。它根据规格说明书的功能来设计测试用例，检查程序的功能是否符合规格说明的要求。
黑盒测试的方法：等价划分法，边界值分析法，错误推测法。
单元测试： 集成测试： 确认测试（验收测试）：验证软件功能和性能及其他特性是否满足了需求规格说明中确定的各种需求以及软件配置是否完全正确。 系统测试：
例题：检查软件产品是否符合需求定义的测试是 A、验证测试 B、确认测试 C、集成测试 D、系统测试
答案：B
程序调试的任务是诊断和改正程序中的错误。
程序调试和软件测试的区别： （1）软件测试是尽可能多地发现软件中的错误，而程序调试先要发现软件的错误，然后借助于一定的调试工具去执行找出软件错误的具体位置。 （2）软件测试贯穿整个软件生命期，调试主要在开发阶段。
软件调试的目的是 A、改善软件的性能 B、挖掘软件的潜能 C、发现错误 D、改正错误
正确答案 D
程序调试的基本步骤：
（1）错误定位。从错误的外部表现形式入手，研究有关部分的程序，确定程序中出错位置，找出错误的内在原因；
（2）修改设计和代码，以排除错误；
（3）进行回归测试，防止引进新的错误。
软件调试可分为静态调试和动态调试。
静态调试主要是指通过人的思维来分析源程序代码和排错，是主要的设计手段，而动态调试是辅助静态调试的。
软件调试方法：
- 强行排错法
- 回溯法
- 原因排除法，包括演绎法，归纳法和二分法。
例题：以下选项中，不属于软件调试技术的是 A、原因排除法 B、强行排错法 C、回溯法 D、集成测试法
答案：D
**数据（Data）**是数据库存储的基本对象，是描述事物的符号记录。
**数据库（DB）**是长期储存在计算机内、有组织的、可共享的大量数据的集合，它具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序所共享，所以数据库技术的根本目标是解决数据共享问题。
**数据库管理系统（DBMS）**是数据库的管理机构，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等。数据库管理系统是数据库系统的核心。数据库系统包含数据库和数据库管理系统。 数据库管理系统的功能： （1）数据模式定义：即为数据库构建其数据框架； （2）数据存取的物理构建：为数据模式的物理存取与构建提供有效的存取方法与手段； （3）数据操纵：为用户使用数据库的数据提供方便，如查询、插入、修改、删除等以及简单的算术运算及统计； （4）数据的完整性、安全性定义与检查； （5）数据库的并发控制与故障恢复； （6）数据的服务：如拷贝、转存、重组、性能监测、分析等。
数据语言 数据定义语言（DDL）：负责数据模式定义和数据物理存取构建。 数据操纵语言（DML）：负责数据的操纵，包括查询及增删改等操作。 数据控制语言（DCL）：负责数据完整性，安全性的定义与检查以及并发控制，故障恢复等功能。 数据语言按使用方式具有两个结构形式：交互式命令语言（自含型和自主型语言）和宿主型语言。
数据库管理员（DBA）的工作：数据库设计，数据库维护，改善系统性能，提高系统效率。
**数据库系统（DBS）**是指在计算机系统中引入数据库后的系统，一般由数据库、数据库管理系统、应用系统、数据库管理员和用户构成。
**数据库应用系统（DBAS）**是数据库系统再加上应用软件及应用界面这三者所组成，具体包括：数据库、数据库管理系统、数据库管理员、硬件平台、软件平台、应用软件、应用界面。
1.数据的高集成性 2.数据的高共享性和低冗余性 3.数据高独立性 4.数据统一管理与控制。
数据独立性是数据与程序间的互不依赖性，即数据库中的数据独立于应用程序而不依赖于应用程序。数据的独立性一般分为物理独立性与逻辑独立性两种。 （1）物理独立性：当数据的物理结构（包括存储结构、存取方式等）改变时，其逻辑结构，应用程序都不用改变。 （2）逻辑独立性：数据的逻辑结构改变了，如修改数据模式、增加新的数据类型、改变数据间联系等，用户的应用程序可以不变。
概念模式：数据库系统中全局数据逻辑结构的描述，全体用户（应用）公共数据视图。
外模式（子模式或用户模式）：用户的数据视图，由概念模式推导而出。
内模式（物理模式）：数据库物理存储结构与物理存取方法。
数据模型是数据特征的抽象，从抽象层次描述了系统的静态特征、动态行为和约束条件，为数据库系统的信息表示与操作提供一个抽象框架。
数据模型描述内容包括：数据结构、数据操作和数据约束。
概念数据模型（概念模型）：是一种面向客观世界，面向用户的模型，不涉及具体的硬件环境和平台也与具体的软件环境无关的模式，它是整个数据模型的基础。 逻辑数据模型（数据模型）：它是一种面向数据库的模型。分为层次模型，网状模型，关系模型和面向对象模型，其中层次模型和网状模型统称为非关系模型。层次模型用树型结构表示实体之间联系的模型。 物理数据模型（物理模型）：它是一种面向计算机物理表示的模型。数据模型在计算机上的物理结构的表示。
Ｅ-Ｒ 图
从 Ｅ－Ｒ 图导出关系数据模型
关系代数运算
集合运算及选择、投影、连接运算，
数据库规范化理论
关系代数是一种抽象的查询语言，关系代数的运算对象是关系，运算结果也是关系。运算对象，运算符和运算结果是运算的三大要素。集合运算符，专门的运算符，算术比较符和逻辑运算符。
关系模型的基本运算：（1）插入 （2）删除 (3)修改 （4）查询（包括投影、选择、笛卡尔积运算）还有扩充运算交、除、连接及自然连接运算。
关系代数的5个基本操作中并，差，交，笛卡尔积是二目运算。
设关系R和S具有相同的关系模式
1、并：R和S的并是由属于R或属于S的所有元组构成的集合。
2、差：R和S的差是由属于R但是不属于S的元组构成的集合
3、笛卡尔积：设R和S的元数分别为r和s，R和S的笛卡尔积是一个（r+s）元的元组集合，每个元组的前r个分量来自R的一个元组，后s个分量来自S的一个元组。运算后得到的新表的元组数是R*S，属性是r+s。
4、交：属于R又属于S的元组构成的集合。
5、投影：一元运算，对一个关系进行垂直切割，消去某些列，并重新按排列的顺序。
6、选择：一元运算，根据某些条件对关系进行水平分割。即选择符合条件的元组。
7、除：给定关系R（X，Y）和S（Y，Z），其中X，Y，Z是属性组，R中的Y和S中Y可以有不同的属性名，但必须出自相同的域集。
8、连接：也称θ连接运算，是一种二元运算，它的操作是从两个关系的笛卡尔积中选取属性间满足一定条件的元组，以合并成一个大关系。连接运算包括等值连接和不等值连接。连接运算后得到的新表的属性是运算前表中属性相加。即多于原来关系中属性的个数。
9、自然连接：自然连接满足的条件是（1）两关系间有公共域（2）通过公共域的相等值进行连接。
一个低一级范式的关系模式，通过模式分解可以转化为若干个高一级范式的关系模式的集合，这种过程就叫规范化。
数据库设计中有两种方法，面向数据的方法和面向过程的方法。
面向数据的方法是以信息需求为主，兼顾处理需求；面向过程的方法是以处理需求为主，兼顾信息需求。由于数据在系统中稳定性高，数据已成为系统的核心，因此面向数据的设计方法已成为主流。
数据库设计方法和步骤：需求分析、概念设计、逻辑设计、物理设计
通过详细调查现实世界要处理的对象（组织、部门、企业等），充分了解原系统的工作概况，明确用户的各种需求，然后在此基础上确定新系统的功能。
- 信息要求
- 处理要求
- 安全性和完整性要求
方法：
结构化分析法（structured analysis SA方法）：自顶向下、逐层分解。
面向对象的方法
用数据流图表达数据和处理过程的关系
通过数据字典对系统中数据详尽描述，是各类数据属性的清单；
数据字典包括5个部分：
-
数据项：数据最小的单位；
-
数据结构；
-
数据流；
-
数据存储；
-
处理过程
将需求分析阶段得到的用户需求抽象为信息结构即概念模型的过程，它是整个数据库设计的关键。
-
选择局部应用
-
视图设计
三种设计次序：
自顶向下：先从抽象级别较高且普遍性较强的对象开始逐步细化、具体化与特殊化
由底向上：
由内向外。
-
视图集成：将所有的局部视图统一与合并成一个完整的数据模型。
解决局部设计冲突：命名冲突、概念冲突、域冲突、约束冲突
消除冗余
将E—R图转换成关系数据库管理系统（Relational Database Management System RDBMS）
| E-R模型 | 关系 |
|---|---|
| 属性 | 属性 |
| 实体 | 元组 |
| 实体集 | 关系 |
| 联系 | 关系 |
规范化
数据冗余、插入异常、删除异常、修改异常
对数据库内部物理结构作调整并选择合理的存取路径，以提高数据库访问速度及有限利用存储空间。