一、计算机系统

1.1、计算机的发展

ENIAC，世界上第一台电子数字计算机，1946年诞生子美国宾夕法尼亚大学。

EDVAC，第一台存储程序的计算机，冯·诺依曼小组研发，“现代电子计算机之父"

EDVAC三个特点:

1. 用二进制来表示计算机内部的指令和数据;
2. 预先将编好的程序和原始数据存入存储器中，再启动计算机工作。
3. 采用由运算器、存储器、控制器、输入设备和输出设备五大部分组成的体系结构，该结构被称为冯诺依曼结构。

根据物理器件的不同，可以将计算机的发展分为四个阶段:

阶段名称	物理器件
第一阶段（1946—1958）	电子管
第二阶段（1958—1964）	晶体管
第三阶段（1964—1971）	中小规模集成电路
第四阶段（1971—至今）	大规模、超大规模集成电路

1.2、计算机硬件系统

1.2.1、CPU

中央处理器，也称CPU，分为控制器和运算器两部分。它主要负责解译计算机指令和处理计算机软件中的数据，是计算机系统的核心.

计算机系统的性能由CPU品质的高低决定，而CPU的品质主要由主频与字长决定。

CPU的工作过程主要包括提取指令、解码指令、执行指令和修改程序计数器四个阶段在这个过程中，需要用到寄存器暂时存储处理的数据，并用总线将控制器和算术逻辑单元连接起来。

1.2.2、存储器

1. 寄存器
   寄存器通常位于CPU内部，用于保存机器指令的操作数。由于其价格昂贵导致其数量有限，又由于存取速度非常快，使其不可或缺。

2. 高速缓冲存储器
   简称缓存，是存在于内存与CPU之间的一种存储器，容量小但存取速度比内存快得多。它的存在有效地解决了内存与CPU之间速度不匹配的问题。

3. 主存储器
   即我们平时所称的内存，通常分为随机存储器(RAM)和只读存储器(ROM)。

   1. 随机存储器（RAM）
      随机存储器可以随时从一个指定的地址写入或读取信息。通电状态下，数据是完整的;旦断电，存在其中的数据会消失且无法恢复。
   2. 只读存储器（ROM）
      只读存储器中的信息在制造时就被存入其中并永久保存，且这些信息只能被读出，不能被修改。即使在断电情况下，只读存储器中的信息也不会消失。

4. 辅助存储器
   即我们平时所称的外存，常见外存有硬盘、移动硬盘、U盘、光盘、磁盘等。
   CPU不能直接访问存在外存中的程序和数据，需要将其调用到内存中才能运行。外存有存取速度慢、价格低、容量大等特点。

1.2.3、输入输出设备

1. 输入设备
   是指能向计算机输入数据或信息的设备。常见的输入设备有键盘、鼠标、摄像头、扫描仪、手写输入板等。
2. 输出设备
   是指能将计算机数据或信息以某种格式（如图片、字符、声音等）输出给用户的设备。常见的输出设备有打印机、显示器、绘图仪、影像输出系统、语音输出系统、磁记录设备等。

1.2.4、总线

总线由导线组成，是用于计算机内部各个功能部件之间传送信息的公共通信干线。计算机的总线可以分为片内总线、系统总线和通信总线等。其中，系统总线又分为数据总线、控制总线和地址总线三种。

总线	作用
数据总线	用于在CPU与RAM之间来回传送需要处理或需要储存的数据。
地址总线	用来指定在RAM中储存数据的地址
控制总线	将微处理器控制单元的信号传送到周边设备

1.3、信息的表示与存储

1.3.1、存储单位

数据的最小单位是位，用bit表示。
存储容量的基本单位是字节，用Byte或B表示，8个二进制位称为一个字节。
字长是指计算机一次能处理的二进制数的位数，如32位、64位、128位。

1.3.2、二进制与十进制的转换

二进制转十进制:**按权展开**
十进制转二进制:**除二取余**

1.3.3、字符编码

计算机中最常用的字符编码是美国信息交换标准代码，简称ASCII码。通用的是7位码，共有128个字符。
包含0-9数字、26个大写字母、26个小写字母，之间夹杂着一些符号。小写英文字母的码要比大写英文字母的码值大32。
控制运算符<数字<大写字母<小写字母
汉字机内码=汉字国标码+(8080)H

1.4、操作系统

1.4.1、操作系统的发展

阶段名称	阶段特征
手工操作	手工操作就是需要手动来操作计算机工作（没有操作系统)）
批处理系统	计算机能自动地、成批地处理一个或多个用户作业（作业指程序、数据、命令）的系统。
多道程序系统	同时将多个相互独立的程序放到计算机内存中，在管理程序控制下，使它们相互交叉运行的系统。
分时系统	分时系统是一个多用户交互式的操作系统。通常采用时间片轮转策略为用户服务。
个人计算机操作系统	个人计算机操作系统是联机交互的单用户操作系统。

1.4.2、进程管理

1.4.3、存储管理

管理类型	内容及特点
连续存储管理	根据分区的大小是否可以固定，可分为固定分区和可变分区（动态分区）。固定分区管理简单，对硬件要求较低，但容易产生内部碎片。可变分区能有效地避免每个分区对存储空间利用不充分的问题，但容易产生外部碎片。
分页式存储管理	能有效地解决碎片问题，内存利用率较高，内存的分配和回收算法也比较简单;但增加了硬件的成本，同时也降低了处理机的速度。
分段式存储管理	能够有效地解决程序员编程、用户资源共享和信息保护等问题。
段页式存储管理	结合了分页式存储管理和分段式存储管理的优点，提高了内存的利用率并实现了段的共享。
虚拟存储管理	是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。它使得存储系统拥有接近外存的容量和接近内存的访问速度。

