---

此文章已经同步更新到个人博客上，喜欢有侧边栏目录的同学，可以点击下面的链接跳转到个人博客上读阅噢。建议到个人博客读阅，CSDN这边更新比较慢，个人博客上，每天都有更新。需要教学视频和真题的，也可以点击下面的个人博客地址，在文末有免费的百度云链接分享。
个人博客地址：http://zwd596257180.gitee.io/blog/2019/04/20/soft_exam/

---

数据结构与算法基础

线性表

基本数据结构

链表

在内存中是离散存储的。

• head：头结点

• 结点：包括数据域和指针域（next 域）

循环链表

注意：循环表的最后一个结点的指针域不为空，而是指向了头结点！！！

链表的操作

单链表的结点删除

需求：删除 a2 结点

具体操作：将要删除的结点（a2）的前一个结点（a1）的 next 域指向 a2 的后一个的结点（a3）的数据域，然后释放（free）掉 a2 即可。

顺序表与链表的比较

性能类别	具体项目	顺序存储	链式存储
空间性能	存储密度	=1，更优	< 1
	容量分配	事先确定	动态改变，更优
时间性能	查找运算	O（n/2）	O(n/2)
	读运算	O（1）	O（[n+1]/2），最好情况为1，最坏情况为n
	插入运算	O（n/2）最好情况为0，最为情况为 n	O（1），更优
	删除运算	O（[n-1]/2）	O（1），更优

栈

• 思想：先进后出

队列

线性队列

• 思想：先进先出

循环队列

head：头指针（队头）

tail：尾指针（队尾）

• 当队列中没有存入值的时候，head 指针和 tail 指针指向同一个元素，并且该元素的值是空的！！！

• 当循环队列开始存入值时，head 指针是不动的，tail 指针是后移一个位置。

注意： 循环队列中为了能够区别队空和队满，牺牲了队列的最后一个空间。 判空条件：head = tail 判满条件：head = tail+1

树的遍历

前序遍历

访问顺序：先访问根节点再访问子结点。

如上图的前序遍历为：1，2，5，6，7，3，4，8，9，10

后序遍历

访问顺序：先访问子结点再访问跟结点

如上图的后序遍历为：5，6，7，2，3，9，10，8，4，1

层次遍历

访问顺序：从上往下，一层一层访问

如上图的层次遍历为：1，2，3，4，5，6，7，8，9，10

二叉树

注意：二叉树并不是一种特殊的树，而是一种独立的数据结构，有明确的左结点和右结点。

二叉树的遍历

前序遍历

• 先访问根结点，接着访问左结点，最后访问右结点。

中序遍历

• 先访问左结点，接着访问根结点，最后访问右结点。

后序遍历

• 先访问左结点，结合访问右结点，最后访问根结点。

树与二叉树的转换

1. 加线：在兄弟之间加一连线
2. 抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系
3. 旋转：以树的根结点为轴心，将整树顺时针转45°

例子：若一颗哈夫曼树共有9个顶点，则其叶子节点的个数为（5）。

n0 = n2 +1

9 = n0 + n2

---

平衡二叉树

基本概念

它或者是一颗空数，或者是一颗这样的树：树中任一结点的左、右子树的深度相差不超过1（即平衡查找树的每个结点的平衡度只能为 -1，0，1 三个值之一）。

平衡树的建立

• 第二种情况

LR 型平衡旋转（双向旋转，先左后右）

图

图的构成

• 一个图是由两个集合：V和E组成，V是有限的非空顶点集合，E是用顶点对表示的边集合，图G的顶点集和边集分别记为V（G）和E（G），而将图G表示为G=（V,E），也就是说，决定一个图需要知道它的顶点集合与边的集合。

无向图与有向图

• 区别于边是否有箭头。

假设A，B为图中的两个顶点。

无向图的边表示方法：（A，B）

有向图的边表示方法：<A→B>、<B→A>

顶点的度（degree）

• 关联顶点的边数

• 有向图：入度和出度

子图

• 已知图A和图B，如果图B中所有的顶点都是图A中的顶点，图B中的所有边都是图A中的边，则图B是图A的子图。允许两种极端情况：什么都不删；删去所有点和所有线

真子图：同“子图”概念一样，但不允许什么都不删。

完全图

无向图，每对顶点之间都有一条边相连，则称该图为完全图。

有向图，每对顶点之间都有两条有向边相互连接，则称该图为完全图。

路径和回路

• 假设图中的两个顶点A和B，A到B之间经过的边数称为路径。从顶点A出现，最后又回到顶点A，所走过的边组成的称为回路。

