大家好，又见面了，我是你们的朋友全栈君。

二级公共基础知识总结

下个学期就要开始我的计算机双学位就读了。在此之前，我打算先考几个证来过渡一下，像二级的C、C++、VB、Java、Python、Office都考一下。其中我比较熟悉的只有C和Python，其他的编程语言就要自己突击一下了。3月我报的是C、C++和VB。为此还买了几本书。这里总结一下考点，做一下笔记。之后书就不重要了，可以丢了。再刷一些题目，做一些记录就可以了。开始笔记吧。

第一部分 数据结构和算法

1.1 算法

• 定义：对解决方案的操作步骤的准确而完整的描述。(是数学计算方法和程序间的一个过渡)

• 基本特征：可行性(可以在实际计算工具上执行)；确定性(算法每一步的表述没有歧义)；有穷性(操作步骤有限，在有限时间内完成)；有足够的输入。
  总之，算法是指一组严谨地定义操作步骤的可以在有限的次数中终止的规则，每一个规则都是可行的、明确的。

• 基本要素：
  (1). 对数据对象的运算和操作(由不同计算机系统的指令集规定其基本运算和操作)；
  (2). 控制结构(就是顺序、选择、循环三种)；

• 算法基本设计方法：列举法、归纳法、递推法、递归法、减半递推法、回溯法

• 算法复杂度：体现在运行该算法所需的计算机的时间和空间资源上，越多则算法复杂度越高。
  (1). 时间复杂度：执行算法所需的计算工作量，用算法所执行的基本运算次数来度量(注意: 不是具体的执行时间)。常用大O表示法表示。我们经常用平均复杂度和最坏情况复杂度来分析算法的工作量。
  (2). 空间复杂度：执行这个算法所需的内存空间。包括3个部分。为降低空间复杂度，主要应减少输入数据所占的空间和额外空间。如果额外空间不随问题规模变化，称该算法in place原地工作。

     a. 输入数据所占的存储空间
     b. 程序本身所占的存储空间
     c. 算法执行过程中所需要的额外空间，包括算法执行过程中的工作单元和某种数据结构所需要的附加存储空间
  

1.2 数据结构

• 数据结构：是数据+结构(即有关联的数据元素集合)。数据是需要处理的数据元素(数据的基本单位)的集合，具有共同特征。结构就是关系，是数据集合中各个数据元素之间存在的某种关系。
  结构又可以分为逻辑结构——数据集合中各数据元素之间固有的逻辑关系；存储结构——各数据元素在计算机中的存储关系。此外，数据结构还研究对各种数据结构的运算。
  所以，数据结构=数据+逻辑结构+存储结构+运算。
• 数据元素间的结构根据不同的特性，分为线性结构、树形结构、网状结构(图形结构)、集合。
• 两两数据元素的关系常常用前后件(前驱后继关系)描述。B=(D+R)，D={数据元素集合}，R={前后件关系的集合}。 如：B=D+R，D={早餐，中餐，晚餐}，R={(早餐，午餐)，(午餐，晚餐)}。
• 节点：数据结构的图形表示中引出的概念，根节点——没有前驱的节点，叶子节点——没有后继的节点，内部节点——除了根节点和叶子节点之外的节点的统称。
• 存储结构：包括顺序存储结构和链式存储结构。
• 逻辑结构：包括线性结构和非线性结构。如果数据结构没有数据元素，称其为空的数据结构。

1.3 线性表

