中间软设笔记
第1章 计算机系统知识
1.1 计算机系统基础知识
一、中央处理单元
1、CPU 的功能： 程序控制、操作控制、时间控制、数据处理。
2、CPU的组成：CPU主要由运算器、控制器、寄存器组和内部总线等部件组成。
（1）运算器：由算术逻辑单元ALU（实现对数据的算术和逻辑运算）、累加寄存器AC（运算结果或源操作数的存放区）、数据缓冲寄存器DR（暂时存放内存的指令或数据）、和状态条件寄存器PSW（保存指令运行结果的条件码内容，如溢出标志等）组成。执行所有的算术运算，如加减乘除等；执行所有的逻辑运算并进行逻辑测试，如与、或、非、比较等。
（2）控制器：由指令寄存器IR（暂存CPU执行指令）、程序计数器PC（存放指令执行地址）、地址寄存器AR（保存当前CPU所访问的内存地址）、指令译码器ID（分析指令操作码）等组成。控制整个CPU的工作，最为重要。
3、CPU依据指令周期的不同阶段来区分二进制的指令和数据，因为在指令周期的不同阶段，指令会命令CPU分别去取指令或者数据。
二、数据表示
（一）数的表示
1、机器数有无符号数和带符号数之分。无符号数表示正数，没有符号位。带符号数最高位为符号位，正数符号位为0，负数符号位为1。
2、带符号数有下列编码方式：
（1）原码：一个数的正常二进制表示，最高位表示符号，数值0的源码有两种形式：
+0（0 0000000） 和-0（1 0000000）。
（2）反码：正数的反码即原码；负数的反码是在原码的基础上，除符号位外，其他各位按位取反。数值0的反码也有两种形式：+0（0 0000000），-0（1 1111111）。
（3）补码：正数的补码即原码；负数的补码是在原码的基础上，除符号位外，其他各位按位取反，而后末位+1，若有进位则产生进位。因此数值0的补码只有一种形式+0=-0=0 0000000.
（4）移码：用作浮点运算的阶码，无论正数负数，都是将该原码的补码的首位（符号位）取反得到移码。
（5）符号表示：要注意的是，原码最高位是代表正负号，且不参与计数；而其他编码最高位虽然也是代表正负号，但参与计数。
3、机器字长为n时各种码制表示的带符号数的取值范围：
差别在于0的表示，原码和反码分+0和-0，补码只有一个 0，因此可以多表示一个。
（二）浮点数
1、一个浮点数的表示方法不是唯一的，浮点数所能表示的数值范围由阶码确定，所表示的数值精度由尾数确定。
2、浮点数的运算：对阶（使两个数的阶码相同，小阶向大阶看齐，较小阶码增加几位，尾数就右移几位）——尾数计算（相加，若是减运算，则加负数）——结果规格化（即尾数表示规格化，带符号尾数转换为1.0xxxx 或 0.1xxxx）。
三、海明码
本质也是利用奇偶性来检错和纠错的检验方法，构成方法是在数据位之间的确定位置上插入k个校验位，通过扩大码距实现检错和纠错。
设数据位是n位，校验位是k位，则n和k必须满足以下关系：2^k-1>=n+k。
1、校验位的位数和具体的数据位的位数之间的关系
所有位都编号，从最低位编号，从1开始递增，校验位处于2的n（n=012……）次方中，即处
于第1，2，4，8，16，32，……位上，其余位才能填充真正的数据位。
2、计算校验码
（1）将所有信息位的编号都拆分成二进制表示。
（2）被校验的海明位的下标等于所有参与校验该位的校验位的下标之和，而校验位由自身校验。
3、检错和纠错原理
接收方收到海明码之后，会将每一位校验位与其校验的位数分别异或。如果是偶校验，那么运算得到的结果应该全为0，如果是奇校验，应该全为1，才是正确。
1.2 计算机体系结构
一、计算机体系结构的发展
1、按处理机的数量进行分类。Flynn 分类法：
| 体系结构类型 | 结构 | 关键特性 | 代表 |
| 单指令流、单数据流 SISD | 控制部分：一个 处 理 器：一个 主存模块：一个 | 单处理系统 | |
| 单指令流、多数据流 SIMD | 控制部分：一个 处 理 器：多个 主存模块：多个 | 各处理器以异步的形式执行执行同一条指令 | 并行处理机 阵列处理机 超级向量处理机 |
| 多指令流、单数据流 MISD | 控制部分：多个 处 理 器：一个 主存模块：多个 | 被证明不可能，至少是不实际的 | 目前没有 有文献称流水线计算机为此类 |
| 多指令流、多数据流 MIMD | 控制部分：多个 处 理 器：多个 主存模块：多个 | 能够实现作业、任务、指令等各级全面并行 | 多处理机系统 多计算机 |
2、流水线时间计算
（1）流水线周期：指令分成不同执行段，其中执行时间最长的段为流水线周期。
（2）流水线执行时间：1条指令总执行时间+（总指令条数-1）*流水线周期。
（3）单缓冲区和双缓冲区：一般来说，能够同时执行的阶段就是流水线的独立执行阶段；只能独立执行的阶段应该合并为流水线中的一个独立执行阶段。
（4）流水线吞吐率计算：吞吐率即单位时间内执行的指令条数。公式：指令条数/流水线执行时间。
（5）流水线的加速比计算：加速比即使用流水线后的效率提升度，即比不使用流水线快了多少倍，越高表明流水线效率越高，公式：不使用流水线执行时间/使用流水线执行时间。
二、存储系统
1、两级存储：Cache-主存、主存-辅存（虚拟存储体系）。
2、局部性原理：总的来说，在CPU运行时，所访问的数据会趋向于一个较小的局部空间地址内，包括下面两个方面：
（1）时间局部性原理：如果一个数据项正在被访问，那么在近期它很可能会被再次访问，即在相邻的时间里会访问同一个数据项。
（2）空间局部性原理：在最近的将来会用到的数据的地址和现在正在访问的数据地址很可能是相近的，即相邻的空间地址会被连续访问。
3、地址映射：在CPU工作时，送出的是主存单元的地址，而应从Cache存储器中读/写信息。这就需要将主存地址转换为Cache存储器地址，这种地址的转换称为地址映像，由硬件自动完成映射，分为下列三种方法：
（1）直接映像。
（2）全相联映像。
（3）组组相连映像。
4、替换算法的目标就是使Cache 获得尽可能高的命中率。
三、输入/输出技术
1、程序控制（查询）方式：CPU主动查询外设是否完成数据传输，效率极低。
2、程序中断方式：外设完成数据传输后，向CPU发送中断，等待CPU 处理数据，效率相对较高。
3、DMA方式（直接主存存取）：CPU 只需完成必要的初始化等操作，数据传输的整个过程都由 DMA 控制器来完成，在主存和外设之间建立直接的数据通路，效率很高。在一个总线周期结束后，CPU会响应 DMA请求开始读取数据；CPU响应程序中断方式请求是在一条指令执行结束时；区分指令执行结束和总线周期结束。
4、通道：也是一种处理机，内部具有独立的处理系统，使数据的传输独立于CPU。分为字节多路通道的传送方式（每一次传送一个通道的一个字节，多路通道循环）和选择通道的传送方式（选择一个通道，先传送完这个通道的所有字节，再开始下一个通道传送）。
1.3 安全性、可靠性与系统性能评测基础知识
一、计算机安全概述
1、串并联系统可靠性
（1）串联系统：一个设备不可靠，整个系统崩溃，整个系统可靠性R=R1*R2*.…*Rn。
（2）并联系统：所有设备都不可靠，整个系统才崩溃，整个系统可靠性R=1-（1-R1） *（1-R2）*...*（1-Rn）。
（3）模冗余系统：N模冗余系统由N个（N=2n+1）相同的子系统和一个表决器组成，表决器把N个子系统中占多数相同结果的输出作为输出系统的输出。在N个子系统中，只要有n+1个或n+1个以上子系统能正常工作，系统就能正常工作，输出正确的结果。
二、加密技术
1、对称加密技术
（1）数据的加密和解密的密钥(密码)是相同的，属于不公开密钥加密算法。
（2）缺点是加密强度不高（因为密钥位数少），且密钥分发困难（因为密钥还需要传输给接收方，也要考虑保密性等问题）。
（3）优点是加密速度快，适合加密大数据。
2、非对称加密技术
（1）数据的加密和解密的密钥是不同的，分为公钥和私钥。是公开密钥加密算法。
（2）缺点是加密速度慢。
（3）优点是安全性高，不容易破解。
（4）原理：发送者发送数据时，使用接收者的公钥作加密密钥，私钥作解密密钥，这样只有接收者才能解密密文得到明文。安全性更高，因为无需传输密钥。但无法保证完整性。
三、认证技术
1、数字信封原理：信是对称加密的密钥，数字信封就是对此密钥进行非对称加密。数字信封运用了对称加密技术和非对称加密技术，本质是使用对称密钥加密数据，非对称密钥加密对称密钥，解决了对称密钥的传输问题。
2、信息摘要，就是一段数据的特征信息，当数据发生了改变，信息摘要也会发生改变，发送方会将数据和信息摘要一起传给接收方，接收方会根据接收到的数据重新生成一个信息摘要，若此摘要和接收到的摘要相同，则说明数据正确。信息摘要是由哈希函数生成的。
3、数字签名：唯一标识一个发送方。发送者发送数据时，使用发送者的私钥进行加密，接收者收到数据后，只能使用发送者的公钥进行解密，这样就能唯一确定发送方，这也是数字签名的过程但无法保证机密性。
第2章 程序设计语言基础知识
2.1 程序设计语言概述
一、程序设计语言的基本概念
1、解释和编译：将高级语言翻译成目标程序执行。
（1）编译程序生成独立的可执行文件，直接运行，运行时无法控制源程序，效率高。
（2）解释程序不生成可执行文件，可以逐条解释执行，用于调试模式，可以控制源程序，因为还需要控制程序，因此执行速度慢，效率低。
2、程序设计语言定义三要素：语法、语义、语用。
3、程序设计语言的分类
（1）命令式和结构化程序设计语言，包括Fortran、PASCAL和C语言。
（2）面向对象程序设计语言，包括C++、JAVA和Smalltalk语言。
（3）函数式程序设计语言，包括LISP、Haskell、Scala、Scheme、APL 等。
（4）逻辑型程序设计语言，包括PROLOG。
二、程序设计语言的基本成分
1、数据成分：
（1）指一种程序设计语言的数据和数据类型。
（2）数据分为常量（程序运行时不可改变）、变量（程序运行时可以改变）、全局量（存储空间在静态数据区分配）、局部量（存储空间在堆栈区分配）。
（3）数据类型有整型、字符型、双精度、单精度浮点型、布尔型等。
2、运算成分：指明允许使用的运算符号及运算规则。包括算术运算、逻辑运算、 关系运算、位运算等。
3、控制成分：指明语言允许表述的控制结构。包括顺序结构、选择结构、循环结构。
4、传输成分：指明语言允许的数据传输方式。如赋值处理、数据的输入输出等。
5、函数：C程序由一个或多个函数组成，每个函数都有一个名字，其中有且仅有一个名字为main的函数作为程序运行时的起点。函数的使用涉及3个概念：函数定义、函数声明和函数调用。
（1）函数的定义包括两部分：函数首部和函数体。函数的定义描述了函数做什么和怎么做。
（2）函数首部说明了函数返回值的数据类型、函数的名字和函数运行时所需的参数及类型。函数所实现的功能在函数体部分进行描述。
（3）函数应该先声明后引用。如果程序中对一个函数的调用在该函数的定义之前进行，则应该在调用前对被调用函数进行声明。函数原型用于声明函数。函数声明的一般形式为： 返回值类型 函数名（参数类型表）；
（4）函数调用时实参与形参间交换信息的方法有值调用和引用调用两种。
①值调用（Call by Value）：若实现函数调用时将实参的值传递给相应的形参，则称为是传值调用。在这种方式下形参不能向实参传递信息。在C语言中，要实现被调用函数对实参的修改，必须用指针作为参数。即调用时需要先对实参进行取地址运算，然后将实参的地址传递给指针形参。其本质上仍属于值调用。这种方式实现了间接内存访问。
②引用调用（Call by Reference）：引用是C++中引入的概念，当形式参数为引用类型时，形参名实际上是实参的别名，函数中对形参的访问和修改实际上就是针对相应实参所做的访问和改变。
2.2 语言处理程序基础
1、编译过程：
（1）词法分析：是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词。
（2）语法分析：是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，语法分析程序判断源程序在结构上是否正确。
（3）语义分析：是编译过程的一个逻辑阶段.语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查，进行类型审查。又分为静态语义错误（在编译阶段能够查找出来）和动态语义错误（只能在运行时发现）。
（4）中间代码和目标代码：中间代码是根据语义分析产生的，需要经过优化链接，最终生成可执行的目标代码。引入中间代码的目的是进行与机器无关的代码优化处理。常用的中间代码有后缀式（逆波兰式）、三元式（三地址码）、四元式和树等形式。需要考虑三个问题：
①如何生成较短的目标代码；
②如何充分利用计算机中的寄存器，减少目标代码访问存储单元的次数；
③如何充分利用计算机指令系统的特点，以提高目标代码的质量。
2、确定的有限自动机和不确定的有限自动机：输入一个字符，看是否能得出唯一的后继，若能，则是确定的，否则若得出多个后继，则是不确定的。
3、语法分析方法
（1）自上而下语法分析：最左推导，从左至右。递归下降思想：原理是利用函数之间的递归调用模拟语法树自上而下的构造过程，是一种自上而下的语法分析方法。
（2）自下而上语法分析：最右推导，从右至左。移进-规约思想：设置一个栈，将输入符号逐个移进栈中，栈顶形成某产生式的右部时，就用左部去代替，称为归约。很明显，这个思想是通过右部来推导出左部，因此是自下而上语法分析的核心思想。
第3章 数据结构
3.1 线性结构
一、线性表
1、线性表是线性结构（每个元素最多只有一个出度和一个入度，表现为一条线状）的代表，线性表按存储方式分为顺序表和链表。
2、存储结构：
（1）顺序存储：用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的元素物理上也相邻。
（2）链式存储：存储各数据元素的结点的地址并不要求是连续的，数据元素逻辑上相邻，物理上分开。
3、顺序存储和链式存储的对比
（1）在空间方面，因为链表还需要存储指针，因此有空间浪费存在。
（2）在时间方面，当需要对元素进行破坏性操作（插入、删除）时，链表效率更高。
（3）而当需要对元素进行不改变结构操作时（读取、查找），顺序表效率更高。
二、栈和队列
1、队列是先进先出，分队头和队尾。
2、栈是先进后出，只有栈顶能进出。
3、环形队列是一个首尾相连的 FIFO 数据结构，采用数组存储，到达尾部时将转回到0位置，该转回是通过取模操作来实现的。因此环形队列逻辑上是将数组元素 q[0]与q[MAX-1]连接，形成一个存放队列的环形空间。
4、判断环形队列为空、为满的方法：
（1）设置一个标志，以区别头、尾指针的值相同时队列是空还是满；
（2）牺牲一个存储单元，约定以“队列的尾指针所指位置的下一个位置是队头指针时”表示队列满。
三、串
1、字符串是一种特殊的线性表，其数据元素都为字符。
（1）空串：长度为0的字符串，没有任何字符。
（2）空格串：由一个或多个空格组成的串，空格是空白字符，占一个字符长度。
（3）子串：串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串，空串是任意串的子串。
2、串的模式匹配：子串的定位操作，用于查找子串在主串中第一次出现的位置的算法。
（1）朴素的模式匹配算法：也称为布鲁特一福斯算法，其基本思想是从主串的第1 个字符起与模式串的第1个字符比较，若相等，则继续逐个字符进行后续的比较； 否则从主串中的第2个字符起与模式串的第1个字符重新比较，直至模式串中每个字符依次和主串中的一个连续的字符序列相等时为止，此时称为匹配成功，否则称为匹配失败。
（2）改进的模式匹配算法（KMP算法）
对基本模式匹配算法的改进，其改进之处在于：每当匹配过程中出现相比较的字符不相等时，不需要回溯主串的字符位置指针，而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的距离，再继续进行比较。
3.2 数组、矩阵和广义表
一、数组
1、数组是定长线性表在维度上的扩展，即线性表中的元素又是一个线性表。N维数组是一种“同构”的数据结构，其每个数据元素类型相同、结构一致。
2、数组结构的特点：数据元素数目固定；数据元素类型相同；数据元素的下标关系具有上下界的约束且下标有序。
3、数组数据元素固定，一般不做插入和删除运算，适合于采用顺序结构。
4、若题目没有特别说明（注意审题），数组元素一般都是从0开始计数的。
二、矩阵
1、特殊矩阵：矩阵中的元素（或非0元素）的分布有一定的规律。常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵。
| 矩阵 | 特点 | 存储数组B[K]与矩阵元素 aij对应公式； 或 示意图 |
| 对称矩阵 | 矩阵An*n中的元素特点为 aij=aji（1<=ij<=n） | |
| 对角矩阵 | 矩阵中的非零元素都集中在以主对角线为中心的带状区域 | 三对角矩阵示意图：
 |