1.4.4、文件管理

计算机中的数据通常是以文件的形式存储在磁盘或其他存储介质上，同时计算机要将自身的数据或程序传递给用户，也是以文件的形式来传递的。文件管理主要涉及文件逻辑组织结构、物理组织结构、目录结构的管理。

文件目录是一种数据结构，用来标识系统中的文件及其物理地址。

根据组织结构，文件目录分为单级目录、二级目录、多级层次目录、图状结构目录和无环图结构目录等。

1.4.5、I/O设备管理

"I/O”即“输入和输出”(lnput/Output) 。

I/O设备一般被分为硬件、中断处理程序、设备驱动程序、设备无关的I/O软件和用户程序五层。

二、数据结构与算法

2.1、算法

2.1.1、算法的概念

算法是指解题方案的完整且准确的描述，是一系列解决问题的清晰指令。算法不等于数学上的计算方法，也不等于程序。

常见的算法设计方法有列举法、归纳法、递推法和递归法等。
在算法设计时，不能只考虑算法的效率，还需要考虑其他因素。

2.1.2、算法的特性

性质	解释
可行性	算法中的每一个步骤必须能够实现，且执行的结果能够达到预期的目的。
确定性	算法中的每一个步骤都有它确定的含义，不存在一个步骤有多个含义的情况。不允许有模棱两可的解释，也不允许有多义性。
有穷性	算法必须在有限时间内完成，即算法必须能在执行有限个步骤之后终止。
拥有足够的情报	一个有效的算法应该有足够多的、正确的输入信息或初始化信息，并且至少有一个输出结果。

2.1.3、算法的复杂度

算法的复杂度主要包括时间复杂度和空间复杂度，但两者之间没有直接的联系。

复杂度	意义
时间复杂度	执行算法所需要的计算工作量，即算法语句的执行次数。
空间复杂度	算法在执行过程中所需要的计算机存储空间。包括程序本身所占的存储空间、输入数据所占的存储空间、算法执行过程中所需要的额外空间。如果额外空间量相对于问题规模(即输入数据所占的存储空间)来说是常数，即额外空间量不随问题规模的变化而变化，则称该算法是原地工作的。

• 在顺序存储的线性表中寻找最大项时，平均情况与最坏情况的时间复杂度相同
• 压缩空间会降低空间复杂度

2.2、数据结构

2.2.1、数据结构的概念

数据结构，即带有“结构"的数据元素的集合。一般来说，现实世界中客观存在的一切个体都可以是数据元素。例如，“春、夏、秋、冬”可以作为季节的数据元素。

在数据处理时，通常把数据元素之间的特殊关系称为前后件关系。以季节为例，在考虑一年四季的时间顺序关系时，“春”就是“夏”的前件，“夏”是“春”的后件。

2.2.2、数据结构的两种表示方法

二元组表示:
B=(D,R)
D={春，夏，秋，冬}
R={(春,夏)，(夏,秋)，(秋,冬)}

• 夏是春的前件，秋是夏的前件。。。

图形表示:

二元组表示：

B=(D,R)
D={司令员，军长，师长，旅长}
R={(司令员,军长)，(军长,师长)，(师长,旅长)}

2.2.3、数据结构的分类

1. 逻辑结构
   数据的逻辑结构是指反映数据元素之间逻辑关系（前后件关系）的数据结构。数据的逻辑结构分为线性结构和非线性结构。

2. 存储结构
   数据的逻辑结构在计算机存储空间中的存放形式被称为数据的存储结构，也可以称为数据的物理结构。
   常见的存储结构有顺序存储、链式存储、索引存储和散列存储等。

2.3、线性表

2.3.1、线性表的概念

线性表是一种逻辑结构，它是最简单、最常用的一种数据结构.在线性表中，数据元素之间是一对一的关系。

线性表是由n(n ≥0)个相同数据类型的数据元素组成的一个有限序列，将其表示为(a,a2,a3,…,an )

其中a1,a2,a3…,an表示n个数据元素，a1为表头元素,也叫根节点，an为表尾元素，也叫终端节点。

2.3.2、线性表的特性

非空线性表的结构特征:

1. 有且只有一个根结点a1，它无前件。
2. 有且只有一个终端结点an，它无后件。
3. 线性表的结点个数就是该线性表的长度。

当n=0时，线性表为空表。

2.3.3、线性表的顺序存储——顺序表

• 将线性表中的数据元素存储在一组地址连续的存储单元里，使得逻辑上相邻的两个元素在物理位置上也相邻，称为线性表的顺序存储，又称为顺序表。

• 在顺序表中可以进行插入、删除、修改和查询数据元素等操作，常用的操作是插入和删除。

顺序表的插入操作

• 在顺序表中插入元素时，首先需找到要插入元素的位置。如果该位置上没有元素，则直接插入新元素;若该位置上有元素，需要将该位置上的元素及其后面的元素向后移动，空出需要插入元素的位置，最后将新元素插入到指定的位置上。

• 当线性表的存储空间已满时，不能再继续插入新元素。若继续插入，则会产生"上溢”错误。

顺序表的删除操作