• 定义：表中除第一个元素外的每一个元素，有且只有一个前件，除最后一个元素外，有且只有一个后件。
• 结构特征：只有一个根节点，它无前件；有且只有一个终端节点，它无后件；除根节点与终端节点外，其他所有节点有且只有一个前件，有且只有一个后件。节点个数n就是线性表的长度，n=0时称为空表。
• 顺序表：线性表的顺序存储结构，所有元素所占的存储空间是连续的，按逻辑顺序依次存放。此时逻辑结构与存储结构是一致的。顺序表中前后件两个元素在存储空间中紧邻，前件元素一定存储在后件元素的前面。只要确定了首地址，顺序表中任意元素的地址都可以方便地计算出来。
• 线性表的插入运算：在第i个元素之前插入一个新元素，需要把原来的第i个节点至第n个节点依次往后移一个元素位置，把新节点放在第i个节点位置上。其时间耗费在节点的移动上，所需移动节点的次数不仅与表的长度有关，还与插入的位置有关。
• 线性表的删除运算：将表的第i个节点删除，应将第i+1个元素至第n个元素依次向前移一个元素位置，共移动n-i个元素。所需移动节点的次数不仅与表的长度有关，还与删除的节点位置有关。
• 综上所述，线性表的顺序存储结构适用于建立之后其中元素不经常变动的情况，而不适用于经常需要进行插入和删除的线性表。

1.4 栈和队列

1.4.1 栈

• 定义：特殊的线性表，所有的插入和删除操作限定在表的同一端(栈顶top)进行，另一端(栈底bottom)是封闭的，既不允许插入元素，也不运行删除元素。栈中没有元素时称为空栈。
• 设有栈S=(a1, a2, a3, a4)，则a1为栈底元素，a4为栈底元素。按照a1,a2,a3,a4的顺序入栈，a4,a3,a2,a1的顺序出栈。
• 特点：Last In First Out，后进先出。即栈顶元素总是最后被插入的元素，也是最早被删除的元素，栈底元素总是最早被插入的元素，也是最晚被删除的元素。在顺序存储结构中，栈的插入和删除不需要移动表中的其他元素。
• 栈的运算之入栈：在栈顶插入一个新元素。
• 栈的运算之出栈：取出栈顶元素并赋予指定变量。
• 栈底运算之读取栈顶元素：读取栈顶指针所指向的元素并赋予指定变量。

1.4.2 队列

• 定义：特殊的线性表，允许在一段(队尾rear)进行插入，而在另一端(队头front)进行删除的线性表。与生活中的排队现象是一样的。
• 设有队列Q=(q1,q2,q3,q4)，则q1为队头元素，q4为队尾元素。按照q1,q2,q3,q4的顺序进入，也按照这个顺序退出。
• 队列运算之入队：队头指针front指示当前执行退队运算的队头位置(即当前队头元素的前一个位置)，队尾指针rear指向当前执行入队运算的队尾位置，往队列的队尾插入一个元素称为入队，首先队尾指针进1，然后在rear指针指向的位置插入新元素。
• 队列运算之出队：从队列的排头删除一个元素称为退队运算。排头指针front+1，然后删除front指针指向的位置上的元素。队头指针始终指向当前执行退队操作的队头位置。
• 循环队列及其运算：为充分地利用数组的存储空间而把数组的前端和后端连接起来，形成一个环形的表，就是循环队列，是队列的一种顺序存储结构。常用取余运算来实现循环顺序队列的“循环”。为区分队空和队满的情况可以设置标志。

1.5 线性链表(线性表的链式存储)

1.5.1 线性链表的概念及基本运算

• 概念：用一组不连续的存储单元存储线性表中的各个元素，数据元素间的逻辑关系不能依靠数据元素的存储单元之间的物理关系来表达，因此每个元素除了存储自身的信息外，还要存储一个指示其后件的信息。
• 存储节点：线性表链式结构的基本单位成为存储节点，包括数据域(存储数据元素本身的信息)和指针域(存储一个指向后继的指针，即存放下一个数据元素的存储地址)
• 单链表：这种链表中，每一个节点只有一个指针域。是最基本的链表。其中第一个元素没有前驱，可以是一个指向链表中第一个节点的特殊指针，即头指针HEAD，最后一个元素没有后继，其指针域为空，用NULL表示。更加直观的表示是用箭头相链接的节点序列。在单链表中，只能顺时针向链尾方向进行扫描。
• 双向链表：在实际应用中有时还会用到每个存储节点有两个指针域的链表，一个存放前驱的地址，称为左指针(Llink)，一个指针域存放后继的地址，称为右指针(Rlink)。双向链表的第一个元素左指针为空，最后一个元素的右指针为空。由于有两个指针，可以从任一节点出发找到其他节点。
• 链栈：使用链式存储结构表示栈，组织成一个单链表。
• 链队列：使用链式存储结构表示队列，组织成一个单链表。
• 顺序表和链表的优缺点比较：