| 三角矩阵 | 矩阵中主对角线上方都为非零元素，下方都为零元素（或相反）。 |
 |
三、广义表
1、广义表是线性表的推广，是由0个或多个单元素或子表组成的有限序列。
2、广义表与线性表的区别：线性表的元素都是结构上不可分的单元素，而广义表的元素既可以单元素，也可以是有结构的表。
3、广义表一般记为：LS=（a1，a2，…，an）
（1）其中LS是表名，a1是表元素，它可以是表（称为子表），也可以是数据元素（称为原子）。（2）其中n是广义表的长度（也就是最外层包含的元素个数），n=0的广义表为空表；而递归定义的重数就是广义表的深度，即定义中所含括号的重数（单边括号的个数，原子的深度为0，空表的深度为1）。
4、head（）：取表头（广义表第一个表元素，可以是子表也可以是单元素）。
5、tail（）：取表尾（广义表中，除了第一个表元素之外的其他所有表元素构成的表，非空广义表的表尾必定是一个表，即使表尾是单元素）操作。
3.3 树
一、树与二叉树的定义
1、树是n个节点的有限集合（n>=0），当n=0时称为空树，在任一颗非空树中，有且仅有一个根节点。其余结点可分为m（m20）个互不相交的有限子集T1，T2，…，Tm，其中，每个Ti又都是一棵树，并且称为根结点的子树。
2、树的基本概念如下：
（1）双亲、孩子和兄弟。结点的子树的根称为该结点的孩子；相应地，该结点称为其子结点的双亲。具有相同双亲的结点互为兄弟。
（2）结点的度。一个结点的子树的个数记为该结点的度。
（3）叶子结点。叶子结点也称为终端结点，指度为0的结点。
（4）内部结点。度不为0的结点，也称为分支结点或非终端结点。除根结点以外，分支结点也称为内部结点。
（5）结点的层次。根为第一层，根的孩子为第二层，依此类推，若某结点在第i 层，则其孩子结点在第i+1层。
（6）树的高度。一棵树的最大层数记为树的高度（或深度）。
（7）有序（无序）树。若将树中结点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树，否则称为无序树。
3、二叉树是n个节点的有限集合，它或者是空树，或者是由一个根节点及两颗互不相交的且分别称为左、右子树的二叉树所组成。
二、二叉树的性质与存储结构
1、二叉树的性质
（1）二叉树第i 层（i≥1）上至多有2^（i-1）个节点。
（2）深度为k的二叉树至多有2^k-1个节点（k≥1）。
（3）对任何一棵二叉树，若其终端节点数为n0，度为2的节点数为n2，则n0=n2+1。
（4）具有n个节点的完全二叉树的深度为[log2 n]+1。
2、二叉树的顺序存储结构
（1）是用一组连续的存储单元存储二叉树中的节点，按照从上到下，从左到右的顺序依次存储每个节点。
（2）对于深度为k的完全二叉树，除第k层外，其余每层中节点数都是上一层的两倍，由此。假设有编号为i的节点，则有：
①若i=1，则该节点为根节点，无双亲；若i>1，则该节点的双亲节点为[i/2]。
②若2i≤n，则该节点的左孩子编号为2i，否则无左孩子。
③若2i+1≤n，则该节点的右孩子编号为2i+1，否则无右孩子。
4、二叉树的链式存储结构由于二叉树中节点包含有数据元素、左子树根、右子树根及双亲等信息，因此可以用三叉链表或二叉链表（即一个节点含有三个指针或两个指针）来存储二叉树，链表的头指针指向二叉树的根节点。
三、二叉树的遍历
1、一颗非空的二叉树由根节点、左子树、右子树三部分组成，遍历这三部分，也就遍历了整颗二叉树。
2、遍历的基本顺序是先左子树后右子树，但根节点顺序可变，以根节点访问的顺序为准有下列三种遍历方式：
（1）先序（前序）遍历：根左右。
（2）中序遍历；左根右
（3）后序遍历：左右根。
4、层次遍历：按层次，从上到下，从左到右。
四、线索二叉树
1、若n个节点的二叉树使用二叉链表存储，则必然有n+1个空指针域，利用这些空指针域来存放节点的前驱和后继节点信息，为此，需要增加两个标志，以区分指针域存放的到底是孩子结点还是遍历节点，如下：
2、若二叉树的二叉链表采用上述结构，则称为线索链表，其中指向前驱、后继节点的指针称为线索，加上线索的二叉树称为线索二叉树。
五、最优二叉树
1、哈夫曼树的求法：给出一组权值，将其中两个最小的权值作为叶子节点，其和作为父节点，组成二叉树，而后删除这两个叶子节点权值，并将父节点的值添加到该组权值中。重复进行上述步骤，直至所有权值都被使用完。
2、若需要构造哈夫曼编码（要保证左节点值小于右节点的值，才是标准的哈夫曼树），将标准哈夫曼树的左分支设为0，右分支设为1，写出每个叶节点的编码，会发现，哈夫曼编码前缀不同，因此不会混淆，同时也是最优编码。
六、树和森林
1、将一个森林转换为一棵二叉树的方法是：先将森林中的每一棵树转换为二叉树，再将第一棵树的根作为转换后的二叉树的根，第一棵树的左子树作为转换后二叉树根的左子树，第二棵树作为转换后二叉树的右子树，第三棵树作为转换后二叉树根的右子树的右子树，依此类推，森林就可以转换为一棵二叉树，
3.4 图
一、图的定义与存储
1、图的定义
（1）无向图：图的结点之间连接线是没有箭头的，不分方向。
（2）有向图：图的结点之间连接线是箭头，区分A到B，和B到A是两条线。
（3）完全图：无向完全图中，节点两两之间都有连线，n个结点的连线数为（n- 1）+（n-2）+…+1=n*（n-1）/2；有向完全图中，节点两两之间都有互通的两个箭头，n 个节点的连线数为n*（n-1）.
（4）度、出度和入度：顶点的度是关联与该顶点的边的数目。在有向图中，顶点的度为出度和入度之和。
（5）路径：存在一条通路，可以从一个顶点到达另一个顶点。
（6）子图：有两个图G=（V，E）和G'=（V'，E'），如果V'≤V且E'∈E，则称G'为G的子图。
（7）连通图和连通分量：针对无向图。若从顶点v到顶点u之间是有路径的，则说明v和u之间是连通的，若无向图中任意两个顶点之间都是连通的，则称为连通图。无向图G的极大连通子图称为其连通分量。
（8）强连通图和强连通分量：针对有向图。若有向图任意两个顶点间都互相存在路径，即存在v到u，也存在u到v的路径，则称为强连通图。有向图中的极大连通子图称为其强连通分量。
（9）网：边带权值的图称为网。
2、图的存储
（1）邻接矩阵：假设一个图中有n个节点，则使用n阶矩阵来存储这个图中各节点的关系，规则是若节点i到节点j有连线，则矩阵Ri，j=1，否则为0。
（2）邻接链表：用到了两个数据结构，先用一个一维数组将图中所有顶点存储起来，而后，对此一维数组的每个顶点元素，使用链表挂上其出度到达的结点的编号和权值。
二、图的遍历
1、图的遍历是指从图的任意节点出发，沿着某条搜索路径对图中所有节点进行访问且只访问一次，分为以下两种方式：
（1）深度优先遍历：从任一顶点出发，遍历到底，直至返回，再选取任一其他节点出发，重复这个过程直至遍历完整个图；
（2）广度优先遍历：先访问完一个顶点的所有邻接顶点，而后再依次访问其邻接顶点的所有邻接顶点，类似于层次遍历。
三、生成树及最小生成树
1、图的最小生成树假设有n个节点，那么这个图的最小生成树有n-1条边（不会形成环路，是树非图），这n-1条边应该会将所有顶点都连接成一个树，并且这些边的权值之和最小，因此称为最小生成树。
2、普里姆算法：从任意顶点出发，找出与其邻接的边权值最小的，此时此边的另外一个顶点自动加入树集合中，而后再从这这个树集合的所有顶点中找出与其邻接的边权值最小的，同样此边的另外一个顶点加入树集合中，依次递归，直至图中所有顶点都加入树集合中，此时此树就是该图的最小生成树。普里姆算法的时间复杂度为O（n^2），与图中的边数无关，因此该算法适合于求边稠密的网的最小生成树：
3、克鲁斯卡尔算法：这个算法是从边出发的，因为本质是选取权值最小的n-1条边，因此，就将边按权值大小排序，依次选取权值最小的边，直至囊括所有节点，要注意，每次选边后要检查不能形成环路。克鲁斯卡尔算法的时间复杂度为O（eloge），与图中的顶点数无关，因此该算法适合于求边稀疏的网的最小生成树。
四、拓扑排序和关键路径
1、拓扑序列
若图中一个节点入度为0，则应该最先执行此活动，而后删除掉此节点和其关联的有向边，再去找图中其他没有入度的结点，执行活动，依次进行。
3.5 查找
一、静态查找表的查找方法
1、顺序查找时间复杂度：O（n）。
2、折半查找
（1）只适用于待查找序列中的元素是有序排列的情况。
（2）中间值位置求出若为小数，应该向下取整。
（3）时间复杂度：O（log2n）。
二、动态查找表
1、二叉排序树
（1）树上的每个节点都存储一个值，且每个节点的所有左孩子结点值都小于父节点值，而所有右孩子结点值都大于父节点值，是一个有规律排列的二叉树，这种数据结构可以方便查找、插入等数据操作。
（2）查找效率取决于二叉排序树的深度，二叉树深度越深，则效率最差，对于结点个数相同的二叉排序树，其深度排序为 满二叉树<完全二叉树<平衡二叉树<单枝树，因此效率最低的是最深的单枝树。
2、平衡二叉树
（1）在查找二叉树特点的基础上，要求每个节点的平衡度只能为0或1或-1.
（2）节点的左右子树深度就是其左右子树各自的层数，而后将左子树深度减去右子树深度，就得到了该节点的平衡度。
（3）平衡二叉树就是任意左右子树层次相差不超过1。
三、哈希表
1、哈希表通过一个以记录的关键字为自变量的函数（称为哈希函数）得到该记录的存储地址，所以在哈希表中进行查找操作时，需要用同一哈希函数计算得到待查记录的存储地址，然后到相应的存储单元去获得有关信息再判定查找是否成功。
2、哈希函数产生了冲突的解决方法如下：
（1）开放定址法：Hi=（H（key）+di）m，i=1， 2，…，k（k≤m-1） 其中，H（key）为哈希函数；m为哈希表表长；di为增量序列。
（2）链地址法。它在查找表的每一个记录中增加一个链域，链域中存放下一个具有相同哈希函数值的记录的存储地址。利用链域，就把若干个发生冲突的记录链接在一个链表内。当链域的值为NULL 时，表示已没有后继记录了。因此，对于发生冲突时的查找和插入操作就跟线性表一样了。
（3）再哈希法：在同义词发生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。这种方法不易产生聚集现象，但增加了计算时间。
（4）建立一个公共溢出区。无论由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入到公共溢出区中。
3.6 排序
一、简单排序
1、冒泡排序
（1）n 个记录进行冒泡排序的方法是：
①首先将第一个记录的关键字和第二个记录的关键字进行比较
②若为逆序，则交换这两个记录的值
③然后比较第二个记录和第三个记录的关键字
④依此类推，直至第n-1 个记录和第n 个记录的关键字比较过为止。
（2）上述过程称为一趟冒泡排序，其结果是关键字最大的记录被交换到第n个记录的位置上。然后进行第二趟冒泡排序，对前n—1个记录进行同样的操作，其结果是关键字次大的记录被交换到第n-1个记录的位置上。
（3）最多进行n-1趟，所有记录有序排列。若在某趟冒泡排序过程没有进行相邻位置的元素交换处理，则可结束排序过程。
（4）本质是从最后两个元素开始进行比较，将较小的元素交换到前面去，依次进行比较交换。比较是为了交换，交换次数很多。
2、简单选择排序：本质就是每次选择出最小的元素进行交换，主要是选择比较过程，交换过程只有一次。
二、希尔排序
1、基本思想：先将整个待排记录序列分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。
3、具体做法：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组，将所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量d2（d2<d1），重复上述分组和排序工作，依此类推，直至所取的增量di=1（di<di-1<…<d2<d1），即所有记录放在同一组进行直接插入排序为止。
4、希尔排序实际是为了解决大数据的排序问题，当待排序的数据很多时，使用直接插入排序效率很低，因此，采取分组的方法，使问题细化，可以提高效率，适用于多数据。
三、堆排序
1、堆排序的基本思想是：对一组待排序记录的关键字，首先按堆的定义排成一个序列（即建立初始堆），从而可以输出堆顶的最大关键字（对于大根堆而言），然后将剩余的关键字再调整成新堆，便得到次大的关键字，如此反复，直到全部关键字排成有序序列为止。
2、初始堆的建立方法是：将待排序的关键字分放到一棵完全二叉树的各个结点中（此时完全二叉树并不一定具备堆的特性）。显然，所有
的结点Ki；都没有子结点，以这样的Ki为根的子树已经是堆，因此初始建堆可从完全二叉树的第
个结点 Ki开始，通过调整，逐步使以
为根的子树满足堆的定义。
四、内部排序方法小结
1、各种排序方法的性能比较
第4章 操作系统知识
4.1 操作系统概述
1、操作系统的作用：通过资源管理提高计算机系统的效率；改善人机界面向用户提供友好的工作环境。
2、操作系统的特征：并发性、共享性、虚拟性、不确定性。
3、操作系统的功能：进程管理、存储管理、文件管理、设备管理、作业管理。
4.2 进程管理
一、基本概念
1、进程的组成：进程控制块PCB（唯一标志）、程序（描述进程要做什么）、数据（存放进程执行时所需数据）。
2、进程基础的状态是下左图中的三态图，这是系统自动控制时只有三种状态，而下右图中的五态，是多了两种状态：静止就绪和静止阻塞，需要人为的操作才会进入对应状态，活跃就绪即就绪，活跃阻塞即等待。
二、进程间的通信
1、互斥：某资源（即临界资源）在同一时间内只能由一个任务单独使用，使用时需要加锁，使用完后解锁才能被其他任务使用；如打印机。
2、同步：多个任务可以并发执行，只不过有速度上的差异，在一定情况下停下等待，不存在资源是否单独或共享的问题；如自行车和汽车。
3、P操作：申请资源，S=S-1，若S>=0，则执行P操作的进程继续执行；若S<0，则置该进程为阻塞状态（因为无可用资源），并将其插入阻塞队列。
4、V操作：释放资源，S=S+1，若S>0，则执行V操作的进程继续执行；若S<=0， 则从阻塞状态唤醒一个进程，并将其插入就绪队列（此时因为缺少资源被P操作阻塞的进程可以继续执行），然后执行V操作的进程继续。
三、进程调度
1、进程调度方式是指当有更高优先级的进程到来时如何分配CPU。分为可剥夺和不可剥夺两种，可剥夺指当有更高优先级进程到来时，强行将正在运行进程的 CPU 分配给高优先级进程；不可剥夺是指高优先级进程必须等待当前进程自动释放 CPU。
2、三级调度
（1）高级调度（又称长调度或作业调度，决定哪个作业可以调入系统中）；
（2）中级调度（又称对换调度，决定哪个就绪进程可以调入内存中）；
（3）低级调度（又称进程调度，决定内存中哪个就绪进程可以占用CPU）。
3、调度算法：
（1）先来先服务 FCFS：先到达的进程优先分配CPU。用于宏观调度。
（2）时间片轮转：分配给每个进程CPU时间片，轮流使用CPU，每个进程时间片大小相同，很公平，用于微观调度。
（3）优先级调度：每个进程都拥有一个优先级，优先级大的先分配 CPU。
（4）多级反馈调度：时间片轮转和优先级调度结合而成，设置多个就绪队列1，2，3…n，每个队列分别赋予不同的优先级，分配不同的时间片长度；新进程先进入队列1的末尾，按 FCFS原则，执行队列1的时间片；若未能执行完进程，则转入队列2的末尾，如此重复。
四、死锁
1、当一个进程在等待永远不可能发生的事件时，就会产生死锁，若系统中有多个进程处于死锁状态，就会造成系统死锁。
2、死锁产生的四个必要条件：资源互斥、每个进程占有资源并等待其他资源、 系统不能剥夺进程资源、进程资源图是一个环路。
3、死锁产生后，解决措施是打破四大条件，有下列方法：
（1）死锁预防。
（2）死锁避免。
（3）死锁检测。
（4）死锁解除。
4、死锁资源计算：系统内有n个进程，每个进程都需要R个资源，那么其发生死锁的最大资源数为n*（R-1）。其不发生死锁的最小资源数为n*（R-1）+1。
五、线程
1、传统的进程有两个属性：
（1）可拥有资源的独立单位；
（2）可独立调度和分配的基本单位。
2、引入线程的原因是进程在创建、撤销和切换中，系统必须为之付出较大的时空开销，故在系统中设置的进程数目不宜过多，进程切换的频率不宜太高，这就限制了并发程度的提高。引入线程后，将传统进程的两个基本属性分开，线程作为调度和分配的基本单位，进程作为独立分配资源的单位。用户可以通过创建线程来完成任务，以减少程序并发执行时付出的时空开销。
4.3 存储管理
一、基本概念
1、存储器的结构：寄存器——高速缓存 Cache——主存——外存。
2、地址重定位：将逻辑地址转换为实际主存物理地址的过程，分为静态重定位（在程序装入主存时就完成了转换）、动态重定位（边运行边转换）。
二、存储管理方案
1、分区存储组织，就是整存，将某进程运行所需的内存整体一起分配给它，然后再执行。
2、三种分区方式：
（1）固定分区。
（2）可变分区：请求和释放分区主要有如下4种算法：最佳适应算法、最差适应算法、首次适应算法、循环首次适应算法。
（3）可重定位分区。
三、分页存储管理
1、纯分页存储管理。
2、快表
（1）是一块小容量的相联存储器，由快速存储器组成，按内容访问，速度快，并且可以从硬件上保证按内容并行查找，一般用来存放当前访问最频繁的少数活动页面的页号。
（2）是将页表存于Cache中；访问一次Cache和一次内存。
四、分段存储管理
1、将进程空间分为一个个段，每段也有段号和段内地址，与页式存储不同的是，每段物理大小不同，分段是根据逻辑整体分段的，因此，段表也与页表的内容不同，页表中直接是逻辑页号对应物理块号，段表有段长和基址两个属性，才能确定一个逻辑段在物理段中的位置。
五、段页式存储管理
1、对进程空间先分段，后分页，优缺点如下：
（1）优点：空间浪费小、存储共享容易、存储保护容易、能动态链接。
（2）缺点：由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降。
4.4 设备管理
I/O设备管理软件的所有层次及每一层功能如下图：
4.5 文件管理
1、文件的物理结构是指文件在物理存储设备上的存放方法，包括：
（1）连续结构。
（2）链接结构。
（3）索引结构：将逻辑上连续的文件信息（如记录）存放在不连续的物理块中，系统为每个文件建立一张索引表。索引表记录了文件信息所在的逻辑块号对应的物理块号，并将索引表的起始地址放在与文件对应的文件目录项中。
（4）多个物理块的索引表。
2、存取方法：顺序存取、随机存取。
3、文件存储空间的管理：
（1）空闲区表。
（2）位示图：这种方法是在外存上建立一张位示图（Bitmap），记录文件存储器的使用情况。每一位对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用。
（3）空闲块链。
（4）成组链接法。
第5章 软件工程基础知识
5.1 软件工程概述
1、软件生存周期：可行性分析与项目开发计划、需求分析、概要设计（选择系统解决方案，规划子系统）、详细设计（设计子系统内部具体实现）、编码、测试、维护。
2、能力成熟度模型 CMM
| 能力等级 | 特点 | 关键过程区域 |
| 初始级 | 软件过程的特点是杂乱无章，有时甚至很混乱，几乎没有明确定义的步骤，项目的成功完全依赖个人的努力和英雄式核心人物的作用。 | |
| 可重复级 | 建立了基本的项目管理过程和实践来跟踪项目费用、进度和功能特性，有必要的过程准则来重复以前在同类项目中的成功。 | 软件配置管理、软件质量保证、软件子合同管理、软件项目跟踪与监督、软件项目策划、软件需求管理。 |
| 已定义级 | 管理和工程两方面的软件过程已经文档化、标准化，并综合成整个软件开发组织的标准软件过程。所有项目都采用根据实际情况修改后得到的标准软件过程来发和维护软件。 | 同行评审、组间协调、软件产品工程、集成软件管理、培训大纲、组织过程定义、组织过程集点。 |
| 已管理级 | 制定了软件过程和产品质量的详细度量标准。对软件过程和产品质量有定量的理解和控制。 | 软件质量管理和定量过程管理。 |
| 优化级 | 加强了定量分析，通过来自过程质量反馈和来自新观念、新技术的反馈使过程能不断持续地改进。 | 过程更改管理、技术改革管理和缺陷预防。 |
5.2 软件过程模型
1、瀑布模型：
（1）是一个经典的软件生命周期模型，一般将软件开发分为：可行性分析（计划）、需求分析、软件设计（概要设计、详细设计）、编码（含单元测试）、测试、运行维护等几个阶段。只适用于需求明确或者二次开发（需求稳定），当需求不明确时，最终开发的项目会错误，有很大的缺陷。
（2）瀑布模型特点
①从上一项开发活动接受该项活动的工作对象作为输入。
②利用这一输入，实施该项活动应完成的工作内容。
③给出该项活动的工作成果，作为输出传给下一项开发活动。
④对该项活动的实施工作成果进行评审。若其工作成果得到确认，则继续进行下一项开发活动；否则返回前一项，甚至更前项的活动。尽量减少多个阶段间的反复。以相对来说较小的费用来开发软件。
2、增量模型：
（1）首先开发核心模块功能，而后与用户确认，之后再开发次核心模块的功能，即每次开发一部分功能，并与用户需求确认，最终完成项目开发，优先级最高的服务最先交付，但由于并不是从系统整体角度规划各个模块，因此不利于模块划分。
（2）每一次增量版本都可作为独立可操作的作品，而原型的构造一般是为了演示。
3、螺旋模型：是多种模型的混合，针对需求不明确的项目，与原型类似，但是增加了风险分析，这也是其最大的特点。适合大型项目开发。
5.3 需求分析
一、软件需求
1、软件需求分为需求开发和需求管理两大过程。
2、需求的层次
（1）业务需求。
（2）用户需求。
（3）系统需求：功能需求、非功能需求、设计约束。
3、质量功能部署
（1）质量功能部署（QFD）是一种将用户要求转化成软件需求的技术，其目的是最大限度地提升软件工程过程中用户的满意度。
（2）QFD将软件需求分为三类：常规需求、期望需求、意外需求。
二、需求分析
1、结构化的需求分析
（1）结构化特点：自顶向下，逐步分解，面向数据。
（2）三大模型：功能模型（数据流图）、行为模型（状态转换图）、数据模型（E-R图）以及数据字典。
三、需求定义
1、需求定义方法
（1）严格定义也称为预先定义，需求的严格定义建立在以下的基本假设之上： 所有需求都能够被预先定义。开发人员与用户之间能够准确而清晰地交流。采用图形（或文字）可以充分体现最终系统。
（2）原型方法，迭代的循环型开发方式：
①需要注意的问题：并非所有的需求都能在系统开发前被准确地说明。项目干系人之间通常都存在交流上的困难，原型提供了克该服困难的一个手段。
②特点：需要实际的、可供用户参与的系统模型。有合适的系统开发环境。反复是完全需要和值得提倡的，需求一旦确定，就应遵从严格的方法。
四、需求管理
1、需求变更和风险
（1）主要关心需求变更过程中的需求风险管理，带有风险的做法有：无足够用户参与、忽略了用户分类、用户需求的不断增加、模棱两可的需求、不必要的特性、过于精简的SRS、不准确的估算。
（2）变更产生的原因：外部环境的变化、需求和设计做的不够完整、新技术的出现、公司机构重组造成业务流程的变化。
（3）变更控制委员会 CCB：也称为配置控制委员会，其任务时对建议的配置项变更做出评价、审批，以及监督已经批准变更的实施。
5.4 系统设计
1、流程表示工具
（1）程序流程图：任何复杂的程序流程图都应该由顺序、选择和循环结构组合或嵌套而成。
（2）IPO图：描述构成软件系统的每个模块的输入、输出和数据加工。
（3）N-S图：表示嵌套和层次关系，并具有强烈的结构化特征，不适合于复杂程序的设计。
（4）问题分析图（PAD）：支持结构化程序设计的图形工具。
2、系统设计方法：结构化设计方法，面向对象设计方法。
3、系统设计基本原理：抽象化、自顶而下，逐步求精、信息隐蔽、模块独立。
4、系统设计原则
（1）保持模块的大小适中；
（2）尽可能减少调用的深度；
（3）多扇入，少扇出；
（4）单入口，单出口；
（5）模块的作用域应该在模块之内；
（6）功能应该是可预测的。
5、人机界面设计的三大原则：置于用户的控制之下、减少用户的记忆负担、保持界面的一致性
5.5 系统测试
一、传统软件的测试策略
1、确认测试：主要用于验证软件的功能、性能和其他特性是否与用户需求一致。根据用户的参与程度，通常包括以下类型：
（1）内部确认测试：主要由软件开发组织内部按照SRS进行测试。
（2）α测试：用户在开发环境下进行测试。
（3）β测试：用户在实际使用环境下进行测试，通过改测试后，产品才能交付用户。
（4）验收测试：针对SRS，在交付前以用户为主进行的测试。其测试对象为完整的、 集成的计算机系统。验收测试的目的是，在真实的用户工作环境下，检验软件系统是否满足开发技术合同或SRS。验收测试的结论是用户确定是否接收该软件的主要依据。除应满足一般测试的准入条件外，在进行验收测试之前，应确认被测软件系统已通过系统测试。
二、测试方法
1、黑盒测试用例：将程序看做一个黑盒子，只知道输入输出，不知道内部代码，由此设计出测试用例，分为下面几类：
（1）等价类划分：把所有的数据按照某种特性进行归类，而后在每类的数据里选取一个即可。等价类测试用例的设计原则：设计一个新的测试用例，使其尽可能多地覆盖尚未被覆盖的有效等价类，重复这一步，直到所有的有效等价类都被覆盖为止；计一个新的测试用例，使其仅覆盖一个尚未被覆盖的无效等价类，重复这一步，直到所有的无效等价类都被覆盖为止。
（2）边界值划分：将每类的边界值作为测试用例，边界值一般为范围的两端值以及在此范围之外的与此范围间隔最小的两个值，如年龄范围为0-150，边界值为0，150，-1，151四个。
（3）错误推测：没有固定的方法，凭经验而言，来推测有可能产生问题的地方，作为测试用例进行测试。
（4）因果图：由一个结果来反推原因的方法，具体结果具体分析，没有固定方法。
2、白盒测试用例：知道程序的代码逻辑，按照程序的代码语句，来设计覆盖代码分支的测试用例，覆盖级别从低至高分为下面几种：
（1）语句覆盖SC：逻辑代码中的所有语句都要被执行一遍，覆盖层级最低，因为执行了所有的语句，不代表执行了所有的条件判断。
（2）判定覆盖DC：逻辑代码中的所有判断语句的条件的真假分支都要覆盖一次。
（3）条件覆盖CC：针对每一个判断条件内的每一个独立条件都要执行一遍真和假。
（4）条件判定组合覆盖CDC：同时满足判定覆盖和条件覆盖。
（5）路径覆盖：逻辑代码中的所有可行路径都覆盖了，覆盖层级最高。
5.6 运行和维护知识
一、系统转换
1、遗留系统是指任何基本上不能进行修改和演化以满足新的变化了的业务需求的信息系统。
2、系统转换是指新系统开发完毕，投入运行，取代现有系统的过程，需要考虑多方面的问题，以实现与老系统的交接，有以下三种转换计划：
（1）直接转换。
（2）并行转换。
（3）分段转换。
3、数据转换与迁移：将数据从旧数据库迁移到新数据库中。要在新系统中尽可能的保存旧系统中合理的数据结构，才能降低迁移的难度。也有三种方法：系统切换前通过工具迁移、系统切换前采用手工录入、系统切换后通过新系统生成。
5.7 软件项目管理
一、范围管理
1、范围管理确定在项目内包括什么工作和不包括什么工作，由此界定的项目范围在项目的全生命周期内可能因种种原因而变化，项目范围管理也要管理项目范围的这种变化。项目范围的变化也叫变更。
2、对项目范围的管理，是通过5个管理过程来实现的：
（1）规划范围管理（编制范围管理计划）。
（2）定义范围。详细描述产品范围和项目范围，编制项目范围说明书，作为以后项目决策的基础。
（3）创建工作分解结构。
（4）确认范围。
（5）范围控制。
二、软件项目估算
1、COCOMO模型：常见的软件规模估算方法，常用的代码行分析方法作为其中一种度量估计单位，以代码行数估算出每个程序员工作量，累加得软件成本。
2、COCOMOⅡ模型：COCOMO的升级，也是以软件规模作为成本的主要因素，考虑多个成本驱动因子。该方法包括三个阶段性模型，即应用组装模型、早期设计阶段模型和体系结构阶段模型。包含三种不同规模估算选择：对象点、功能点和代码行。
三、进度管理
1、进度管理包括以下过程：
（1）活动定义。
（2）活动排序。
（3）活动资源估算。
（4）活动历时估算。
（5）进度计划编制。
（6）进度控制。
2、进行活动资源估算的方法主要有专家判断法、替换方案的确定、公开的估算数据、估算软件和自下而上的估算。
3、进度安排的常用图形描述方法有Gantt 图(甘特图)和项目计划评审技术(Program Evaluation & Review Technique，PERT)图。
4、关键路径法
（1）进度网络图中可能有多条关键路径，因为活动会变化，因此关键路径也在不断变化中。
（2）总浮动时间=最迟开始LS-最早开始ES或 最迟完成LF-最早完成EF 或 关键路径-非关键路径时长。
（3）自由浮动时间=紧后活动最早开始时间的最小值-本活动的最早完成时间。
四、成本管理
1、项目成本管理包括成本估算、成本预算和成本控制三个过程。
（1）成本估算是对完成项目所需成本的估计和计划，是项目计划中的一个重要的、关键的、敏感的部分；成本估算主要靠分解和类推的手段进行，基本估算方法分为三类：自顶向下的估算、自底向上的估算和差别估算法。
（2）成本预算是把估算的总成本分配到项目的各个工作包，建立成本基准计划以衡量项目绩效；应急储备和管理储备。
（3）成本控制保证各项工作在各自的预算范围内进行。
2、成本的类型
(1)可变成本：随着生产量、工作量或时间而变的成本为可变成本。可变成本又称变动成本。
(2)固定成本：不随生产量、工作量或时间的变化而变化的非重复成本为固定成本。
(3)直接成本：直接可以归属于项目工作的成本为直接成本。如项目团队差旅费、工资、 项目使用的物料及设备使用费等。
(4)间接成本：来自一般管理费用科目或几个项目共同担负的项目成本所分摊给本项目的费用，就形成了项目的间接成本，如税金、额外福利和保卫费用等。
(5)机会成本：是利用一定的时间或资源生产一种商品时，而失去的利用这些资源生产其他最佳替代品的机会就是机会成本，泛指一切在做出选择后其中一个最大的损失。
(6)沉没成本：是指由于过去的决策已经发生了的，而不能由现在或将来的任何决策改变的成本。沉没成本是一种历史成本，对现有决策而言是不可控成本，会很大程度上影响人们的行为方式与决策，在投资决策时应排除沉没成本的干扰。
五、软件配置管理
1、配置管理是为了系统地控制配置变更，在系统的整个生命周期中维持配置的完整性和可跟踪性，而标识系统在不同时间点上配置的学科。
2、配置管理包括6个主要活动：
（1）制订配置管理计划；（2）配置标识；（3）配置控制；（4）配置状态报告；
（5）配置审计；（6）发布管理和交付。
3、典型配置项包括项目计划书、需求文档、设计文档、源代码、可执行代码、测试用例、 运行软件所需的各种数据，它们经评审和检查通过后进入配置管理。
4、每个配置项的主要属性有：名称、标识符、文件状态、版本、作者、日期等。
5、所有配置项的操作权限应由CMO(配置管理员)严格管理，基本原则是：基线配置项向开发人员开放读取的权限；非基线配置项向PM、CCB及相关人员开放。
6、配置项状态：草稿、正式、修改。
7、对基线的变更必须遵循正式的变更控制程序。
8、配置库可以分：开发库（由开发人员自行控制）、受控库（需要走变更流程）、产品库（真要修改的话需要走变更流程）。
六、风险管理
1、技术风险是指潜在的设计、实现、接口、测试和维护方面的问题。技术风险威胁到待开发系统的质量和预定的交付时间。
2、风险的属性：随机性、相对性、风险的可变性。
3、风险的分类：
（1）按照后果的不同，风险可划分为纯粹风险和投机风险。
（2）按风险来源划分，自然风险和人为风险。
（3）按是否可管理划分，可管理和不可管理， 也要看主体管理水平。
（4）按影响范围划分，局部风险和总体风险。
（5）按后果承担者划分：业主、政府、承包商、投资方、设计单位、监理单位、 保险公司等。
（6）按可预测性划分：已知风险、可预测风险、不可预测风险。
4、风险管理过程
（1）风险管理计划编制。
（2）风险识别。
（3）风险定性分析。
（4）风险定量分析。
（5）风险应对计划编制。
（6）风险监控。
5.8 软件质量
1、ISO/IEC 9126 软件质量模型
（1）功能性。
（2）可靠性。
（3）可用性。
（4）效率。
（5）可维护性。
（6）可移植性。
第6章 结构化开发方法
6.1 系统分析与设计概述
1、系统结构设计原则：
（1）分解-协调原则。
（2）自顶向下的原则。
（3）信息隐蔽、抽象的原则。
（4）一致性原则。
（5）明确性原则。
（6）模块之间的耦合尽可能小，模块的内聚度尽可能高。
（7）模块的扇入系数和扇出系数要合理。
（8）模块的规模适当。
2、子系统划分的原则：
（1）子系统要具有相对独立性。
（2）子系统之间数据的依赖性尽量小。
（3）子系统划分的结果应使数据冗余较小。
（4）子系统的设置应考虑今后管理发展的需要。
（5）子系统的划分应便于系统分阶段实现。
（6）子系统的划分应考虑到各类资源的充分利用。
3、一个模块应具备以下4个要素：输入和输出、处理功能、内部数据、程序代码。
6.2 结构化分析方法
1、结构化方法的分析结果由以下几部分组成：一套分层的数据流图、一本数据词典、一组小说明(也称加工逻辑说明)、补充材料。
一、数据流图
1、基本图形元素：外部实体、加工、数据存储、数据流。
二、数据字典（DD）
1、数据字典有以下4 类条目：数据流、数据项、数据存储和基本加工。
2、常用的加工逻辑描述方法有结构化语言、判定表和判定树3种。
6.3 结构化设计方法
1、结构化设计方法中用结构图(Structure Chart)来描述软件系统的体系结构，指出一个软件系统由哪些模块组成，以及模块之间的调用关系。模块结构图是结构化设计的工具，由模块、调用、数据、控制和转接五种基本符号组成。
2、结构化设计主要包括
①体系结构设计：定义软件的主要结构元素及其关系。
②数据设计：基于实体联系图确定软件涉及的文件系统的结构及数据库的表结构。
③接口设计：描述用户界面，软件和其他硬件设备、其他软件系统及使用人员的外部接口，以及各种构件之间的内部接口。
④过程设计：确定软件各个组成部分内的算法及内部数据结构，并选定某种过程的表达形式来描述各种算法。
6.4 WebApp分析与设计
一、WebApp的特性
1、网络密集性：WebApp 驻留在网络上，服务于不同客户全体的需求。
2、并发性：大量用户可能同时访问WebApp。
3、无法预知的负载量：WebApp的用户数量每天都可能有数量级的变化。
4、性能：如果一位WebApp用户必须等待很长时间，该用户就可能转向其他地方。
5、可用性：对于热门的WebApp，用户通常要求能够24/7/365(全天候)访问。
6、数据驱动：许多WebApp的主要功能是使用超媒体向最终用户提供文本、 图片、音频及视频内容。除此之外，WebApp还常被用来访问那些存储在Web 应用环境之外的数据库中的信息。
二、WebApp需求模型
1、内容模型：给出由WebApp提供的全部系列内容，包括文字、图形、图像、 音频和视频。包含结构元素，为WebApp的内容需求提供了一个重要的视图。这些结构元素包含内容对象和所有分析类，在用户与WebApp交互时生成并操作用户可见的实体。
2、交互模型：描述了用户与WebApp采用了哪种交互方式。由一种或多种元素构成，包括用例、顺序图、状态图、用户界面原型等。
3、功能模型：许多WebApp提供大量的计算和操作功能，这些功能与内容直接相关(既能使用又能生成内容，如统计报表)。这些功能常常以用户的交互活动为主要目标。功能模型定义了将用于WebApp内容并描述其他处理功能的操作，这些处理功能不依赖于内容却是最终用户所必需的。
4、导航模型：为WebApp定义所有导航策略。考虑了每一类用户如何从一个WebApp元素(如内容对象)导航到另一个元素。
5、配置模型：描述WebApp所在的环境和基础设施。在必需考虑复杂配置体系结构的情况下，可以使用UML部署图。
第7章 面向对象技术
7.1 面向对象基础
一、面向对象的基本概念
1、对象：由数据及其操作所构成的封装体，是系统中用来描述客观事务的一个实体，是构成系统的一个基本单位。一个对象通常可以由对象名、属性和方法3个部分组成。
2、类：现实世界中实体的形式化描述，类将该实体的属性(数据)和操作(函数)封装在一起。（1）对象是类的实例，类是对象的模板。
（2）类可以分为三种：实体类、接口类、控制类。
3、抽象：通过特定的实例抽取共同特征以后形成概念的过程。它强调主要特征，忽略次要特征。
4、封装：是一种信息隐蔽技术，将相关的概念组成一个单元模块，并通过一个名称来引用。
面向对象封装是将数据和基于数据的操作封装成一个整体对象，对数据的访问或修改只能通过对象对外提供的接口进行。
5、继承：表示类之间的层次关系(父类与子类)，这种关系使得某类对象可以继承另外一类对象的特征，又可分为单继承和多继承。
6、多态：不同的对象收到同一个消息时产生完全不同的结果。包括参数多态(不同类型参数多种结构类型)、包含多态(父子类型关系)、过载多态(类似于重载，一个名字不同含义)、强制多态(强制类型转换)四种类型。多态由继承机制支持，将通用消息放在抽象层，具体不同的功能实现放在低层。
二、 面向对象设计
1、面向对象的设计：是设计分析模型和实现相应源代码，设计问题域的解决方案，与技术相关。OOD 同样应遵循抽象、信息隐蔽、功能独立、模块化等设计准则。
2、面向对象的设计原则：
（1）单一责任原则。
（2）开放一封闭原则。
（3）里氏替换原则。
（4）依赖倒置原则。
（5）接口分离原则。
7.2 UML
一、关系
1、依赖：一个事物的语义依赖于另一个事物的语义的变化而变化。
2、关联：是一种结构关系，描述了一组链，链是对象之间的连接。分为组合和聚合，都是部分和整体的关系，其中组合事物之间关系更强。两个类之间的关联，实际上是两个类所扮演角色的关联，因此，两个类之间可以有多个由不同角色标识的关联。
3、泛化：一般/特殊的关系，子类和父类之间的关系。
4、实现：一个类元指定了另一个类元保证执行的契约。
二、UML中的图
1、类图：静态图，为系统的静态设计视图，展现一组对象、接口、协作和它们之间的关系。
2、对象图：静态图，展现某一时刻一组对象及它们之间的关系，为类图的某一快照。在没有类图的前提下，对象图就是静态设计视图。
3、用例图：静态图，展现了一组用例、参与者以及它们之间的关系。用例图中的参与者是人、硬件或其他系统可以扮演的角色；用例是参与者完成的一系列操作，用例之间的关系有扩展、包含、泛化。
4、序列图：即顺序图，动态图，是场景的图形化表示，描述了以时间顺序组织的对象之间的交互活动。有同步消息，异步消息、返回消息三种。
7.3 设计模式
一、创建型设计模式
| 创建型设计模式 | 记忆关键字 |
| Abstract Factory 抽象工厂模式 | 抽象接口 |
| Builder 构建器模式 | 类和构造分离 |
| Factory Method 工厂方法模式 | 子类决定实例化 |
| Prototype 原型模式 | 原型实例，拷贝 |
| Singleton 单例模式 | 唯一实例 |
二、结构型设计模式
| 结构型设计模式 | 记忆关键字 |
| Adapter 适配器模式 | 转换，兼容接口 |
| Bridge 桥接模式 | 抽象和实现分离 |
| Composite 组合模式 | 整体-部分，树形结构 |
| Decorator 装饰模式 | 附加职责 |
| Facade 外观模式 | 对外统一接口 |
| Flyweight 享元模式 | 细粒度，共享 |
| Proxy 代理模式 | 代理控制 |
三、行为设计模式
| 行为型设计模式 | 记忆关键字 |
| Chain of Responsibility 职责链模式 | 传递请求、职责、链接 |
| Command 命令模式 | 日志记录、可撤销 |
| Interpreter 解释器模式 | 解释器，虚拟机 |
| Lterator 迭代器模式 | 顺序访问，不暴露内部 |
| Mediator 中介者模式 | 不直接引用 |
| Memento 备忘录模式 | 保存，恢复 |
| Observer 观察者模式 | 通知、自动更新 |
| State 状态模式 | 状态变成类 |
| Strategy 策略模式 | 算法替换 |
| Template Method 模板方法模式 | |
| Visitor 访问者模式 | 数据和操作分离 |
第8章 算法设计与分析
8.1 算法设计与分析的基本概念
一、算法的特性
5个重要特性：有穷性、确定性、可行性、输入、输出。
二、算法的复杂度
1、算法的时间复杂度分析：主要是分析算法的运行时间，即算法执行所需要的基本操作数。不同规模的输入所需要的基本操作数是不相同。在算法分析中，可以建立以输入规模n为自变量的函数T(n)来表示算法的时间复杂度。
2、即使对于相同的输入规模，数据分布不相同也影响了算法执行路径的不同，因此所需要的执行时间也不同。根据不同的输入，将算法的时间复杂度分析分为3 种情况：最佳情况、最坏情况、平均情况。
3、渐进符号：以输入规模n为自变量建立的时间复杂度实际上还是较复杂的。
例如an2+bn+c，不仅与输入规模有关，还与系数a、b和c有关。下面简单介绍3种常用的标准方法来简化算法的渐进分析。
（1）O记号：O(g(n))表示一个函数集合，往往用该记号给出一个算法运行时间的渐进上界。
（2）Ω记号：Ω(g(n))表示一个函数集合，往往用该记号给出一个算法运行时间的渐进下界。
（3）Θ记号：Θ(g(n))表示一个函数集合，往往用该记号给出一个算法运行时间的渐进上界和渐进下界，即渐进紧致界。
三、递归
1、阶乘函数
（1）可递归地定义为：
（2）阶乘函数的自变量n的定义域是非负整数。
①递归式的第一式给出了这个函数的一个初始值，是递归的边界条件。
②递归式的第二式是用较小自变量的函数值来表示较大自变量的函数值的方式来定义n的阶乘，是递归体。
（3）n!可以递归地计算如下：
int Factorial(int num){
f(num==0)
return1；
f(num>0)
return num* Factorial(num -1)；
}
2、递归算法的时间复杂度分析方法：将递归式中等式右边的项根据递归式进行替换，称为展开。展开后的项被再次展开，如此下去，直到得到一个求和表达式，得到结果。
8.3 分治法
1、概念：对于一个规模为n的问题，若该问题可以容易地解决则直接解决；否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解决这些子问题，然后将各子问题的解合并得到原问题的解。
2、步骤：分解、求解、合并。
3、凡是涉及到分组解决的都是分治法。
8.4 动态规划法
1、动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
2、动态规划算法常用于求解具有某种最优性质的问题。
3、动态规划法的基本思路：不同子问题的数目常常只有多项式量级。如果能够保存已解决的子问题的答案，在需要时再找出已求得的答案，这样就可以避免大量的重复计算，从而得到多项式时间的算法。为了达到这个目的，可以用一个表来记录所有已解决的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。
4、对于一个给定的问题，若其具有以下两个性质，可以考虑用动态规划法来求解。
（1）最优子结构：如果一个问题的最优解中包含了其子问题的最优，也就是说该问题具有最优子结构。当一个问题具有最优子结构时，提示我们动态规划法可能会适用，但是此时贪心策略可能也是适用的。
（2）重叠子问题：重叠子问题指用来解原问题的递归算法可反复地解同样的子问题，而不是总在产生新的子问题。即当一个递归算法不断地调用同一个问题时，就说该问题包含重叠子问题。
8.5 贪心法
1、贪心法在解决问题的策略上是仅根据当前已有的信息做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。
2、贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。
3、贪心法问题一般具有两个重要的性质。
（1）最优子结构：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。问题具有最优子结构是该问题可以采用动态规划法或者贪心法求解的关键性质。
（2）贪心选择性质：指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。这是贪心法和动态规划法的主要区别。证明一个问题具有贪心选择性质也是贪心法的一个难点。
8.6 回溯法
1、概念：有“通用的解题法”之称，可以系统地搜索一个问题的所有解或任一解。在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。
2、一般用于解决迷宫类的问题。
8.7 分支限界法
1、原理：在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
8.8 概率算法
1、原理：在算法执行某些步骤时，可以随机地选择下一步该如何进行，同时允许结果以较小的概率出现错误，并以此为代价，获得算法运行时间的大幅度减少(降低算法复杂度)。
2、基本特征：对所求解问题的同一实例用同一概率算法求解两次，可能得到完全不同的效果。
8.9 近似算法
1、原理：解决难解问题的一种有效策略，其基本思想是放弃求最优解，而用近似最优解代替最优解，以换取算法设计上的简化和时间复杂度的降低。
2、虽然它可能找不到一个最优解，但它总会给待求解的问题提供一个解。
8.10 数据挖掘算法
1、数据分类的两个步骤：
①学习模型(基于训练数据集采用分类算法建立学习模型)；
②应用模型(应用测试数据集的数据到学习模型中，根据输出来评估模型的好坏以及将未知数据输入到学习模型中，预测数据的类型)。
8.11 智能优化算法
1、人工神经网络ANN：一个以有向图为拓扑结构的动态系统，通过对连续或断续的输入作状态响应而进行信息处理。从信息处理角度对人脑神经元网络进行抽象，建立某种简单模型，按不同的连接方式组成不同的网络。
2、遗传算法：源于模拟达尔文的“优胜劣汰、适者生存”的进化论和孟德尔.摩根的遗传变异理论，在迭代过程中保持已有的结构，同时寻找更好的结构。其本意是在人工适应系统中设计一种基于自然的演化机制。
3、蚁群算法
（1）是一种用来寻找优化路径的概率型算法。
（2）单个蚂蚁的行为比较简单，但是蚁群整体却可以体现一些智能的行为。例如蚁群可以在不同的环境下，寻找最短到达食物源的路径。这是因为蚁群内的蚂蚁可以通过某种信息机制实现信息的传递。后又经进一步研究发现，蚂蚁会在其经过的路径上释放一种可以称之为“信息素”的物质，蚁群内的蚂蚁对“信息素”具有感知能力，它们会沿着“信息素”浓度较高路径行走，而每只路过的蚂蚁都会在路上留下“信息素”，这就形成一种类似正反馈的机制，这样经过一段时间后，整个蚁群就会沿着最短路径到达食物源了。
（3）用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。
第9章 数据库技术基础
9.1 基本概念
1、模式：又称为概念模式，就是我们通常使用的基本表，根据应用、需求将物理数据划分成一张张表。
2、内模式：管理如何存储物理的数据，对应具体物理存储文件。
3、外模式：对应数据库中的视图这个级别，将表进行一定的处理后再提供给用户使用
4、外模式一模式映像：是表和视图之间的映射，存在于概念级和外部级之间，若表中数据发生了修改，只需要修改此映射，而无需修改应用程序。
5、模式一内模式映像：是表和数据的物理存储之间的映射，存在于概念级和内部级之间，若修改了数据存储方式，只需要修改此映射，而不需要去修改应用程序。
9.2 数据模型
一、数据模型的三要素
（1）数据结构(所研究的对象类型的集合)；
（2）数据操作(对数据库中各种对象的实例允许执行的操作的集合)；
（3）数据的约束条件(一组完整性规则的集合)。
二、 E-R模型
1、在E-R模型中，使用椭圆表示属性(一般没有)、长方形表示实体、菱形表示联系，联系的两端要填写联系类型。
2、实体集：具有相同类型和共享相同属性的实体的集合，如学生、课程。
3、属性：实体所具有的特性。
4、属性分类：简单属性和复合属性；单值属性和多值属性；NUL属性；派生属性。
5、域：属性的取值范围称为该属性的域。
6、码(key)：唯一标识实体的属性集。
7、联系类型：一对一 1：1、一对多 1：N、多对多 M：N。
三、关系模型
E-R模型转换为关系模型：每个实体都对应一个关系模式，联系分为三种：1：1联系中、1：N的联系中、M：N的联系中。
9.3 关系代数
1、并：结果是两张表中所有记录数合并，相同记录只显示一次。
2、交：结果是两张表中相同的记录。
3、差：S1-S2，结果是S1表中有而S2表中没有的那些记录。
9.4 关系数据库 SQL语言简介
一、语法关键字
1、创建表 create table;
2、修改表 alter table;
3、删除表 drop table
4、索引 index，视图 view;
5、数据库查询 select…from…where;
6、分组查询 group by，分组时要注意select后的列名要适应分组，having为分组查询附加条件；
7、字符串匹配 like，%配多个字符串，_匹配任意一个字符串；
8、数据库插入 insert into…values();
9、数据库删除 delete from…where;
10、数据库修改 update…set…where;
11、排序 order by，默认为升序，降序要加关键字DESC。
12、DISTINCT：过滤重复的选项，只保留一条记录。
二、SQL语法原理
1、SELECT之后的为要查询显示的属性列名
2、FROM后面是要查询的表名
3、WHERE后面是查询条件
4、涉及到平均数、最大值、求和等运算，必须要分组
5、group by后面是分组的属性列名
6、分组的条件使用Having 关键字，后面跟条件。
7、在 SQL语句中，条件判断时数字无需打引号，字符串要打单引号。
9.5 关系数据库的规范化
一、函数依赖
1、函数依赖的公理系统(Armstrong)
设关系模式R<U，F>，U是关系模式R的属性全集，F是关系模式R的一个函数依赖集。对于R<U，F>来说有以下的：
二、键与约束
1、键
（1）超键：能唯一标识此表的属性的组合。
（2）候选键：超键中去掉冗余的属性，剩余的属性就是候选键。
（3）主键：任选一个候选键，即可作为主键。
（4）外键：其他表中的主键。
（5）主属性：候选键内的属性为主属性，其他属性为非主属性。
2、约束
（1）实体完整性约束：即主键约束，主键值不能为空，也不能重复。
（2）参照完整性约束：即外键约束，外键必须是其他表中已经存在的主键的值，或者为空。
（3）用户自定义完整性约束：自定义表达式约束，如设定年龄属性的值必须在0到150之间。
三、模式分解及分解应具有的特性
1、保持函数依赖分解
对于关系模式R，有依赖集F，若对R进行分解，分解出来的多个关系模式，保持原来的依赖集不变，则为保持函数依赖的分解。另外，注意要消除掉冗余依赖(如传递依赖)。
2、无损分解：分解后的关系模式能够还原出原关系模式，就是无损分解，不能还原就是有损。
9.6 数据库的控制功能
一、事务管理
1、事务的 ACID性质
（1）(操作)原子性。
（2）(数据)一致性。
（3）(执行)隔离性。
（4）(改变)持续性。
二、封锁协议
1、X锁是排它锁(写锁)。若事务T对数据对象A加上X锁，则只允许T读取和修改A，其他事务都不能再对A加任何类型的锁，直到T释放A上的锁。
2、S锁是共享锁(读锁)。若事务T对数据对象A加上S锁，则只允许T读取A，但不能修改A，其他事务只能再对A加S锁(也即能读不能修改)，直到T释放A上的S锁。
3、共分为三级封锁协议，如下：
（1）一级封锁协议：可解决丢失更新问题。
（2）二级封锁协议：可解决丢失更新、读脏数据问题。
（3）三级封锁协议：可解决丢失更新、读脏数据、数据重复读问题。
第10章 网络与信息安全基础知识
10.2 网络互连硬件
1、异步传输：发送方每发送一个字符，需要约定一个起始位和停止位插入到字符的起始和结尾处，这样当接收方接收到该字符时能够识别，但是这样会造成资源浪费，传输效率降低。
2、同步传输：以数据块为单位进行传输，当发送方要发送数据时，先发送一个同步帧，接收方收到后做好接收准备，开始接收数据块，结束后又会有结束帧确认，这样一次传输一个数据块，效率高。
3、交换方式
（1）电路交换：通信一方进行呼叫，另一方接收后，在二者之间会建立一个专用电路，特点为面向连接、实时性高、链路利用率低，一般用于语音视频通信。
（2）报文交换：以报文为单位，存储转发模式，接收到数据后先存储，进行差错校验，没有错误则转发，有错误则丢弃，因此会有延时，但可靠性高，是面向无连接的。
（3）分组交换：以分组为单位，也是存储转发模式，因为分组的长度比报文小，所以时延小于报文交换，又可分为三种方式：
①数据报：是现在主流的交换方式，各个分组携带地址信息，自由的选择不同的路由路径传送到接收方，接收方接收到分组后再根据地址信息重新组装成原数据，是面向无连接的，但是不可靠的。
②虚电路：发送方发送一个分组，接收方收到后二者之间就建立了一个虚拟的通信线路，二者之间的分组数据交互都通过这条线路传送，在空闲的时候这条线路也可以传输其他数据，是面向连接的，可靠的。
③信元交换：异步传输模式ATM采用的交换方式，本质是按照虚电路方式进行转发，只不过信元是固定长度的分组，共53B，其中5B为头部，48B为数据域，也是面向连接的，可靠的。
10.3 网络的协议与标准
1、IP：网络层最重要的核心协议，在源地址和目的地址之间传送数据报，无连接、不可靠。
2、ARP和RARP：地址解析协议，ARP是将IP地址转换为物理地址，RARP是将物理地址转换为IP地址。
3、TCP：整个TCP/IP协议族中最重要的协议之一，在IP协议提供的不可靠数据数据基础上，采用了重发技术，为应用程序提供了一个可靠的、面向连接的、全双工的数据传输服务。一般用于传输数据量比较少，且对可靠性要求高的场合。
4、UDP：是一种不可靠、无连接的协议，有助于提高传输速率，一般用于传输数据量大，对可靠性要求不高，但要求速度快的场合。
10.4 Intemet 及应用
1、一般的IP地址按标准划分为A、B、C类后，可以进行再一步的划分，将主机号拿出几位作为子网号，就可以划分出多个子网，此时IP地址组成为：网络号+子网号+主机号。
2、网络号和子网号都为1，主机号都为0。这样的地址为子网掩码。
3、子网号可以为全0和全1，主机号不能为全0或全1，因此，主机数需要-2，而子网数不用。
10.5 信息安全基础知识
1、“安全空间”的五大属性：认证、权限、完整、加密和不可否认。
2、信息安全属性：保密性、完整性、可用性、真实性、可核查性、不可抵赖性、可靠性。
3、安全需求：物理线路安全、网络安全、系统安全、应用安全。
10.6 网络安全概述
1、入侵检测系统IDS
（1）原理：监控当前系统/用户行为，使用入侵检测分析引擎进行分析，这里包含一个知识库系统，囊括了历史行为、特定行为模式等操作，将当前行为和知识库进行匹配，就能检测出当前行为是否是入侵行为，如果是入侵，则记录证据并上报给系统和防火墙，交由它们处理。
（2）IDS入侵检测系统是一个监听设备，没有跨接在任何链路上，无须网络流量流经它便可以工作。一般是采用旁路挂接的方式，连接在网络中。
2、入侵防御系统IPS
（1）IPS是能够提前发现入侵行为，在其还没有进入安全网络之前就防御。
（2）与IDS的区别：在安全网络之前的链路上挂载入侵防御系统IPS，可以实时检测入侵行为，并直接进行阻断。
3、蜜罐系统：伪造一个蜜罐网络引诱黑客攻击，蜜罐网络被攻击不影响安全网络，并且可以借此了解黑客攻击的手段和原理，从而对安全系统进行升级和优化。
第11章 标准化和软件知识产权基础知识
11.2 知识产权基础知识
1、知识产权
（1）指公民、法人、非法人单位对自己的创造性智力成果和其他科技成果依法享有的民事权。包含著作权、专利权、商标权、商业秘密权、植物新品种权、集成电路布图设计权和地理标志权等。
2、中国公民、法人或者其他组织的作品，不论是否发表，都享有著作权。开发软件所用的思想、处理过程、操作方法或者数学概念不受保护。
3、侵权判定
| 不侵权 | 侵权 |
| ✔个人学习、研究或者欣赏； ✔适当引用： ✔公开演讲内容 ✔用于教学或科学研究 ✔复制馆藏作品 ✔免费表演他人作品； ✔室外公共场所艺术品临摹、绘画、摄影、录像； ✔将汉语作品译成少数民族语言作品或盲文出版。 | ✘未经许可，发表他人作品： ✘未经合作作者许可，将与他人合作创 作的作品当作自己单独创作的作品发表的； ✘未参加创作，在他人作品署名； ✘歪曲、篡改他人作品的； ✘剽窃他人作品的； 使用他人作品，未付报酬； ✘未经出版者许可，使用其出版的图书、期刊的版式设计的。 |