• 在线性中删除已有的元素，然后将删除元素之后的所有元素依次向前移动相应个位置，并减少线性表的结点数。

• 若线性表为空时，不能再进行数据元素的删除。若继续删除，则会产生“下溢′错误。

2.3.4、线性表的链式存储——线性链表

• 线性表的链式存储结构称为线性链表，用一组地址任意的存储单元存放线性表中的各个数据元素，不要求逻辑上相邻的两个元素在物理位置也相邻。
• 链式存储结构中的结点通常由两部分组成，用于存放数据的部分称为数据域，用于存放指针的部分称为指针域。
• 线性链表又分为了单向链表，双向链表，循环链表。

单向链表

单向链表是链表的一种，它的指向是单向的，对链表的访问是从头部开始顺序读取元素，其每个结点都有指针成员变量指向列表中的下一个结点。单向链表的head指针指向第一个成为表头结点，而终止于最后一个指向NULL的指针。

双向链表

双向链表有两个指针域，一个指向前件结点，一个指向后件结点。指向前件结点的指针称为左指针( Llink )，指向后件结点的指针称为右指针（Rlink ) 。

• 双向但不循环

循环链表

循环链表是将表中最后一个结点的指针域指向头结点，使整个链表形成一个环。

在循环链表中，只要知道任一结点的位置，都可以从该结点位置出发，访问表中所有的结点。

循环链表插入和删除元素比单向链表更加简单。表头结点是循环链表中固有的结点，即使表中没有数据，表中至少都还有一个表头结点，这样就实现了空表和非空表运算的统

线性表的操作

线性链表常用的基本运算操作有插入、删除、查找。

例如，在a2和a3之间插入a6元素:

• 查找操作

如果要在线性链表中查找指定元素，就需要从队头指针出发，逐个向后搜索，直到找到指定元素或链表尾部为止。当搜索到指定元素时，需要返回该元素的所在位置；若在链表中没有找到指定元素，则返回空。

三、栈和队列

3.1、栈

3.1.1、栈的概念

栈是一种操作受限的线性表，限定它只能在表的同—端进行插入和删除操作。允许插入和删除元素的一端称为栈顶，不允许插入和删除元素的一端称为栈底。

由于最先插入的元素总是最后被删除，最后插入的元素总是最先被删除，因此栈也被称为**"先进后出"或"后进先出"的线性表，也被称为顺序栈**。

通常用top指向栈顶元素，反应栈中元素变化情况﹔bottom表示栈底，在运算当中维持不变。

运算	内容
入栈运算	从栈顶位置插入新元素的操作称为入栈。
出栈运算	从栈顶位置取出栈顶元素的操作称为出栈。
读栈顶元素	当栈不为空时，将栈顶元素赋给一个指定变量的操作称为读栈顶元素。

入栈运算

插入一个新元素，栈顶指针top加1，指向新插入元素的位置，因此，栈顶指针top的动态变化能反映栈中元素的变化情况。当栈满时，不能继续做入栈操作，若继续入栈，就会产生"上溢"错误。

出栈运算

当栈不为空时，从栈顶位置取出栈顶元素的操作称为"出栈”。取出一个元素，栈顶指针top减1，指向新的栈顶元素所在的位置。当栈空时，不能继续做出栈操作，若继续出栈，就会产生”下溢"错误。

读栈顶元素

当栈不为空时，将栈顶元素赋给一个指定变量的操作称为"读栈顶元素"。这个操作不删除栈顶元素，因此栈顶指针top不会发生任何变化。

当题目中出现栈的存储空间为s (1:n)，初始状态为top=0, top=-1，或top=n+1，初始状态都按空栈处理。

• 出现top=n+1时，说明栈顶部是1底部是n

3.1.2、带链的栈

栈是一种线性结构，既可以采用顺序存储也可以采用链式存储。采用链式存储的栈称为链栈，也可以称为带链的栈。链栈不要求逻辑上相邻的两个元素在物理位置上也相邻。

在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。可利用栈总是处于动态变化之中，其栈顶指针和栈底指针会随栈的操作而动态变化。

3.2、队列

3.2.1、队列的概念

队列也是—种操作受限的线性表，限定它只能在一端进行插入操作，在另一端进行删除操作。允许删除元素的一端称为队头，允许插入元素的一端称为队尾。由于先插入的元素总是先删除，后插入的元素总是后删除。因此，队列也被称为"先进先出"或"后进后出”的线性表。

3.2.2、队列的基本运算

入队和退队操作是队列的基本运算操作。在队列的基本运算中，通常用front表示队头指针（排头指针），用rear表示队尾指针。

当队列不满时，在队尾插入新元素的操作称为入队操作。当队列不为空时，在队头删除元素的操作称为退队操作。退队操作会引起队头指针front的变化，入队操作会引起队尾指针rear的变化，如下图所示。

3.2.3、循环队列

在实际应用中，队列的顺序存储结构一般采用的是循环队列的形式。

循环队列是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。

在循环队列中，用队尾指针rear指向队尾元素，用队头指针front指向队头元素的前一个位置，因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。

循环队列中计算元素个数

1. 第一种情况︰ rear > front

   • 元素个数 = rear - front

2. 第二种情况: rear < front

   • 元素个数= ( rear - front ) +循环队列长度

3. 第三种情况: rear = front

   • 循环队列为空（ 0个）或为满（Q个）

3.2.4、带链的队列

队列也是一种线性结构，也可以采用链式存储结构。