• 线性链表的基本运算：
  (1). 查找指定元素：必须从队头指针出发，沿着指针域Next逐个节点搜索，直到找到指定元素或链表尾部返回NULL为止。
  (2). 可利用栈(线性链表的存储单元是不连续的，就存在离散的空闲节点，将计算机存储空间中空闲的存储节点利用起来，把其组织成一个带链的栈，就是可利用栈)的插入和删除：线性链表执行删除时，被删除节点回收到可利用栈，即把该空闲节点放到可利用栈栈顶，执行入栈操作；线性链表执行插入运算时，
  需要一个空闲节点，就在可利用栈中取栈顶节点，执行退栈操作。
  (3). 插入运算：在链式存储结构下的线性表中插入一个新元素。由于新节点的存储单元取自可利用栈，只要可利用栈非空，线性链表就总能找到存储新元素的节点，因而不需要规定最大存储空间，不会发生上溢错误。
  (4). 删除运算。

1.5.2 循环链表

• 概念：在单链表第一个节点之前增加一个没有元素的表头节点，HEAD指针指向表头节点，最后一个节点的指针域指向表头节点。在循环链表中，所有节点的指针构成了一个环状链。
• 与单链表的比较：
  (1). 对单链表的访问是一种顺序访问，从其中一个节点出发，只能找到它的后继；在循环链表中，可以通过一个节点访问到表中的所有节点。
  (2). 在单链表中空表和第一个节点的处理必须单独考虑；在循环链表中，表头节点是循环链表所固有的节点，因此即使在表中没有数据元素的情况下，表中也至少有一个节点，从而使空表与非空表的处理统一。

1.6 树与二叉树

1.6.1 树的基本概念

• 树：一种简单的非线性结构，是以分支关系定义的层次结构。在使用图形表示数据结构中元素的前后件关系时通常使用有序箭头，但是树形结构中使用无向箭头也可以，因为前后件关系很明确。

1.6.2 二叉树及其性质

• 二叉树(Binary Tree)定义：是一个有限的节点集合，该集合或为空，或由一个根节点及其左右不相交的左、右二叉子树所构成。与树是相似的，但又有不同。二叉树不是树的特殊情况，二者是不同的概念。

• 二叉树的特点：
  (1). 二叉树可以为空，空的二叉树没有节点，非空二叉树只有一个根节点；
  (2). 每个节点最多只有两棵子树，即二叉树中不存在度大于2的节点，二叉树中的节点可能没有子节点，可能只有一个左子节点或只有一个右子节点；
  (3). 二叉树的子树有左右之分，不能任意颠倒次序。

• 二叉树的基本形态：5种；空，仅有根节点，左右子树均非空，左子树非空右子树为空，左子树为空右子树非空。

• 满二叉树：除最后一层，每一层上的所有节点都有两个子节点的二叉树，一棵平衡的二叉树。
  (1). 其在第i层有2^(i-1)个节点，相当于每一层的节点数都满了；
  (2). 一棵深度为K的满二叉树共有2^k-1个节点;
  (3). 满二叉树中只有度为2和0的节点，没有度为1的节点。所有度为0的叶子节点都在最后同一层。

• 完全二叉树：除最后一层，每一层上的节点数均达到最大，在最后一层上只缺少右边的若干节点。
  (1). 叶子节点只在最后两层出现；
  (2). 对于任一节点，若其右子树的深度为m，则左子树的深度为m或m+1。

• 二叉树的基本性质：
  (1). 二叉树的第K层上面，最多只有2^k-1个节点；
  (2). 深度为K的二叉树，最多有2^k-1个节点(等比数列求和)；
  (3). 对任何一棵二叉树，度为0的节点(叶子节点)总是比度为2的节点多一个；
  (4). 具有n个节点的二叉树，其深度至少为[log₂n]+1；
  (5). 具有n个节点的完全二叉树，其深度为[log₂n]+1。
  (6). 较复杂。