连通图和连通分量

无向图：任何两个顶点都有路径到达的图，称为连通图。

有向图：每两个顶点之间都能够有边（此处的边为有向边）到达的图，称为连通图。

连通分量：把连通图给分割出来，每一部分都是该图的连通分量。

邻接矩阵

拓扑排序

AOV 络

我们把用有向边表示活动之间开始的先后关系。

这种有向图称为用顶点表示活动 络，简称AOV 络。

关键路径的几个重要概念

关键路径，就是从源点到终点，路径长度最长的路径。

哈希算法（Hash)

什么是 Hash 表

Hash 函数的构造方法

处理冲突方法

哈希表的查找

可以查考这个博客学习：https://www.cnblogs.com/zhangbing12304/p/7997980.html

查找算法

正规式（正则表达式）

正规式与正规文法之间的转换：

*：代表的是大于等于0的数

正规式与有限自动机之间的转换

操作系统

进程

进程的三态图

就绪状态：进程已得到运行所需资源，只等待 CPU 的调度便可运行；

运行状态：进程已得到运行所需资源，并且得到了 CPU 的调度；

等待状态：不具备运行条件、等待时机的状态。（等待状态也称为阻塞状态）

进程的死锁

前趋图

前趋图是一个有向无循环图，记为 DAG ，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序或前趋关系“→”。

如果 Pi 必须在 Pj 之前完成，可写成 Pi → Pj，称 Pi 是 Pj 的直接前驱，而 Pj 是 Pi 的直接后继。

把没有前驱的结点，称为初始结点。

把没有后继的结点，称为终止结点。

PV 操作

临界资源：诸进程间需要互斥方式对其进行共享的资源，如打印机、磁带机等。

临界区：每个进程中访问临界资源的那段代码称为临界区。

信 量：是一种特殊的变量。

P 操作：也称为 down（）、wait（）操作，使 S=S-1，若S<0，进程暂停执行，放入信 量的等待队列。

V 操作：也称为 up（）、signal（）操作，使 S=S+1，若S<=0，唤醒等待队列种的一个进程。

生产者与消费者问题

读者与写着问题

管程

概念：指关于共享资源的数据及在其上操作的一组过程或共享数据结构及其规定的所有操作。

PV操作缺点：

易读性差、不利于修改和维护、正确性难以保证

在利用管程方法来解决生产者-消费者问题时，首先便是为它们建立一个管程，并命名为PC。包括两个过程:

• (1) put(item)过程。生产者利用该过程将自己生产的产品投放到缓冲池种，并用整型变量 count 来表示在缓冲池种已有的产量数目，当 count >= n 时，表示缓冲池已经满了，生产者须等待。

• (2) get(item)过程。消费者利用该过程从缓冲池种取出一个产品，当 count <= 0 时，表示缓冲池中已无可取用的产品，消费者应等待。

存储

实存管理

存储管理的任务是存储空间的分配与回收。在现代操作系统中通常有的单一连续分配、固定分区分配、可变分区分配（动态分配法）三种分配方法。

虚存管理

页式存储组织

解析：

已知页面大小为 4K ，因为 4K = 2^12，所以页内地址有12位。将逻辑地址8644（10）转成二进制，10 0001 1100 0100（2），其中的低12位为页内偏移量，最高两位（10）则为页 ，所以逻辑地址8644的页 为10（2），即十进制的2，所以从上图表格可以得到物理块 为8，即二进制的1000。把物理块 和页内偏移地址拼合得 1000 0001 1100 0100，化为十进制得33220。

段式存储组织

优点：便于多道程序共享内存，便于对存储器的保护，各段程序修改互不影响。

缺点：内存利用率低，内存碎片浪费大。

段页式存储组织

分段之后，在每段中进行分页。

优点：空间浪费小、存储共享容易、存储保护容易、能动态连接。

缺点：由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降。

在段页式管理的存储器中，实存等分为页、程序按逻辑模块分成段。

在多道程序环境下，每道程序还需要一个基 作为用户标志 。

每道程序都有对应的一个段表和一组页表。一个逻辑地址包括基 x、段 s、页 p和页内地址d四个部分。

页面置换算法

• 最优算法（OPT）

• 先进先出算法（FIFO）：保留最近需要使用的页面

• 最近最少使用算法（LRU）：淘汰最长时间没有被访问的页面

没有进行页面置换的，不算入缺页次数，但刚刚开始的3次需要算入。

局部性原理

时间局部性：被引用过一次的存储器位置在未来会被多次引用（通常在循环中）。