与顺序队列相比，链式存储的队列在插入和删除元素时，操作更加简单。且链式队列也是动态分配的，易于扩充，但需要为队列中的逻辑关系增加额外的存储空间。

四、树和二叉树

4.1、树

4.1.1、数的概念

树是一种典型的非线性结构，它具有明显的层次性，与自然界中的树极为相似，因此而得名。

4.1.2、树的概念

1. 父结点:即结点的前件。除根结点外每个结点只有一个父结点。
2. 子结点:即结点的后件。
3. 根结点:没有父结点的结点，一棵树只有一个根结点。
4. 叶子结点:没有子结点的结点。
5. 度:一个结点的后件个数称为该结点的度。
6. 树的度:一棵树中所有结点中最大的度数称为树的度。
7. 结点的深度:从根结点到该结点的累计层数。
8. 树的深度:树的总层数即为树的深度。
9. 子树:以某结点的一个子结点为根构成的树成为该结点的一棵子树。

4.1.3、数的性质

1. 树的总结点数等于每层结点数之和。即
   Sn=N1+N2+N3+ …+Nk(Nk表示第K层的节点数)

2. 树的总结点数等于所有不同度数的结点数之和。即
   Sn=N0+N1+N2+ …+Nm (Nm表示度为m的节点数)

3. 树的总结点数等于所有结点度数加1。即
   S= N0x0+N1×1+N2×2+ …+Nmxm +1 (Nm表示度为m的节点数)

N0+N1+N2+ …+Nm = N0x0+N1×1+N2×2+ …+Nmxm +1

4.2、二叉树

4.2.1、二叉树的概念

二叉树是一种特殊的树结构。二叉树具有以下两个特点:

1. 非空二叉树只有一个根结点;
2. 每个结点至多有两棵子树（即结点的度≤2），分别称为该结点的左子树和右子树。

二叉树的五种形态：

4.2.2、满二叉树

满二叉树是二叉树的一种特殊形态，是指除最后一层外，其余每一层上的结点都有两个子结点的二叉树，即该二叉树中每一层都含有最多的结点。如下图所示。

4.2.3、完全二叉树

完全二叉树也是二叉树的一种特殊形态，是指除最后一层外，其余每一层上的结点数均达到最大值，且在最后一层上只会缺少右边的若干结点，这种二叉树称为完全二叉树。

满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

4.2.4、二叉树的性质

1. 非空二叉树的第K层上最多有2的k-1次方个结点。
2. 深度为K的二叉树，最多有2的k次方-1个结点。
3. 具有n个结点的二叉树，深度最少为[log2n]+1，其中[log2n]表示取log2n的整数部分。
4. 非空二叉树中，叶子结点数（度为0的结点）等于度为2的结点数加1
   即N0=N2+1。

4.2.5、二叉树的储存结构

• 一般二叉树采用链式存储

• 满二叉树和完全二叉树可以采用顺序存

• 顺序存储对于一般二叉树不适用

4.2.6、二叉树的遍历

二叉树的遍历是指按某条搜索路径访问树中的每个结点，使得每个结点均被访问一次,而且仅被访问一次。

常见的遍历方法有前序遍历（ DLR）、中序遍历（LDR）和后序遍历（LRD)三种。

1. 前序遍历

   • 在遍历二叉树时，先访问根结点，再遍历左子树，最后遍历右子树。
   • 在遍历左子树和右子树时，也是先访问该子树的根结点，再遍历其左子树，最后遍历其右子树。即“根左右”。

2. 中序遍历

   • 在遍历二叉树时，先遍历左子树，再访问根结点，最后遍历右子树。
   • 在遍历左子树和右子树时，也是先遍历其左子树，再访问该子树的根结点，最后遍历其右子树。即“左根右”。

3. 后序遍历

   • 在遍历二叉树时，先遍历左子树，再遍历右子树，最后访问根结点。
   • 在遍历左子树和右子树时，也是先遍历其左子树，再遍历其右子树，最后访问该子树的根结点。即“左右根”。

前序遍历序列和中序遍历序列可以唯一确定一棵二叉树
后序遍历序列和中序遍历序列可以唯一确定一棵二叉树

前中一样后颠倒，中后一样前颠倒。

五、程序设计基础

5.1、程序设计方法与风格

5.1.1、程序设计方法

程序设计是给出解决特定问题程序的过程，是软件构造活动中的重要组成部分。

Wirth公式:程序=算法+数据结构

常用的程序设计方法有结构化程序设计方法和面向对象的程序设计方法。

5.1.2、程序设计的风格

程序设计风格指一个人编制程序时所表现出来的特点、习惯和逻辑思路等。

为了程序的测试和维护，要求编写的程序不仅需要程序员自己能看懂，而且也要让别人能看懂。

除非对效率有特殊要求，程序编写要做到清晰第一，效率第二。

四个重点：

要求	意义
源程序文档化	符号名的命名应该有实际的含义;程序中要有注释，要有适当的空格、空行和缉进等,便于阅读和理解
数据说明规范化	应规范数据说明的顺序，使数据的属性易于查找;一个语句说明多个变量时，各弯量应该按字母顺序排列
语句结构简明化	语句结构应该简单直接，不能为了追求效率而使语句复杂化;为了便于阅读和理解，理论上应该一行一个语句;不同层次的语句采用缩进形式，使程序的逻辑结构和功能特征更加清晰;要避免复杂的判定条件，避免多重的循环嵌套
输入和输出合理化	系统能否被用户接受，往往取决于输入和输出的风格，所以输入、输出的方式和格式应尽可能方便用户的使用