1.6.3 二叉树存储结构及其遍历

• 二叉链表：二叉树常采用链式结构。由于每个元素可以有两个后件，因此每个节点有两个指针：左指针域执行左子节点，右指针域执行右子节点。因此，二叉树的链式存储结构也称为二叉链表(非线性结构，不同于双向链表)。
• 二叉树的遍历：不重复的访问二叉树中的所有节点。一般先访问左子树，在访问右子树，在先左后右的原则下，根据访问根节点的次序不同，二叉树的遍历分为前序遍历(DLR)、中序遍历(LDR)、后序遍历(LRD)三种。
  (1). 前序遍历：先访问根节点——> 前序遍历左子树——> 前序遍历右子树(DLR)
  (2). 中序遍历：先中序遍历左子树——> 访问根节点——> 中序遍历右子树(LDR)
  (3). 后序遍历：先后序遍历左子树——> 后序遍历右子树——> 访问根节点 (LRD)
  

  已知中序遍历序列和前序遍历序列(或后序遍历序列)可以唯一确认一棵二叉树，但是知道前序和后序则无法唯一确定这棵二叉树。

1.7 查找技术

查找是插入和删除等运算的基础，是数据处理的重要内容。

• 顺序查找：最好情况：1次找到；最坏情况：n次比较后找到；平均：n/2次，即O(n)的时间复杂度。特点在于：虽然效率很低，但是在线性表无序(不管使用顺序存储还是链式存储)的时候，或者在采用链式存储结构时，只能用顺序查找。
• 二分查找：条件：使用顺序存储结构；线性表是有序表。对于长度为n的有序线性表，在最坏情况下二分查找只需比较log₂n次。即O(logn)的时间复杂度。
• 哈希查找：时间复杂度O(1)。

1.8 排序技术

排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。

• 交换类排序法(借助数据元素的交换来排序的方法)：冒泡排序: 最坏的情况下，对长度为n的线性表排列需要比较n(n-1)/2次。快速排序则是对冒泡排序的一种本质改进，其平均时间最佳O(nlog₂n) ，最坏O(n²)。如初始序列基本有序，则蜕化为冒泡排序。

• 插入类排序法(每次将一个待排序元素按其大小插入到前面的有序子表中)：简单插入排序：持续不断的清空无序表，插入有序表中，其效率与冒泡排序法基本相同。希尔排序法则有较大改进。

• 选择类排序法(每趟从待排序的序列中选择最小的元素，顺序放在有序子表中的后面，直到全部序列满足排序要求为止)：简单选择排序，最坏的情况下要比较n(n-1)/2次。对于大量数据元素，堆排序则是很有效的。

• 排序方法比较：

  方法	平均时间	最坏情况时间	辅助存储
  冒泡排序	O(n2)	O(n2)	O(1)
  快速排序	O(nlog2n)	O(n2)	O(log2n)
  简单插入排序	O(n2)	O(n2)	O(1)
  简单选择排序	O(n2)	O(n2)	O(1)
  堆排序	O(nlog2n)	O(nlog2n)	O(1)

第二部分 程序设计基础

2.1 程序设计方法与风格

• 程序设计：指设计、编制、调试程序的方法与过程。不等同于编程。程序设计的方法和风格显著影响程序的质量。良好的程序设计风格可以使程序结构清晰，便于维护。
• 程序设计规范：
  (1). 源程序文档化：在源程序中包含一些内部文档，以帮助人们理解和阅读源程序。考虑符号名的命名、程序注释(包括序言性注释和功能性注释)、视觉组织(空行、空格和缩进)。
  (2). 数据说明的方法：词序规范化、变量安排有序化、使用注释。
  (3). 语句结构：简单直接，模块化……
  (4). 输入输出：方式和格式尽量方便用户使用；对所有的输入数据都要进行检验，确保输入数据的合法性；输入数据时，应允许使用自由格式，允许默认值；输入一批数据后，最好使用输入结束标志；给所有的输出加注释，并设计良好的输出报表格式……