空间局部性：如果一个存储器的位置被引用，那么将来他附近的位置也会被引用。

作业管理

作业右三部分构成，即程序、数据和作业说明书，它是用户在完成一项任务过程中要求计算机系统所做工作的集合。作业的状态有后备状态、运行状态和完成状态三种。

等待时间 = 开始时间 – 提交时间

周转时间 = 完成时间 – 提交时间

最短作业优先调度算法

先来先服务调度算法

原型法

原型法的最大特点就是它采用了一种动态定义需求的方法。这样，优势也就提现出来了，即不需要有明确的需求。

螺旋模型

螺旋模型结合了瀑布模型和演化模型的优点，最主要的特点在于加入了风险分析。它是由制定计划、风险分析、实施工程、客户评估这一循环组成的，它最初从概念项目开始第一个螺旋。

项目管理基础

软件项目管理的内容

软件项目管理的核心问题（铁三角）：成本、质量、进度

软件项目管理的主要活动：

1. 启动软件项目
2. 度量
3. 估算
4. 风险分析
5. 进度安排
6. 追踪和控制

软件项目管理的三个阶段：

1. 项目启动阶段（项目立项、可行性分析、项目的初步计划）
2. 项目实施阶段（制定计划、执行计划、监控进度、根据实际情况进行计划调整、关注需求变更）
3. 项目关闭阶段

软件项目估算

自顶向下估算法

优点：耗费时间少

这种方式的一种通常采用的方法，但其并不能够有效地解决项目估算的问题，经常容易使得估算值与实际值产生很大的差异。比较适合估算系统级别的。

自底向上估算法

这种方式通常能够得到较为客观的、可操作的估算结果，而且还能够使得项目组成员主动地参与，并且通常能够对自己所做的承诺权利守信，从而为项目树立了一个良好的文化。

软件规模估算

LOC 估算法

也就是估算软件的代码行数，通常使用 KLOC（千行代码）为单位

FP 估算法

FP（功能点）是一种衡量工作量大小的单位，它的计算方法是：功能点 = 信息处理规模 X 技术复杂度，其中，技术复杂度 = 0.65 + 调节因子

• 信息处理规模
• 技术复杂度（取值0~0.05之间）

软件工作量估算

1. IBM 模型
2. 普特南模型
3. COCOMO 模型

软件成本估算

常用的估算辅助方法

Delphi 法，专家判定技术

Standard-component 方法

软件项目组织与计划

• 项目计划包括：项目组计划和个人项目计划
• 计划的编制，应该包括两个重要的图标：人员职责矩阵和甘特图
• 已获值分析（EVA） 是最常用的项目进度监控方法。

Gannt 图

特点：

• 使用水平线段表示任务的工作阶段
• 线段的起点和终点分别对应着任务的开工时间和完成时间
• 线段的长度表示完成任务所需的时间

优点：

• 标明了各任务的计划进度和当前进度，能动态地反映项目进展

缺点：

• 难以反映多个任务之间存在的复杂逻辑关系

范式

• 第一范式（1NF）：在关系模式 R 中，当且仅当所有域只包含原子值，即每个分量都是不可再分的数据项，则称实体 E 是第一范式。

• 第二范式（2NF）：当且仅当实体 E 是第一范式，且每一个非键属性完全依赖主键时，则称实体 E 是第二范式。（存在数据冗余等问题，可以每个非键属性给单独拆分到一个关系模式里）

• 第三范式（3NF）：当且仅当实体 E 是第二范式，且 E 中没有非主属性传递依赖于码时，则称实体 E 是第三范式。（消除传递函数依赖）

无损联接分解

有损：不能还原

无损：可以还原

无损联接分解：所谓无损联接分解是指将一个关系模式分解成若干个关系模式后，通过自然联接和投影等运算仍能还原到原来的关系模式，则称这种分解为无损联接分解。

投影(Project,用符 π表示)

从一个关系里面抽取指明的属性(列)。 令R为一个包含一个属性X的关系。 πX{ t(X) | t ∈ R },这里t(X)表示记录里的属性X的值。

交(Intersection,用符 ∩表示)

计算两个表集合理论上的交集。给出表R和S,R∩S是同时在R和S里面的记录的集合。我们同样要求R和S拥有相同的元/列数。

联接(Join，用符 示)

通过共同属性联接两个表。令R为一个有属性A，B，C的表，令S为一个有属性C，D，E的表。两个表有一个共同的属性C。

除(Division，用符 示)

设有关系R（X，Y）与关