5.2、结构化程序设计

5.2.1、结构化程序设计的四个原则

原则	解释
自顶向下	自顶向下是指在程序设计时，应遵循先总体后细节，先全局后局部的原则。不要一开始就去追求众多的细节，应该先从总体开始设计，再逐步具体化各个细节。
逐步求精	对于一些比较复杂的问题，需要设计一些子目标作为过渡，将这个复杂的问题逐步细化。
模块化	模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，我们将这些小目标称为模块。
限制使用goto语句	随意使用goto语句很可能导致程序结构混乱，所以应尽量避免使用goto语句

5.2.2、结构化程序设计的三大基本结构

结构化程序设计的三大基本结构为:顺序结构、选择结构、循环结构。

5.3、面向对象的程序设计（主流）

5.3.1、面向对象的程序设计的五大优点

面向对象方法的实质就是主张从客观世界固有的事物出发来构造系统，提倡用人类在现实生活中常用的思维方法来认识、理解和描述客观事物，强调最终建立的系统能够映射问题域。目前已成为主流的程序设计方法。

面向对象的程序设计的优点有:

1. 与人类习惯的思维方法一致
2. 稳定性好
3. 可重用性好
4. 易于开发大型软件产品
5. 可维护性好

5.3.2、面向对象的程序设计的五大基本要素

关于面向对象的程序设计，对其概念有许多不同的看法和定义，但是都涵盖了对象、类和实例、消息、继承、多态性五个基本要素。

对象

对象是面向对象方法中最基本的概念，对象可以用来表示客观世界中的任何实体。一个对象通常可由对象名、属性和操作三部分组成。

特点	意义
标识唯一性	每个对象都有自身唯一的标识，通过这种标识，可找到相应的对象
分类性	指可以将具有相同属性和操作的对象抽象成类
多态性	指同一个操作可以是不同对象的行为
封装性	指从外面只能看到对象的外部特性，对象的内部对外是不可见的
模块独立性好	由于完成对象功能所需的元素都被封装在对象内部，所以模块独立性好

类和实例

具有共同属性、共同方法的对象的集合即为类。类是关于对象的抽象描述，描述了属于该对象类型的所有对象的性质。对象则是类的具体化，是类的实例。

消息

消息传递是对象间通信的手段，一个对象通过发送消息向另外一个对象请求服务。

继承

继承是类之间共享属性和操作的机制，能够直接获得已有的性质和特征，不必重复地定义。即在已有的类（父类）基础上，定义新的类（子类），子类在继承了父类所有的特性后，还可以定义自己的特性。

继承分为单继承和多重继承，即一个子类可以有一个或多个父类。

继承具有传递性，如果类A继承类B，类B继承类C，那么类A继承类C。

多态性

对象根据所接收的消息做出动作，同样的消息被不同的对象接收时可能会导致完全不同的行动，该现象称为多态性。

六、软件工程基础

6.1、软件工程及基本概念

6.1.1、软件

软件的定义

计算机软件是与计算机系统的操作有关的程序、规程、规则及任何与之有关的文档和数据。

它由两部分组成:

1. 机器可执行的——程序及有关数据;
2. 机器不可执行的——与软件开发、运行、维护、使用等有关的文档.

软件的特点

1. 软件是一种逻辑实体，具有抽象性。
2. 软件的生产与硬件不同，它没有明显的制作过程
3. 软件在运行、使用期间不存在磨损、老化问题。
4. 软件的开发、运行对计算机系统具有依赖性。
5. 软件复杂性高，成本昂贵。
6. 软件开发涉及诸多的社会因素。

6.1.2、软件危机

软件危机是指落后的软件生产方式无法满足迅速增长的计算机软件需求，从而导致在开发与维护过程中出现一系列严重问题的现象。

软件危机主要表现在以下几个方面:

1. 开发过程中经常遇到各种问题，导致软件开发进度难以预测。
2. 软件开发成本难以控制且不断提高。
3. 软件需求的增长得不到满足。
4. 软件产品质量难以保证。
5. 软件产品难以维护。
6. 软件开发生产率的提高赶不上硬件的发展和应用需求的增长等。

6.1.3、软件工程

软件工程包括3个要素:方法、工具和过程。

• 方法是完成软件工程项目的技术手段。
• 工具用来支持软件开发、管理和文档生成。
• 过程用来支持软件开发的各个环节控制、管理。

6.1.4、软件过程

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

软件过程通常包含以下4个基本活动:

1. 软件规格说明:规定软件的功能和运行时的限制。
2. 软件开发或软件设计与实现:开发出满足规则说明的软件。
3. 软件确认:确认软件能够满足客户提出的要求。
4. 软件演进:为满足客户变更要求，在使用的过程中，软件必须不断演进

6.1.5、软件的生命周期

软件的生命周期是指软件产品从提出、实现、使用维护到停止使用退役的过程。

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

6.2、需求分析

需求分析的目标是让软件系统确定要“做什么”，它是软件生命周期中的一个重要环节，目的是了解用户对软件在功能、性能和设计等方面的期望。

6.2.1、需求分析阶段的主要工作