2.2 结构化程序设计

• 原则：自顶向下； 逐步求精；模块化；限制使用goto语句。
• 基本结构：顺序结构、选择结构和循环结构。3种基本结构就足以表达各种其他形式的结构。共同特征是严格的只有一个入口和出口。
• 注意事项：使用顺序、选择、循环等有限的控制结构表示程序的控制逻辑；选用的控制结构只允许有一个入口和出口；程序语句组成容易识别的功能模块，每个模块只有一个入口和一个出口；复杂结构应该用基本控制结构进行组合嵌套来实现；语言中没有的控制结构，应采用前后一致的方法模拟；严格控制goto语句的使用。
• 总之，按结构化程序设计出的程序具有明显的优点：程序易于理解、使用和维护；提高呢编程工作的效率，降低了软件开发成本。

2.3 面向对象的程序设计

基本概念：

• 对象(Object)：系统中用于描述客观事物的一个实体，是构成系统的一个基本单位，由一组静态特征(属性)和它可执行的一系列方法(行为)组成。其中的属性即对象包含的信息，一般只能通过执行对象的操作来改变。方法则是对象的动态行为。
  对象的基本特点：标识唯一性；分类性(可以将具有相同属性和操作的对象抽象成类)；多态性(同一个操作可以是不同对象的行为)；封装性(对象内部对外是不可见的)；模块独立性好(完成对象功能所需的元素都被封装在对象内部)。
• 类(Class)：具有共同属性和方法的对象的集合，是关于对象的抽象描述，反映属于该对象类型的所有对象的性质。
• 实例(Instance)：一个具体对象则是其对应类的一个实例。
• 消息(Message)：消息传递是对象间通信的手段，一个对象通过向另一个对象发送对象来请求其服务。一个消息由接受消息的对象名称、消息选择符、零或多个参数组成。消息只告知接受对象需要完成什么操作，而不指示怎样完成操作。
• 继承：直接获得已有的性质和特征，而不必重复定义它们。一个子类可以直接继承父类的全部描述，而且可以定义自己的属性和方法。其中，继承又分成单继承和多继承。
• 多态：同样的消息可以被不同的对象接受而产生不同的行为。即子类对象可以像父类对象那样使用，同样的消息既可以发给父类也可以发给子类对象。
• 优点：与人类习惯的思维方法一致；稳定性好；可重用性好；容易开发大型软件产品；可维护性好。

第三部分 软件工程基础

3.1 软件工程基本概念

3.1.1 软件

• 定义：是由(机器可执行的)程序、数据和(不可执行的)相关文档组成的完整集合。
  (1). 程序：软件开发人员依据用户需求开发的、用某种程序设计语言描述的、能够在计算机中执行的语句序列。
  (2). 数据：使程序能够正常操作信息的数据结构。
  (3). 文档：与程序开发维护使用相关的文件资料。
• 特点：(1). 是一种逻辑实体；(2). 没有明显的制作过程；(3). 在使用期间不存在磨损老化问题，损失方式特殊；(4). 对硬件和环境具有依赖性，给软件的移植带来问题；(5). 软件复杂性高，成本昂贵；(6). 软件开发涉及诸多社会因素。
• 分类：(1). 系统软件：管理计算机资源，提高使用效率，为用户提供各种服务的软件。(2). 支撑软件：介于系统软件和应用软件之间，辅助用户开发软件的工具型软件。 (3). 应用软件：为了应用于特定软件而开发的软件。
• 软件危机：泛指在计算机软件的开发和维护中所遇到的一系列严重问题，几乎所有软件都不同程度存在这些问题(软件开发生产率低；软件质量难以保证；软件开发进度无法控制；软件成本不断提高；软件维护程度低下；软件需求的增长得不到满足)。主要原因在于：软件本身的特点，如复杂度高，规模庞大；人们对软件开发维护有许多错误认识和做法，对软件的特性认识不足。为此，诞生了软件工程的概念。