阶段名称	主要工作内容
需求获取	确定对目标系统的各方面的需求
需求分析	对需求进行分析，得出解决方案和逻辑模型
编写需求规格说明书	需求规格说明书应重点描述软件的目标，内容应包含软件的功能需求、外部接口、属性及约束条件等。需求规格说明书为用户与开发人员之间的交流提供了方便，它是软件开发工作的基础和依据，也是软件验收的标准。它是需求分析的阶段成果
需求评审	对需求分析阶段的工作进行评审，验证需求文档的一致性、可行性、完整性和有效性

6.2.2、需求分析方法

需求分析的方法主要有结构化分析方法和面向对象的分析方法。

6.2.3、结构化分析法概念

结构化分析方法是常用的需求分析方法，它着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。

6.2.4、结构化分析法的工具

结构化分析方法常用的工具包括数据字典（DD）、数据流图（DFD）、判定树和判定表。其中最为常用的是数据字典和数据流图。数据字典是结构化分析方法的核心。

6.3、软件设计

经过需求分析，软件系统确定了要“做什么”的目标，进而进入软件设计，来解决和确定“怎样做”的问题。软件设计可以认为是把软件需求转换为软件表示的过程。

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

6.3.1、软件设计的基本原理

基本原理	概念
抽象	抽象是人类认识复杂问题时使用的有效思维工具，它的原理是把事物的共同特性提取出来并勿略们的细节和差异
模块化	把一个待开发的软件分解成若干个小的、简单的部分，模块化是将软件系统自顶向下、逐步划分成若干模块的过程。
信息隐藏	信息隐蔽是指一个模块内包含的信息（过程或数据），对于不需要这些信息的其他模块来说是不能访问的。
模块的独立性	模块的独立性是指每个模块仅完成一个相对独立的特定子功能，并且与其他模块之间的关系尽量简单。内聚性和耦合性是度量模块独立程度的两个标准。内聚性是对一个模块内部各个元素之间彼此结合的紧密程度的度量。耦合性是对模块间互相连接的紧密程度的度量。一个好的软件，应该尽量做到高内聚、低耦合。

6.3.2、概要设计

概要设计，又称为结构设计，将软件需求转化为软件体系结构，确定系统接口、全局数据结构和数据库模式。

概要设计的基本任务为:

1. 设计软件系统结构；
2. 数据结构及数据库设计;
3. 编写概要设计文档;
4. 概要设计文档评审。

概要设计文档包含:

1. 概要设计说明书;
2. 数据库设计说明书;
3. 集成测试计划。

6.3.3、概要设计的工具

在概要设计阶段，常用的软件结构设计工具是结构图，也可以称为程序结构图或系统结构图。它是用来描述软件系统的层次和分块结构关系，反映整个系统的功能实现以及模块与模块之间的联系和通信的。

结构图的几个概念:
上级模块:调用其他模块的模块。该图中，“某系统”是“功能2”的上级模块。

从属模块:被其他模块调用的模块。该图中，“功能2”是“某系统”的从属模块。

扇入数:调用一个给定模块的模块个数，即调用上级模块的个数。该图中“功能1.2.1”模块分别调用了“功能1.1”和“功能1.2”模块，所以扇入数为2。

扇出数:一个模块直接调用的其他模块数，即调用下级模块的个数。该图中，“某系统”模块分别调用了“功能1”、“功能2”和“功能3”模块，所以扇数为3。

深度:表示控制的层数。该系统结构图共有四层，所以深度为4。

宽度:整体控制跨度（最大模块数的层）的表示。该系统结构图4层的跨度分别为1、3、4、2，故该系统结构图的宽度为4。

原子模块:树中位于叶子结点的模块。该图中，“功能2”“功能3.1”“功能3.2”“功能1.2.1”“功能1.2.2”均为原子模块。

6.3.4、详细设计

详细设计，又称为过程设计，是为每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。

6.3.5、详细设计的工具

详细设计常用的工具有:

• 图形工具:程序流程图、N-S图、PAD图、HIPO图

• 表格工具:判定表

• 语言工具:PDL（伪码)

6.4、软件测试

软件测试的目的是为了发现程序中的错误，提高用户体验。

一个好的测试用例是指很可能找到迄今为止尚未发现的错误的用例;
一个成功的测试是发现了至今尚未发现的错误的测试。

6.4.1、软件测试的准则

软件测试的准则:

1. 所有测试都应追溯到需求。
2. 严格执行测试计划，排除测试的随意性。
3. 充分注意测试中的群集现象。
4. 程序员应避免检查自己编写的程序。
5. 穷举测试是不可能的。
6. 妥善保存测试计划、测试用例、出错统计和最终分析报告，为维护提供方便。

6.4.2、软件测试的方法

从是否需要执行被测软件的角度，可划分为静态测试和动态测试两种方法。

方法	解释
静态测试	利用人的逻辑思维优势去发现软件的逻辑设计和编码错误，并不实际运行软件
动态测试	基于计算机的测试，是为了发现错误而执行程序的过程。

从功能的角度，可划分为黑盒测试和白盒测试方法。
白盒测试也称为结构测试或逻辑驱动测试，黑盒测试也称为功能测试或数据驱动测试。

功能	解释
黑盒测试	它依据程序的需求和功能规格说明，检查程序的功能是否符合它的功能说明。不考虑内部结构。黑盒测试的测试方法主要有等价类划分法、边界值分析法、错误推测法等。
白盒测试	它把测试对象看作是可见的盒子，依据程序的内部逻辑，对程序所有的逻辑路径进行测试。白盒测试的测试方法主要有逻辑覆盖、基本路径测试等。

• 白盒的方法简称白逻基
• 黑盒的方法简称等边错

6.4.3、软件测试的步骤

6.5、程序调试

程序调试的目的是诊断和改正程序中的错误。

在对程序进行了成功的测试之后，将进入程序的调试（通常称debug，即排错)。它与软件测试不同，软件测试是尽可能多地发现软件中的错误。先要发现软件的错误，然后借助于一定的调试工具去执行找出软件错误的位置并改正错误。软件测试贯穿整个软件生命周期，调试主要在开发阶段。

6.5.1、程序调试的步骤

程序调试的基本步骤:

1. 错误定位，确定错误的位置，找出错误的内在原因。
2. 修改设计和代码，用以排除错误。
3. 需要进行回归测试，防止引进新的错误。

6.5.2、程序调试的方法

程序调试的方法有:

1. 强行排错法:传统方法，使用较多但效率较低。
2. 回溯法:比较适用于规模较小的程序排错。
3. 原因排错法:通过演绎、归纳和二分法来实现。

七、数据库设计基础

7.1、数据库系统的基本概念

7.1.1、三个基本概念

1. 数据库（DB）
   长期存储在计算机内的、有组织的、可共享的数据集合。
   两大特点: 集成、共享。
2. 数据库系统（DBS）
   是以数据库为核心运行的实体。包含数据库、数据库管理系统、数据库管理员、硬件平台、软件平台5个部分。
3. 数据库管理系统（DBMS）
   是数据库的管理工具，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等。

关系:数据库系统（DBS）包含数据库（DB）和数据库管理系统(DBMS),而数据库管理系统（DBMS）是数据库系统的核心。

7.1.2、数据管理发展的三个阶段

7.1.3、数据库管理的特点

特点	解释
数据的集成性	数据库系统实现了整体数据的结构化。
数据的高共享性和低冗余性	数据的集成性使得数据可以被多个应用所共享，数据的共享又极大地减少了数据的冗余性。
数据独立性	数据的独立性是指数据与程序之间的互不依赖性，一般分为物理独立性和逻辑独立性。
数据统一管理与控制	数据的完整性检查、数据的安全性保护和并发控制是统一管理数据的三个手段。数据的完整性检查用以确保数据的正确性;数据的安全性保护用以防止非法访问;并发控制用以控制多个应用的并发访问所产生的相互干扰，以保证其正确性。

7.1.4、数据库系统的体系结构

数据库系统的体系结构主要有三级模式和两级映射。

三级模式:

1. 外模式(也称为子模式或用户模式，用户的数据视图)
2. 概念模式(是全局数据逻辑结构的描述)
3. 内模式(又称物理模式，是数据物理结构和存储方式的描述)

两级映射:

1. 外模式到概念模式的映射
2. 概念模式到内模式的映射

一个数据库只有一个概念模式和一个内模式，但可以有多个外模式。两级映射的提出，极大地提高了数据库的逻辑独立性和物理独立性。

7.2、数据模型

7.2.1、数据模型的概念

数据模型是数据特征的抽象，从抽象层次上描述了系统的静态特征、动态行为和约束条件,为数据库系统的信息表示与操作提供一个抽象的框架。

数据模型的三要素是数据结构、数据操作和数据约束。

7.2.2、数据模型的类型

根据不同的应用层次，将数据模型分为概念数据模型（简称为概念模型)、逻辑数据模型（简称为数据模型）和物理数据模型（简称为物理模型）三种类型。

E-R模型

E-R模型是被广泛使用的一种概念数据模型，也称实体联系模型，是将现实世界的要求转化为实体、联系、属性等基本概念，以及它们之间的两种基本联系，并可以用E-R图直观地表示出来。

E-R模型三大基本概念:

1. 实体：指客观存在并且可以相互区别的事物，是概念世界中的基本单位。
2. 联系︰指实体之间的对应关系，反映现实世界事物之间的相互关联。
3. 属性：描述实体的特性，一个实体一般有多个属性。

实体间联系的个数可以是单个也可以是多个，一般将这种联系分为三种类型，分别是一对一（1:1）联系、一对多（1:m）联系和多对多（m:n）联系。

联系模型	案例
一对一（1:1）	如学校和校长的的联系，一个学校与一个校长——对应。
如学校和校长的的联系，一个学校与一个校长一一对应.
一对多（1:m）	如宿舍房间与学生的联系，一个宿舍房间有多个学生，一个学生只能属于某个宿舍房间
多对多（m:n）	如教师和学生的联系，一个教师可以教多个学生，一个学生又可以受教于多个老师。

E-R模型可以用图的形式展示，这种图被称为E-R图，也可称为实体-联系

层次模型

层次模型是逻辑数据模型的一种，是用树形结构来表示实体间联系的模型，这种模型在现实世界中很常见，例如家族结构、职位结构等。它们都是自顶向下，层次分明的

网状模型

网状模型是指用网络结构表示实体类型及其实体之间联系的模型，它是层次模型的拓展，各个从属级之间呈交叉的关系。允许一个结点可以有多个父结点，也允许一个或多个结点没有父结点。

关系模型（重点）

关系模型是最常用的数据模型之一，它使用一张二维表来表示，简称表。关系模型涉及的名词如下表所示

名词	含义
关系	一个关系对应一个二维表，二维表名就是关系名。
属性	二维表中的一列称为属性。
值域	属性值的取值范围。
元组	二维表中的一行称为一个元组。
键	二维表中能唯一标识元组的最小属性集，也称为码。
候选键	二维表中可能有若干个键，即为该表的候选键。
主键	在一个二维表的若干候选键中指定一个作为主键。
外键	表1中的某个属性集是表2的键，则这个属性集是表1的外键。