3.1.2 软件工程

• 软件工程：应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准、工序。重要三要素是方法(技术手段)、工具、过程。
• 软件工程目标和研究内容(软件开发技术和软件工程管理)
• 软件工程的原则：

• 软件工程过程：是使用适当的资源为开发软件进行的一组开发活动，在过程结束时将输入(用户要求)转化为输出(软件产品)。
  基础活动如下：

• 软件生命周期：一个软件从提出、实现、使用、维护和停止使用与废弃的过程称为软件生命周期。分为3个时期和8个阶段。

• 软件开发工具：从单项工具逐步向集成工具发展；软件开发环境：是全面支持软件开发全过程的软件工具的集合。

3.2 结构化分析方法

也称传统方法学，使用结构化方法完成软件开发的各项任务。

3.2.1 需求分析

• 软件需求是用户对目标软件系统在功能、性能和设计约束上的期望。需求分析的任务是发现需求、定义需求的过程，将创建所需的数据模型、功能模型和控制模型。
• 需求分析阶段的工作：
  (1). 需求获取：了解用户情况，发现用户问题和对目标系统的完整、准确和具体的需求。
  (2). 需求分析：整合获得的需求，得出系统的解决方案和目标系统的逻辑模型。
  (3). 编写需求规格说明书：这是需求分析的阶段性成果。
  (4). 需求评审：从一致性、完整性、现实性、有效性复审软件需求规格说明书。

3.2.2 需求分析方法

• 结构化分析方法：面向数据流的结构化分析(SA)；面向数据结构的Jackson系统开发；面向数据结构的结构化数据系统开发方法。面向对象分析方法：面向对象分析是面向对象软件工程方法的第一个环节。
• 结构化分析方法：使用数据流图、数据字典、结构化英语、判定表和判定树等工具来建立一种新的称为结构化规格说明的目标文档。

3.2.3 结构化分析方法的常用工具

• 数据流图：分析员和用户间极好的通讯工具。

• 数据字典：对数据流图中所有元素的定义的集合，是结构化分析的核心，与数据流图共同构成系统的逻辑模型。其中共有4种类型的条目，数据流、数据项、数据存储和加工。
• 判定表：如果一个加工逻辑有多个条件、多个操作并且在不同场合下执行不同的操作，可以使用判定表来描述。一个十字分成四个区域，左上部是基本条件项，列出各种可能的条件；右上部成为条件项，列出各种可能的条件组合；左下部是基本动作项，列出所有的操作；右下部是动作项，列出在对应的条件组合下所选的操作。
• 判定树：可以用判定表表示的加工逻辑都可以用判定树表示。

3.2.4 软件需求规格说明书

这是需求分析阶段的最后成果，是软件开发过程中的重要文档之一，衡量它的标准如下：

3.3 结构化设计方法

在需求分析阶段已经使用数据流图和数据字典等工具建立了系统的逻辑模型，即做什么，接下来解决怎么做的问题。

3.3.1 软件设计概述

• 软件设计基础：基本目标是用抽象概括的方式确定目标系统如何完成预定的任务，确定系统的物理模型，是开发阶段最重要的步骤。

• 软件设计基本原理与原则：
  (1). 模块化，但要避免模块的数目过多或过少；(2). 抽象；(3). 信息隐藏——指出设计和确定模块时应使得一个模块中包含的信息对不需要这些信息的模块来说是不能访问的；(4).模块独立性——每个模块完成一个相对独立的特定子功能，并且和其他模块间的关系很简单。模块的独立性是设计好坏的关键，可以用耦合和内聚两个定性指标来衡量，一般来说，要求模块之间的耦合尽可能弱，即模块尽可能独立，且模块的内聚程度尽可能高。实践表明，内聚更加重要，应把更多精力放到提高模块的内聚程度上。

3.3.2 概要设计(总体设计)

• 基本任务：
  (1). 设计软件系统结构：过程如下：