二维表一般满足下面7个性质:

1. 元组个数有限性:二维表中元组个数是有限的;
2. 元组的唯一性:二维表中元组均不相同;
3. 元组的次序无关性:元组的次序可以任意调换;
4. 元组分量的原子性:元组的分量是不可分割的基本数据项;
5. 属性名唯一性:二维表中属性名各不相同;
6. 属性的次序无关性:属性与次序无关，可以任意交换;
7. 分量值域的同一性:属性的分量具有与该属性相同的值域。

关系模型的完整性约束包括实体完整性约束、参照完整性约束和用户定义的完整性约束。

1. 实体完整性约束:数据库完整性的最基本要求，它要求关系中主键的属性值不能为空;
2. 参照完整性约束:关系之间相关联的基本约束，它要求关系不能引用不存在的元组;
3. 用户定义的完整性约束:由用户设置具体数据环境和应用环境的约束，它反映了具体应用数据的语义要求。

7.3、关系代数

7.3.1、基本预算符

关系数据库系统的特点之一是它建立在数学理论的基础之上，而最为著名的理论是关系代数。在关系代数中，最常使用的运算符有两类:集合运算符和专门的关系运算符。

并运算

关系R和S通过并运算得到的结果是由属于R或S的元组构成的集合，记为RUS。

交运算

关系R和S通过交运算得到的结果是由属于R且又属于S的元组构成的集合，记为R∩S。

差运算

关系R和S通过差运算得到的结果是由属于R但不属于S的元组构成的集合，记为R-S。

笛卡尔积运算

r元关系R和s元关系S通过笛卡尔积运算得到结果T,T的每个元组的前r个分量来自R的一个元组后s个分量来自S的一个元组。记为RxS，有rxs个元组。

选择运算

选择运算是从关系中找出满足给定条件的所有元组，公式为σF®={t(t∈R且F (t)为真}。例如需要从关系R中选择出性别为“男”的学生，则公式表示为σ性别=’男‘(R），选择运算结束后得出关系S。

得到的是元组

投影运算

投影运算是指从关系中挑选若干个属性组成新的关系，公式表示为ΠA®={t[A]t∈R}(A为R中的属性列）。例如对关系R中的“考试成绩”属性进行投影，得出关系S。

得到的是列

连接运算 -自然连接

自然连接是要求两个关系中进行比较的是相同的属性，将属性值相同的元组进行连接，并且在结果中去掉重复的属性列。

连接运算 -等值连接

自然连接是两个关系中没有相同的属性，但是两个属性间有相同的值,将值相同的元组进行连接

除运算

除运算可以近似地看作笛卡尔积运算的逆运算，记为R÷S=T，其中关系R包含关系S中的所有属性且含有关系S中不曾出现的属性。

7.4、数据库设计与管理

7.4.1、数据库设计4个阶段

数据库设计一般采用生命周期法，分为需求分析、概念设计、逻辑设计和物理设计四个阶段。

7.4.2、转换规则（逻辑设计阶段）

逻辑设计阶段的主要任务是将E-R模型转换成关系模型。

E-R模型	关系模型
实体	元组
属性	属性
联系	关系
实体集	关系

7.4.3、规范化理论（逻辑设计阶段）

设计关系数据库时，遵从不同的规范要求，设计出合理的关系型数据库，这些不同的规范要求被称为不同的范式。

规范化是为了克服逻辑结构中的插入异常，删除异常，数据冗余等问题。

目前关系数据库有六种范式:

1. 第一范式（ 1NF)
2. 第二范式(2NF)
3. 第三范式( 3NF)
4. 巴斯-科德范式(BCNF)
5. 第四范式（4NF)
6. 第五范式（5NF，又称完美范式)

第一范式

第一范式（1NF） :数据库表中的每一列的属性都不可再分

第二范式

第二范式（2NF):是在第一范式的基础上建立起来的，即满足第二范式必须先满足第一范式。
第二范式要求实体的属性完全依赖于主键。所谓完全依赖是指不能存在仅依赖主键一部分的属性，如果存在，那么这个属性和主关键字的这一部分应该分离出来形成一个新的实体。

第三范式

第三范式（3NF)︰满足第二范式，且消除非主属性对主键的传递依赖
所谓传递依赖,例如在某关系模式中，主键→属性A，属性A→属性B，那么可以称属性B是对主键的传递依赖。

带链的考题

现在状态	现在个数
现在相等	0或1
现在相等且初始相等	1
现在不相等	无法判断

各种排列方式长度的计算

快速排序会产生新的逆序

表中查元素次数

• 一半在表中，一半不在表中
  • 在表中：第1个1次，第2个2次，第3个3次，第n个n次，一共需要找（1+2+3+4+…+n）次，才可以找到n个节点，
    • 所以，平均次数就是（1+2+3+4+…+n）/n次
  • 不在表中：每次都是n次。
    • 结果：1/2*(1+n)/2 +1/2*n = (1+n)/4 + 2n/4 约等于 3n/4

堆的排放

上面的数据一定比下面一层的大

子程序调用

支持子程序调用的数据结构是栈

程序流程图与数据流程图中的箭头

程序流程图中的箭头表示 控制流

数据流程图中的箭头表示 数据流