作者前言

• 因为第五版的基本都是PDF的，没法复制和搜索作者不方便写笔记。而各大商城的都只有第三版的，所以参考了不少第三版的

1、计算机系统知识

1.1、计算机系统基础知识

1.1.1　计算机系统硬件基本组成

• 计算机的基本硬件系统由运算器、控制器、存储器、输入设备和输出设备5大部件组成。
• 运算器、控制器等部件被集成在一起统称为中央处理元（Central Processing Unit, CPU）。

1.1.2　中央处理单元

• CPU的功能：程序控制、操作控制、时间控制、数据处理。
• CPU的组成：运算器、控制器、寄存器和内部总线，其中控制器不仅要保证程序的正确执行，而且要能够处理异常事件。
  
• 运算器

算术逻辑单元：ALU是运算器的重要组成部件，负责处理数据，实现对数据的算术运算和逻辑运算。
累加寄存器（AC）：AC通常简称为累加器，它是一个通用寄存器。
数据缓冲寄存器（DR）：在对内存储器进行读写操作时，用DR暂时存放由内存储器读写的一条指令或一个数据字，将不同时间段内读写的数据隔离开来。
状态条件寄存器（PSW）：PSW保存由算术指令和逻辑指令运行或测试的结果建立的各种条件码内容，

• 控制器

指令寄存器（IR）：当CPU执行一条指令时，先把它从内存储器取到缓冲寄存器中，再送入IR暂存，指令译码器根据IR的内容产生各种微操作指令，控制其他的组成部件工作，完成所需的功能。
程序计数器（PC）：PC具有寄存信息和计数两种功能，又称为指令计数器。程序的执行分两种情况，一是顺序执行，二是转移执行。
地址寄存器（AR）：AR保存当前CPU所访问的内存单元的地址。
指令译码器（ID）：指令分为操作码和地址码两部分，为了能执行任何给定的指令，必须对操作码进行分析，以便识别所完成的操作。

• 寄存器组

1.1.3、数据表示

原码、反码、补码和移码（符号数）

• 原码：正数的原码等于自身的二进制数，负数的原码第一位为1(符号位，表示负数)，后面为自身的二进制数
• 反码：正数的反码等于自身的二进制数，负数的反码符号位不动，其余各位按位取反
• 补码：正数的补码等于自身的二进制数，负数的补码是在反码的基础上+1
• 移码(增码)：无论正负数，只要将其补码的符号位取反即可

符号数的应用

• 补码：在计算机中最适合数字加减运算的数字编码。补码运算的结果就是该结果的补码值，不用经过处理。
• 移码：最适合表示浮点数阶码的数字编码，移码的比较最为简单，不用考虑符号。

定点数和浮点数

• 所谓定点数，就是小数点的位置固定不变的数。小数点的位置通常有两种约定形式：定点整数（纯整数，小数点在最低有效数值位之后）和定点小数（纯小数，小数点在最高有效数值位之前）。
  
• 浮点数：定点数能表示的范围太小，所以使用浮点数。

阶码：通常为带符号的纯整数，使用移码，阶码决定数值范围。
尾数：通常为带符号的纯小数，使用补码，尾数决定精度。
浮点数的值=尾数值*2^阶码值
浮点数的运算：先对阶，再求尾数和。对阶方式，阶码较小的值变阶码较大的值，同时尾数变小。
阶码使用移码的原因：简化比较操作，可以直接按照无符号整数的方式进行比较，而无需考虑符号位。
尾数使用补码的原因：方便加减运算，补码在计算机中最适合数字加减运算的数字编码

1.1.4、校验码

奇偶校验

• 奇校验：将信息数据的各位进行模二加法并作为校验码的称为奇校验。
• 偶校验：将信息数据的各位进行模二加法并取反作为校验码的称为偶校验。

循环冗余校验码

• 检错能力非常强，但是不能纠错。编码长度(CRC字长)为数据位+校验位

海明码

• 采用多位校验码的方式，可以发现、纠正错误。数据位和校验位必须满足关系式：2^校验位-1≥数据位+校验位。码距至少是3。

1.2、计算机体系结构

1.2.1、计算机体系结构的发展

计算机系统结构概述

• 计算机体系结构（computer architecture）是指计算机的概念性结构和功能属性。
• 计算机组织（computer organization）是指计算机体系结构的逻辑实现，包括机器内的数据流和控制流的组成以及逻辑设计等（常称为计算机组成原理）。
• 计算机实现（computer implementation）是指计算机组织的物理实现。

计算机体系结构分类

• 宏观上按处理机的数量进行分类，分为单处理系统、并行处理与多处理系统和分布式处理系统。
• 微观上按并行程度分类，有Flynn分类法、冯泽云分类法、Handler分类法和Kuck分类法。

指令系统

• CISC（Complex Instruction Set Computer，复杂指令集计算机）的基本思想是：进一步增强原有指令的功能，用更为复杂的新指令取代原先由软件子程序完成的功能，实现软件功能的硬化，导致机器的指令系统越来越庞大而复杂。事实上，目前使用的绝大多数计算机都属于CISC类型。
• RISC（Reduced Instruction Set Computer，精简指令集计算机）的基本思想是：通过减少指令总数和简化指令功能，降低硬件设计的复杂度，使指令能单周期执行，并通过优化编译，提高指令的执行速度，采用硬线控制逻辑，优化编译程序。在20世纪70年代末开始兴起，导致机器的指令系统进一步精炼而简单。
• 指令控制方式有顺序方式、重叠方式和流水方式三种。
• 吞吐率：执行完成的任务数/执行时间（单个单位时间执行完成的任务数）
• 流水线最大吞吐率：1/△t，△t为为最长子过程的时间
• 流水建立时间：若m个子过程所用时间一样，均为∆t0，则建立时间T0＝m∆t0。
• 寻址类型

  立即寻址：操作数包含在指令中，获取操作数是最快的
  直接寻址：操作数的地址在指令中
  寄存器寻址：操作数在寄存器中
  寄存器间接寻址：操作数的地址在寄存器中
  

1.2.2、存储系统

存储器的层次结构

• 三层存储器结构：高速缓存（Cache）、主存储器（Main memory, MM）和辅助存储器（外存储器）
  

存储器的分类

• 按位置分类：内存（主存）、外存（辅存）
• 按材料分类：磁存储器、半导体存储器、光存储器
• 按工作方式分类：读写存储器、只读存储器
• 按访问方式分类：按地址访问的存储器、按内容访问的存储器（相联存储器）
• 按寻址方式分类：随机存储器、顺序存储器、直接存储器

相联存储器

• 相联存储器可用在高速缓冲存储器中；在虚拟存储器中用来作段表、页表或快表存储器；用在数据库和知识库中。
• 相联存储器是一种按内容访问的存储器。其工作原理就是把数据或数据的某一部分作为关键字，将该关键字与存储器中的每一单元进行比较，找出存储器中所有与关键字相同的数据字。

高速缓存

高速缓存的组成

• 高速缓存的组成：控制部分和Cache存储器部分。
  

高速缓存中的地址映像方法

• 直接映像：直接映像是指主存的块与Cache中块的对应关系是固定的。
  
• 全相联映像：主存与Cache存储器均分成容量相同的块。这种映像方式允许主存的任一块可以调入Cache存储器的任何一个块的空间中。
  
• 组相联映像：这种方式是前面两种方式的折衷。具体做法是将Cache中的块再分成组。例如，假定Cache有16块，再将每两块分为1组，则Cache就分为8组。主存同样分区，每区16块，再将每两块分为1组，则每区就分为8组。

替换算法

• 随机替换算法。就是用随机数发生器产生一个要替换的块号，将该块替换出去。
• 先进先出算法。就是将最先进入Cache的信息块替换出去。
• 近期最少使用算法。这种方法是将近期最少使用的Cache中的信息块替换出去。
• 优化替换算法。这种方法必须先执行一次程序，统计Cache的替换情况。有了这样的先验信息，在第二次执行该程序时便可以用最有效的方式来替换。

Cache的性能分析

• 设Hc为Cache的命中率，tc为Cache的存取时间，tm为主存的访问时间。
• Cache访问和主存访问是同时启动的：Cache存储器的平均访问时间为ta为。

  访问流程：CPU发出访问请求时，同时向Cache和主存发送请求。如果Cache命中，主存访问可以被取消或者不必等待其完成；如果不命中，CPU直接等待主存的响应。
  

• 如果在Cache不命中时才启动主存，则
  

  访问流程：CPU首先尝试从Cache中读取数据。如果命中，直接从Cache获取数据。如果不命中，此时才开始启动对主存的访问请求。
  

多级Cache

• 在多级Cache的计算机中，Cache分为一级（L1 Cache）、二级（L2 Cache）等，CPU访存时首先查找L1 Cache，如果不命中，则访问L2 Cache，直到所有级别的Cache都不命中，才访问主存。目前，CPU内的Cache通常为二级结构。通常要求L1 Cache的速度足够快，以赶上CPU的主频。L1 Cache的容量一般都比较小，为几千字节到几十千字节；L2 Cache则具有较高的容量，一般为几百字节到几兆字节，以具有足够高的命中率。

虚拟存储器

• 虚拟存储（virtual memory）技术的概念是：把很大的程序（数据）分成许多较小的块，全部存储在辅存中。
• 页式虚拟存储器：以页为信息传送单位的虚拟存储器。通常一页为几百字节到几千字节。
• 段式虚拟存储器：以程序的逻辑结构形成的段（如某一独立程序模块、子程序等）作为主存分配依据的一种段式虚拟存储器的管理方法。
• 段页式虚拟存储器：是页式虚拟存储器和段式虚拟存储器两者相结合的一种管理方式。

外存储器

• 磁盘存储器：在磁表面存储器中，磁盘的存取速度较快，且具有较大的存储容量，是目前广泛使用的外存储器。
• 磁盘容量有两种指标：一种是非格式化容量，它是指一个磁盘所能存储的总位数；另一种是格式化容量，它是指各扇区中数据区容量总和。计算公式分别如下：
  非格式化容量＝面数×（磁道数／面）×内圆周长×最大位密度
  格式化容量＝面数×（磁道数／面）×（扇区数／道）×（字节数／扇区）
• 光盘存储器：光盘存储器是一种采用聚焦激光束在盘式介质上非接触地记录高密度信息的新型存储装置。根据性能和用途，可分为只读型光盘（CD-ROM）、只写一次型光盘（WORM）和可擦除型光盘。

1.2.3、输入输出技术

• 直接程序控制：在完成外设数据的输入输出中，整个输入输出过程是在CPU执行程序的控制下完成的。这种方式分为无条件传送和程序查询方式两种情况。
• 直接内存存取（Direct Memory Access, DMA）：是指数据在内存与I/O设备间的直接成块传送，即在内存与I/O设备间传送一个数据块的过程中，不需要CPU的任何干涉，只需要CPU在过程开始启动（即向设备发出“传送一块数据”的命令）与过程结束（CPU通过轮询或中断得知过程是否结束和下次操作是否准备就绪）时的处理，实际操作由DMA硬件直接执行完成，CPU在此传送过程中可做别的事情。

1.2.4、总线结构

• 总线的定义与分类：内部总线、系统总线、外部总线。

1.3　安全性、可靠性与系统性能评测基础知识

1.3.1　计算机安全概述

• 信息安全的5个基本要素：机密性、完整性、可用性、可控性和可审查性。
• 计算机系统中的三类安全性是指：技术安全性、管理安全性和政策法律安全性。

1.3.2　加密技术和认证技术

• 对称加密技术：加密系统的加密密钥和解密密钥相同，或者虽然不同，但从其中的任意一个可以很容易地推导出另一个。
• 对称加密有：DES、3DES（TDES）、IDEA、RC-5
• 非对称加密技术：公钥和私钥是不一样的，公钥对外开放，私钥仅限自己知道
• 非对称加密有：RSA、ECC

1.3.3　计算机可靠性

• 失效率（λ）：是指单位时间内失效的元件数与元件总数的比例
• 平均无故障时间（MTBF）：两次故障之间系统能正常工作的时间的平均值。MTBF=1/λ
• 平均修复时间（MTRF）：表示计算机的可维修性，即计算机的维修效率，指从故障发生到机器修复平均所需要的时间。
• 计算机的可用性（A）：是指计算机的使用效率，它以系统在执行任务的任意时刻能正常工作的概率。A=MTBF/(MTBF+MTRF)
• 串联系统可靠性：R=R1*R2*R3…*Rn
• 串联系统失效率：λ=λ1+λ2+λ3…+λn
• 并联系统可靠性：
  
• 假如所有子系统的失效率均为λ（失效率不同的不做讨论），则系统的失效率μ为：μ=1/(1/λx(1+1/2+1/3+…+1/n))
  

1.3.4、计算机系统的性能评价

• 性能评测的常用方法：时钟频率、指令执行速度、等效指令速度法、数据处理速率法、核心程序法。
• 基准测试程序（Benchmark）：目前一致承认的测试性能的较好方法，有多种多样的基准程序，如主要测试整数性能的基准程序、测试浮点性能的基准程序等。

2、程序设计语言基础知识

2.1、程序语言概述

2.1.1、程序语言的基本概念

• 机器语言和汇编语言为低级语言。机器语言用于机器识别，高级语言用于用户的编程。
• 解释方式下，翻译源程序时不生成独立的目标程序，而编译器则将源程序翻译成独立保存的目标程序。
• 程序设计语言的定义都涉及语法、语义和语用等方面。

2.2.2、编译程序基本原理

编译过程概述

• 词法分析：单个词语是否有错误
  从左到右逐个字符地扫描，从中识别出一个个“单词”符号。“单词”符号是程序设计语言的基本语法单位，如关键字、标识符、常数、运算符和分隔符等。
• 语法分析：单个语句是否有错误
  根据语言的语法规则将单词符号序列分解成各类语法单位，比如表达式、语句和程序等。语法规则就是各类语法单位的构成规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。
• 语义分析：多个语句是否有错误
  检查源程序是否包含静态语义错误，并收集类型信息供后面的代码生成阶段使用。只有语法和语义都正确的源程序才能被翻译成正确的目标代码。语义分析的一个主要工作是进行类型分析和检查。程序语言中的一个数据类型一般包含两个方面的内容：类型的载体及其上的运算。例如：整除取余运算只能对整型数据进行运算，若其运算对象中有浮点数就认为是类型不匹配的错误。静态的语义错误是指编译程序可以发现，动态的语义错误是指源程序虽然能够被编译和执行，但是结果不对，一般是逻辑上的错误。
• 编译过程中，对高级语言程序语句的翻译主要考虑声明语句和可执行语句、对声明语句，主要是将需要的信息正确地填入合理组织的符号表中；对可执行语句，则是转换成中间代码和目标代码。

文法和语言的形式描述

终结符和非终结符

• 文法格式通常为：ɑ→β，若字符为大写字母，则是非终结符，若字符为小写字母，则是终结符

文法的分类

0型文法(短语文法)

设G=（VN，VT，P，S），如果它的每个产生式α→β是这样一种结构：α∈(VN∪VT)且至少含有一个非终结符，而β∈(VN∪VT)，则G是 一个0型文法。一个非常重要的理论结果是：0型文法的能力相当于图灵机(Turing)。或者说，任何0型文语言都是递归可枚举的，反之，递归可枚举集必定是一个0型语言。0型文法是这几类文法中，限制最少的一个，所以我们在试题中见到的,至少是0型文法。

1型文法(上下文有关文法)

此文法对应于线性有界自动机。它是在0型文法的基础上每一个α→β,都有|β|>=|α|。这里的|β|表示的是β的长度。

注意：虽然要求|β|>=|α|，但有一特例：α→ε也满足1型文法。

如有A->Ba则|β|=2,|α|=1符合1型文法要求。反之,如aA->a，则不符合1型文法。

2型文法(上下文无关文法)

此文法对应于下推自动机。2型文法是在1型文法的基础上,再满足：每一个α→β都有α是非终结符。如A->Ba,符合2型文法要求。大多数程序设计语言的语法规则可以用上下文无关文法描述

如Ab->Bab虽然符合1型文法要求,但不符合2型文法要求，因为其α=Ab，而Ab不是一个非终结符。

3型文法(正规文法)

此文法对应于有限状态自动机。它是在2型文法的基础上满足:A→α|αB（右线性）或A→α|Bα（左线性）。

如有：A->a,A->aB,B->a,B->cB，则符合3型文法的要求。但如果推导 为:A->ab,A->aB,B->a,B->cB或推导 为:A->a,A->Ba,B->a,B->cB则不符合3型方法的要求了。具体的说，例子 A->ab,A->aB,B->a,B->cB中的A->ab不符合3型文法的定义,如果把后面的ab,改成“一个非终结 符＋一个终结符”的形式（即为aB）就对了。例子A->a,A->Ba,B->a,B->cB中如果把B->cB改为 B->Bc的形式就对了,因为A→α|αB（右线性）和A→α|Bα（左线性）两套规则不能同时出现在一个语法中,只能完全满足其中的一个,才能算 3型文法。

词法分析

• 有限自动机DFA 、 无限自动机NFA
• 状态转换图是一个有向图，简称转换图。例如：（s0为初态、s3为终态），s3用两个圆圈表示
  

语法制导翻译和中间代码生成

• 静态语义分析方法是语法制导翻译，其基本思想是将语言结构的语义以属性的形式赋予代表此结构的文法符号，而属性的计算以语义规则的形式赋予文法的产生式。
• 中间代码：常用的中间代码有后缀式（逆波兰式）、三元式、四元式和树等形式。

中间代码优化和目标代码生成

• 优化就是对程序进行等价变换，使得从变换后的程序能生成更有效的目标代码。

  等价：不改变程序的运行结果；
  有效：目标代码运行时间较短，占用的存储空间较少
  

• 目标代码的生成由代码生成器实现。代码生成器以经过语义分析或优化后的中间代码为输入，以特定的机器语言或汇编代码为输出。
• 代码生成所需考虑的主要问题有：中间代码形式、目标代码形式、寄存器的分配、计算次序的选择。

2.2.3、解释程序基本原理

解释程序的基本结构

• 两部分：分析部分、解释部分
• 分析部分：词法、语法和语义分析
• 解释部分：用来对第一部分产生的中间代码进行解释执行。

高级语言编译与解释方式的比较

• 效率：解释运行效率小于编译。
• 灵活性：解释方式能够比编译方式更灵活。
• 可移植性：解释器一般也是用某种程序设计语言编写的，因此只要对解释器进行重新编译，就可以使解释器运行在不同的环境中。
• 编译比解释多了代码优化、目标代码生成两个过程。

3、数据结构

3.1、线性结构

3.1.1、线性表

• 线性表的定义

一个线性表是 n(n>0)个元素的有限序列，通常表示为(a,a,,…,an)。非空线性表的特点如下。
(1)存在唯一的一个称作“第一个”的元素。
(2)存在唯一的一个称作“最后一个”的元素。
(3)除第一个元素外，序列中的每个元素均只有一个直接前驱。
(4)除最后一个元素外，序列中的每个元素均只有一个直接后继。

• 线性表的存储结构：顺序存储和链式存储

3.1.2、栈和队列

• 栈和队列是程序中常用的两种数据结构，它们的逻辑结构和线性表相同。其特点在于运算有所限制:栈按“后进先出”的规则进行操作，队列按“先进先出”的规则进行操作，故称为运算受限的线性表。

3.1.3、串

• 串(字符串)是一种特殊的线性表，其数据元素为字符。计算机中非数值问题处理的对象经常是字符串数据，例如，在汇编和高级语言的编译程序中，源程序和目标程序都是字符串;在事务处理程序中，姓名、地址等一般也是作为字符串处理的。串具有自身的特性，运算时常常把一个串作为一个整体来处理。这里介绍串的定义、基本运算、存储结构及串的模式匹配算法。

3.2、数组、矩阵和广义表

• 数组：n维数组是一种“同构”的数据结构，其每个数据元素类型相同、结构一致。
• 矩阵：假如值相同的元素或0元素在矩阵中的分布有一定的规律，则称此类矩阵为特殊矩阵，否则称其为稀疏矩阵。
• 广义表

  广义表是线性表的推广，是由0个或多个单元素或子表组成的有限序列。
  广义表与线性表的区别在于:线性表的元素都是结构上不可分的单元素，而广义表的元素既可以是单元素，也可以是有结构的表。广义表的特点：
  (1)广义表可以是多层次的结构，因为广义表的元素可以是子表，而子表的元素还可以是子表。
  (2)广义表中的元素可以是已经定义的广义表的名字，所以一个广义表可被其他广义表所共享。
  (3)广义表可以是一个递归的表，即广义表中的元素也可以是本广义表的名字。
  

3.3、树

二叉排序树

• 若它的左子树非空，则左子树上所有节点的值均小于它的根节点的值
• 若它的右子树非空，则右子树上所有结点的值均大于等于它的根节点的值
• 它的左、右子树也分别为二叉排序树。查找的时候，中序遍历二叉树，得到一个递增序列
• 关键字最大的结点可以有左子树，但一定没有右子树

哈夫曼树(最优二叉树)

• 定义：是带权路径(WPL)最短的树，权值越大的叶子节点越靠近根节点。

平衡二叉树

• 平衡二叉树（Baland Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

满二叉树

• 除最后一层无任何子节点外，每一层上的所有结点都有两个子结点或0个子节点的二叉树。

3.4、图

• 图是比树结构更复杂的一种数据结构。在线性结构中，除首结点没有前驱、末尾结点没有后继外，一个结点只有唯一的一个直接前驱和唯一的一个直接后继。在树结构中，除根结点没有前驱结点外，其余的每个结点只有唯一的一个前驱(双亲)结点和多个后继(子树)结点。而在图中，任意两个结点之间都可能有直接的关系，所以图中一个结点的前驱结点和后继结点的数目是没有限制的。

无向图

• 无向图邻接矩阵：其邻接矩阵第i行元素的和即为顶点i的度,例如：顶点4的度就是第四行的和，即2。
  

有向图

• 其邻接矩阵的第i行元素之和为顶点i的出度，而邻接矩阵的第j列元素之和为顶点j的入度。例如：顶点3的出度和入度分别为5和16.
  

3.5、查找

二分查找法(折半查找法)

• 适用情况：不经常变动而查找频繁的有序列表
• 优点：1、比较次数少，2、查找速度快，3、平均性能好
• 缺点：1、要求待查表为有序表，2、插入删除困难
• 实现算法：首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

分块查找

• 适用情况：节点动态变化的情况
• 优点：比顺序查找算法（就是一个一个的去比较）快得多
• 缺点：速度不如折半查找法
• 实现算法：把一个大的线性表分解成若干块，每块中的节点可以任意存放，但块与块之间必须排序。假设是按关键码值非递减的，那么这种块与块之间必须满足已排序要求，实际上就是对于任意的i，第i块中的所有节点的关键码值都必须小于第i+1块中的所有节点的关键码值。此外，还要建立一个索引表，把每块中的最大关键码值作为索引表的关键码值，按块的顺序存放到一个辅助数组中，显然这个辅助数组是按关键码值费递减排序的。查找时，首先在索引表中进行查找，确定要找的节点所在的块。由于索引表是排序的，因此，对索引表的查找可以采用顺序查找或折半查找；然后，在相应的块中采用顺序查找，即可找到对应的节点。
• 平均查找长度(E(n))：假设某个线性表中共有n个节点，分成大小相等的b块，每块有s=n/b,则
  

3.6、排序

直接插入排序

• 每一趟将一个待排序的记录，按照其关键字的大小插入到有序队列的合适位置里，直到全部插入完成,比如斗地主抽牌就是这样的规则。
  

简单选择排序

• 每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。
  

冒泡排序

• 两两比较待排序的关键字，并交换不满足次序要求的那对数，直到整个表都满足次序要求为止。
  

希尔排序

• 把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。
  

快速排序

• 通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。采用了分治法的算法策略。
  

堆排序

• 堆排序中堆的定义：n个元素的序列{k1，k2，…，kn}当且仅当满足下列关系时，称为堆。
  

归并排序

• 将待排序序列R[0…n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。
• 原理就是：两个有序序列拼接成一个有序序列，只需要序列各扫描一次即可完成。
• 采用分治法的设计策略
  

基数排序

• 基数排序与本系列前面讲解的七种排序方法都不同，它不需要比较关键字的大小。它是根据关键字中各位的值，通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。
• 设有一个初始序列为: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。
• 我们知道，任何一个阿拉伯数，它的各个位数上的基数都是以0~9来表示的。所以我们不妨把0~9视为10个桶。 我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R[0] = 50，个位数上是0，将这个数存入编号为0的桶中。
  
• 分类后，我们在从各个桶中，将这些数按照从编号0到编号9的顺序依次将所有数取出来。这时，得到的序列就是个位数上呈递增趋势的序列。 按照个位数排序： {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。

每个排序的比较

• 从时间复杂度、空间复杂度、稳定性各个维度比较。
  

4、操作系统知识

4.1、操作系统基础知识

• 计算机系统的硬件资源包括中央处理机、存储器（包括主存与外存）和输入输出设备等物理设备；
• 操作系统有如下两个重要的作用：通过资源管理，提高计算机系统的效率；改善人机界面，向用户提供友好的工作环境。
• 操作系统的4个特征：并发性、共享性、虚拟性和不确定性。
• 操作系统的5个功能：处理机管理、文件管理、存储管理、设备管理和作业管理。
• 操作系统的7个类型：批处理操作系统（简称批处理）、分时操作系统、实时操作系统、网络操作系统、分布式操作系统、微机操作系统和嵌入式操作系统。

4.2、处理机管理

4.2.1、基本概念

• 处理机管理也称进程管理。在多道程序批处理系统和分时系统中，有多个并发执行的程序，为了描述系统中程序动态变化的过程引入了进程。
• 进程是资源分配和独立运行的基本单位。
• 处理机管理重点需要研究诸进程之间的并发特性，以及进程之间相互合作与资源竞争产生的问题。
• 前驱图：前趋图是一个有向无循环图，图由节点和节点间的有向边组成，节点代表各程序段的操作，而节点间的有向边表示两程序段操作之间存在的前趋关系（“→”）。
• 进程的组成：进程是程序的一次执行，该程序可以和其他程序并发执行。进程通常是由程序、数据和进程控制块（PCB）组成的。
• 进程的状态及其状态间的切换
• 进程的三态图
  
• 进程的五态图
  

4.2.2、进程的控制

• 进程控制就是对系统中所有进程从创建到消亡的全过程实施有效的控制。为此，操作系统设置了一套控制机构，该机构的主要功能包括创建一个新进程，撤销一个已经运行完的进程，改变进程的状态，实现进程间的通信。进程控制是由操作系统内核（Kernel）中的原语实现的。内核是计算机系统硬件的首次延伸，是基于硬件的第一层软件扩充，它为系统对进程进行控制和管理提供了良好的环境。
• 原语（Primitive）是指由若干条机器指令组成的，用于完成特定功能的程序段。原语的特点是在执行时不能被分割，即原子操作要么都做，要么都不做。

4.2.3、进程间的通信

• 临界区管理的原则：有空即进、无空则等、有限等待、让权等待。
• 信号量机制：S≥0表示某资源的可用数，若S＜0，则其绝对值表示阻塞队列中等待该资源的进程数。
• PV操作：进入临界区时执行P操作（申请），退出临界区时执行V操作（释放）
• P操作的定义：S:＝S－1，若S≥0，则执行P操作的进程继续执行；若S＜0，则置该进程为阻塞状态（因为无可用资源），并将其插入阻塞队列。例子：若当前的信号量为0，进程A进行P操作，运算之后变成-1，判定 -1(S)<0，进程A进入等待。
• V操作定义：S:＝S＋1，若S＞0，则执行V操作的进程继续执行；若S≤0，则从阻塞状态唤醒一个进程，并将其插入就绪队列，然后执行V操作的进程继续。
• 利用PV操作实现进程的互斥：令信号量mutex的初值为1，当进入临界区时执行P操作，退出临界区时执行V操作。
• 利用PV操作实现进程的同步：生产者消费者问题，　一个生产者和一个消费者，缓冲区可存放n件物品。生产者不断地生产产品，消费者不断地消费产品。
• PV操作实现进程间通信缺点：编程难度大，通信对用户不透明，容易出现死锁；效率低，生产者每次只能向缓冲区放一个消息，消费者只能从缓冲区取一个消息。
• 高级通信原语（高级通信方式）：共享存储模式、消息传递模式和管道通信。

4.2.4、管程

• 其基本思路是采用资源集中管理的方法，将系统中的资源用某种数据结构抽象地表示出来。由于临界区是访问共享资源的代码段，建立一个管程管理进程提出的访问请求。

4.2.5、进程调度

• 三级调度：高级调度、中级调度、低级调度
• 调度算法：有先来先服务、时间片轮转、优先级调度和多级反馈调度算法。

3.2.6　死锁

• 所谓死锁，是指两个以上的进程互相都要求对方已经占有的资源导致无法继续运行下去的现象。
• 产生死锁的4个必要条件是互斥条件、请求保持条件、不可剥夺条件和环路条件。
• 死锁的处理策略主要有4种：鸵鸟策略（即不理睬策略）、预防策略、避免策略和检测与解除死锁。
• 银行家算法（预防死锁）：进程发出的每一个系统可以满足的资源请求命令加以检测，如果发现分配资源后，系统进入不安全状态，则不予分配；若分配资源后系统仍处于安全状态，则实施分配。与死锁预防策略相比提高了资源的利用率，但增加了系统开销。

3.2.7　线程

• 引入线程后，将传统进程的两个基本属性分开，线程作为调度和分配的基本单位，进程作为独立分配资源的单位。用户可以通过创建线程来完成任务，以减少程序并发执行时付出的时空开销。
• 线程也具有就绪、运行和阻塞三种基本状态。由于线程具有许多传统进程所具有的特性，故称为“轻型进程（Light-Weight Process）”；

4.3、存储管理

4.3.1、基本概念

• 存储器管理的对象是主存，也称内存。存储器是计算机系统中的关键性资源，是存放各种信息的主要场所。
• 一般存储器的结构有“寄存器—主存—外存”结构和“寄存器—缓存—主存—外存”结构
  

4.3.2、存储管理方案

• 存储管理方案主要包括分区存储管理、分页存储管理、分段存储管理、段页式存储管理以及虚拟存储管理
• 分区存储管理：分区存储管理是早期的存储管理方案，其基本思想是把主存的用户区划分成若干个区域，每个区域分配给一个用户作业使用，并限定它们只能在自己的区域中运行，这种主存分配方案就是分区存储管理方式。
• 分区的划分方式：固定分区、可变分区和可重定位分区
• 固定分区：固定分区是一种静态分区方式，在系统生成时已将主存划分为若干个分区，每个分区的大小可不等。
• 可变分区：可变分区是一种动态分区方式，存储空间的划分是在作业装入时进行的，故分区的个数是可变的，分区的大小刚好等于作业的大小。可变分区分配需要两种管理表格：已分配表，记录已分配分区的情况；未分配表，记录未分配分区的情况。
• 可变分区分配算法

  首次适应法：从主存低地址开始，寻找第一个可用（即大于等于作业需求的内存）的自由区，这种方法可实现快速分配，缩短查找时间。
  循环适应法：是首次适应法的一个变种，也就是不再是每次都从头开始匹配，而是连续向下匹配。
  最佳适应法：选择最接近作业需求的内存自由区进行分配。这种方法可以减少碎片，但同时也可能带来更多小得无法再用的碎片。
  最差适应法：选择整个主存中最大的内存自由区。
  

• 可重定位分区：可重定位分区是解决碎片问题的简单而又行之有效的方法。基本思想是移动所有已分配好的分区，使之成为连续区域。

4.3.3、分页存储管理

• 分页原理：将一个进程的地址空间划分成若干个大小相等的区域，称为页。相应地，将主存空间划分成与页相同大小的若干个物理块，称为块或页框。在为进程分配主存时，将进程中若干页分别装入多个不相邻接的块中。
• 地址结构：页号+页内地址
• 图中的地址长度为32位，其中0～11位为页内地址（每页的大小为4KB），12～31位为页号，所以允许地址空间的大小最多为1MB个页。
  
• 页表：在将进程的每一页离散地分配到主存的多个物理块中后，系统应能保证在主存中找到每个页面所对应的物理块。页表的作用是实现从页号到物理块号的地址映射。
• 图中逻辑页号为4，查找的物理块号为15，与页内地址256拼接得到物理地址。
  
• 从地址映射的过程可以发现，页式存储管理至少需要两次访问主存。系统为每个进程建立了一张页面映射表，简称页表（放在内存里面），读到页表之后，寄存器找到物理块号再次读取内存取到进程数据。
• 快表：用来保存当前访问频率高的少数活动页的页号及相关信息。说白了就是把页表访问频率比较高的记录给抽取出来放在联想存储器。联想存储器这玩意在这种使用场景比内存更快一些，你这么理解就完事了。

80386的逻辑地址有2^32个，若页面大小为4KB（2^12B），则页表项达1MB个，每个页表项占用4B，故每个进程的页表占用4MB主存空间

4.3.4、分段存储管理

• 在系统中为每个进程建立一张段映射表，简称为“段表”。
• 每个段在表中占有一个表项，在其中记录了该段在主存中的起始地址（又称为“基址”）和段的长度。
• 逻辑地址转化为物理地址过程，在不发生地址越界的情况下，通过段表使用段号查询基址，基址+段内地址=物理地址。

4.3.5、段页式存储管理

• 段页式管理的地址结构
  
• 对比分段存储管理：段内页号+页内地址=段内地址
• 段内页号+页内地址的计算和分页存储管理的计算方式是完全一样的，正常计算出来即可
• 物理地址的计算过程：段内页号+页内地址通过页表计算出物理地址（段内地址），段内地址再和段长比较，如果没越界，通过段号查询段表得到基址，基址+段内地址（段内页号+页内地址求得的的物理地址）=物理地址

4.3.6、虚拟存储管理

• 如果一个作业只部分装入主存便可开始启动运行，其余部分暂时留在磁盘上，需要时再装入主存。
• 程序局部性原理：空间局部性、时间局部性
• 虚拟存储器的实现：请求分页系统、请求分段系统、请求段页式系统

4.4、设备管理

• 设备管理采用的相关缓冲技术：通道技术、DMA技术、缓冲技术、Spooling技术
• 磁盘调度算法：先来先服务、最短寻道时间优先、扫描算法、单向扫描调度算法

4.5、文件管理

4.5.1、文件与文件系统

• 文件：文件（file）是具有符号名的、在逻辑上具有完整意义的一组相关信息项的集合。
• 文件系统：所谓文件管理系统，就是操作系统中实现文件统一管理的一组软件和相关数据的集合，专门负责管理和存取文件信息的软件机构，简称文件系统。
• 文件类型：

  按文件性质和用途：系统文件、库文件和用户文件
  信息保存期限分类：临时文件、档案文件和永久文件
  文件的保护方式分类：只读文件、读写文件、可执行文件和不保护文件
  UNIX系统将文件分为：普通文件、目录文件和设备文件（特殊文件）
  常用的文件系统类型：FAT、Vfat、NTFS、Ext2和HPFS等
  

4.5.2、文件的结构和组织

• 文件的逻辑结构：记录式文件（有结构）、流式文件（无结构）
• 文件的物理结构：连续结构、链接结构、索引结构、多个物理块的索引表

4.5.3、文件目录

• 文件控制块：基本信息类、存取控制信息类、使用信息类
• 目录结构：一级目录结构、二级目录结构、多级目录结构

4.5.4　存取方法和存储空间的管理

• 文件的存取方法：顺序存取法、直接存取法、按键存取法
• 文件存储空间的管理：空闲区表、位示图、空闲块链、成组链接法

4.5.5、文件的使用

• 文件系统将用户的逻辑文件按一定的组织方式转换成物理文件存放到文件存储器上，也就是说，文件系统为每个文件与该文件在磁盘上的存放位置建立了对应关系。

4.5.6、文件的共享和保护

• 文件的共享：硬链接、符号链接
• 文件的保护：存取控制矩阵、存取控制表、用户权限表、密码

4.5.7、系统的安全与可靠性

• 系统安全4个级别：系统级、用户级、目录级和文件级
• 文件系统的可靠性：转储和恢复、日志文件、文件系统的一致性

4.6、作业管理

4.6.1、作业与作业控制

• 可以采用脱机和联机两种控制方式控制用户作业的运行。
• 作业由程序、数据和作业说明书三部分组成
• 作业状态分为4种：提交、后备、执行和完成。
• 作业控制块（JCB）：作业控制块（JCB），是记录与该作业有关的各种信息的登记表。JCB是作业存在的唯一标志，包括用户名、作业名和状态标志等信息。

4.6.2、作业调度

• 作业调度算法：先来先服务、短作业优先、响应比高优先、优先级调度算法、均衡调度算法
• 作业调度算法性能的衡量指标：在一个以批量处理为主的系统中，通常用平均周转时间或平均带权周转时间来衡量调度性能的优劣。简单来说：作业等待时间越短，调度越好。

4.6.3、用户界面

• 计算机用户界面的发展过程：控制面板式用户界面、字符用户界面、图形用户界面、新一代用户界面

4.7、网络与嵌入式操作系统基础知识

• 网络操作系统类型：集中模式、客户端／服务器模式、对等模式（peer-to-peer）模式
• 网络操作系统主要有三大阵营：UNIX、Windows NT和NetWare
• 嵌入式操作系统的特点：微型化、可定制、实时性、可靠性、易移植性
• 嵌入式操作系统有Windows CE、VxWorks、pSOS、Palm OS和μC/OS-Ⅱ

4.8、UNIX操作系统实例

• UNIX操作系统是由美国贝尔实验室发明的一种多用户、多任务的分时操作系统。
• UNIX文件系统的目录结构是树型带交叉勾连的，根目录记为“/”，非叶节点为目录文件，叶节点可以是目录文件，也可以是文件或特殊文件。
• UNIX进程与存储管理：在UNIX中，进程由控制块（PCB）、正文段和数据段组成；在UNIX中的进程控制子系统负责进程同步、进程间通信、存储管理及进程调度；UNIX系统对进程的调度采用动态优先数调度算法，进程的优先数随进程的执行情况而变化。
• UNIX设备管理：在UNIX系统中，文件等于系统中可用的任何资源；块设备与字符设备具有相似的层次结构；将设备作为一个特殊文件，并赋予一个文件名；采用完善的缓冲区管理技术。

5、软件工程基础知识

5.1、软件工程概述

• 按照软件的应用领域分为10大类：系统软件、应用软件、工程/科学软件、嵌入式软件、产品线软件、Web应用、人工智能软件、开放计算、网络资源、开源软件
• 软件工程7条基本原理

  1.用分阶段的生命周期计划严格管理
  2.坚持进行阶段评审
  3.实现严格的产品控制
  4.采用现代程序设计技术
  5.结果应能清楚地审查
  6.开发小组的人员应少而精
  7.承认不断改进软件工程实践的必要性
  

• 软件生存周期：可行性分析与项目开发计划、需求分析、设计(概要设计和详细设计)、编码、测试、维护
• 能力成熟度模型（CMM）

  初始级
  可重复级
  已定义级
  已管理级
  优化级
  

• 能力成熟度模型集成（CMMI）：阶段型模型（类似CMM）和连续式模型

5.2、软件过程模型

• 瀑布模型：瀑布模型是将软件生存周期中的各个活动规定为依线性顺序连接的若干阶段的模型，包括需求分析、设计、编码、测试、运行与维护。它规定了由前至后、相互衔接的固定次序，如同瀑布流水逐级下落。
• 增量模型：增量模型融合了瀑布模型的基本成分和原型实现的选代特征，它假设可以将需求分段为系列增量产品，每一增量可以分别开发。
• 演化模型：软件类似于其他复杂的系统，会随着时间的推移而演化。常见的细分模型有：原型模型、螺旋模型。
• 喷泉模型：喷泉模型是一种以用户需求为动力,以对象作为驱动的模型,适合于面向对象的开发方法。它克服了瀑布模型不支持软件重用和多项开发活动集成的局限性。
• 基于构件的开发模型：基于构件的开发是指利用预先包装的构件来构造应用系统。
• 形式化方法模型(Formal Methods Model )：形式化方法是建立在严格数学基础上的一种软件开发方法，其主要活动是生成计算机软件形式化的数学规格说明。
• 统一过程(UP)模型：统一过程模型是一种“用例和风险驱动，以架构为中心，迭代并且增量”的开发过程，由UM工方法和工具支持。
• 敏捷方法(Agile Development)：敏捷开发的总体目标是通过“尽可能早地、持续地对有价值的软件的交付”使客户满意。
• 极限编程(XP)

  4大价值观:沟通、简单性、反馈和勇气。
  5个原则:快速反馈、简单性假设、逐步修改、提倡更改和优质工作。
  12个最佳实践:计划游戏(快速制定计划、随着细节的不断变化而完善)、小型发布(系统的设计要能够尽可能早地交付)、隐喻(找到合适的比喻传达信息)、简单设计(只处理当前的需求,使设计保持简单)、测试先行(先写测试代码,然后再编写程序)、重构(重新审视需求和设计，重新明确地描述它们以符合新的和现有的需求)、结队编程、集体代码所有制、持续集成(可以按日甚至按小时为客户提供可运行的版本)、每周工作 40 个小时、现场客户和编码标准。
  

5.3、需求分析

• 软件需求：需求包括功能需求、性能需求、用户或人的因素、环境需求、界面需求、文档需求、数据需求、资源使用需求、安全保密需求、可靠性需求、软件成本消耗与开发进度需求等。
• 需求分析原则

  (1)必须能够表示和理解问题的信息域。
  (2)必须能够定义软件将完成的任务。
  (3)必须能够表示软件的行为(作为外部事件的结束)。
  (4)必须划分描述数据、功能和行为的模型，从而可以分层次地揭示细节。
  (5)分析过程应该从要素信息移向细节信息。
  

• 需求工程：需求工程可以细分为需求获取、需求分析与协商、系统建模、需求规约、需求验证以及需求管理6个阶段。

5.4、系统设计

• 概要设计：设计软件系统总体结构、数据结构及数据库设计、编写概要设计文档、评审
• 详细设计：对每个模块每个步骤进行更细致的设计。

系统测试一原则和目的

• 尽早、不断的进行测试。
• 程序员避免测试自己设计的程序。
• 既要选择有效、合理的数据,也要选择无效、不合理的数据。
• 修改后应进行回归测试。
• 尚未发现的错误数量与该程序已发现错误数成正比

5.5、系统测试

5.5.1、系统测试与调试

• 意义：系统测试是为了发现错误而执行程序的过程，成功的测试是发现了至今尚未发现的错误的测试。
• 目的：希望能以最少的人力和时间发现潜在的各种错误和缺陷。

5.5.2、传统软件的测试策略

单元测试（模块测试）

• 一般是在编程阶段完成，由程序员对自己编写的模块自行测试，检查模块是否实现了详细设计说明书中规定的功能和算法，通常使用白盒测试。
• 单元测试计划应该在详细设计阶段制定。
• 单元测试期间着重从：模块接口、局部数据结构、重要的执行通路、出错处理、边界条件这几个方面对模块进行测试。

集成测试（组装测试）

• 主要目标是发现模块间的接口和通信问题。集成测试主要发现概要设计阶段产生的错误，通常采用黑盒测试。集成测试计划应该在概要设计阶段制定。集成的方式可分为非增殖式和增殖式。

确认测试

• 检查软件的功能、性能和其他特征是否与用户的需求一致。它是以需求规格说明书作为依据的测试，通常采用黑盒测试。软件确认测试首先要进行有效性测试以及软件配置审查，然后进行验收测试。
• 确认测试一般有以下三个步骤：
  （1） 有效性测试
  （2） 软件配置审查
  （3） 验收测试
• α测试与β测试（当一个软件是作为产品被许多客户使用时需要用这种测试）

系统测试（结束）

• 系统测试的任务是把软件放在实际的硬件和网络环境中进行测试，主要测试软件的非功能需求和质量属性是否得到满足。系统测试是根据系统方案说明书来设计测试用例，通常采用黑盒测试。常见的系统测试有：恢复测试、安全性测试、强度测试、性能测试、可靠性测试和安装测试。在已确认的计算机软硬件环境下，通过与系统需求对比，发现系统与用户需求不符或矛盾的地方。

回归测试

• 在软件发生变更后进行的测试，以发现变更时引起的其他错误

5.5.3、测试面向对象软件

• 以下四个层次由低到高的顺序排列
  (1)测试与对象关联的单个操作，即算法层。
  (2)测试单个对象类，类层。
  (3)测试对象集群，模板层
  (4)测试面向对象系统，系统层。

5.5.4、测试Web应用

• 质量维度：内容、功能、结构、可用性、导航性、性能、兼容性、安全性。
• WebApp测试策略

  (1)对 WebApp 的内容模型进行评审，以发现错误。
  (2)对接口模型进行评审，保证适合所有的用例。
  (3)评审 WebApp 的设计模型，发现导航错误。
  (4)测试用户界面，发现表现机制和(或)导航机制中的错误。
  (5)对功能构件进行单元测试。
  (6)对贯穿体系结构的导航进行测试。
  (7)在各种不同的环境配置下实现 WebApp，并测试 WebApp 对于每一种配置的兼容性。
  (8)进行安全性测试，试图攻击 WebApp 或其所处环境的弱点。
  (9)进行性能测试。
  (10)通过可监控的最终用户群对 WebApp 进行测试，对他们与系统的交互结果进行以下方面的评估，包括内容和导航错误、可用性、兼容性以及 WebApp 的安全性、可靠性及性能等方面的评估。
  

5.5.5、测试方法

• 静态测试：人工检测、计算机辅助静态检测
• 动态测试：黑盒测试、白盒测试

黑盒测试

• 等价类划分
• 边界值分析
• 错误推测
• 因果图

白盒测试

基本路径测试

• 细节不是那么重要

循环覆盖测试

• 细节不是那么重要

逻辑覆盖测试

• 语句覆盖：使被测程序中的每条语句至少执行一次
• 判定覆盖（分支覆盖）：使被测程序中的每个判定表达式至少获得一次“真”值和“假”值
• 条件覆盖：使被测程序中的每个逻辑条件的各种可能的值至少满足一次
• 判定/条件覆盖：使得判定中的每个条件的“真”值和“假”值至少出现一次，并使本身判定结果的“真”值和“假”值至少出现一次
• 条件组合覆盖：使得每个判定中条件的各种可能值的组合都至少出现一次。满足条件组合覆盖的测试用例是一定满足判定覆盖、条件覆盖和判定/条件覆盖的
• 路径覆盖：覆盖被测试程序中所有可能的路径

5.5.6、调试

• 调试并不是测试，且总是发生在测试之后。
• 调试方法：试探法、回溯法、对分查找法、归纳法、演绎法

5.6、运行和维护知识

• 一个系统开发后，让它实际运行一段时间，是对系统最好的检验和测试方法。
• 新旧系统之间的转换方式：直接转换、并行转换和分段转换。
• 软件维护：软件维护是软件生命周期中的最后一个阶段，处于系统投入生产性运行以后的时期中，因此不属于系统开发过程。
• 系统维护：主要包括硬件维护、软件维护和数据维护。
• 系统评价：信息系统的评价分为广义和狭义两种。广义的信息系统评价是指从系统开发的一开始到结束的每一阶段都需要进行评价。狭义的信息系统评价则是指在系统建成并投入运行之后所进行的全面、综合的评价。

5.7、软件项目管理

5.7.1、软件项目管理涉及的范围

• 人员：项目管理人员、高级管理人员、开发人员、客户、最终用户
• 产品：项目环境、信息目标、功能和性能
• 过程：软件过程提供了一个项目团队要选择一个适合于待开发软件的过程模型
• 项目：明确目标及过程、保持动力、跟踪进展、做出明智的决策、进行事后分析

5.7.2、软件项目估算

• 估算方法：基于已经完成的类似项目进行估算、基于分解技术进行估算、基于经验估算模型的估算
• 成本估算方法：自顶向下估算方法、自底向上估算方法、差别估算方法、其他估算方法
• COCOMO 估算模型：COCOMO 模型是一种精确的、易于使用的成本估算模型。COCOMO 模型按其详细程度分为基本COCOMO 模型（静态单变量）、中级 COCOMO 模型（静态多变量）和详细 COCOMO 模型。
• COCOMOⅡ 模型：COCOMO 模型的升级版，分为3个阶段性模型分别是应用组装模型、早期设计阶段模型、体系结构阶段模型。
• Putnam 估算模型：Putnam 模型是一种动态多变量模型,它是假设在软件开发的整个生存周期中工作量有特定的分布。

5.7.3、进度管理

进度管理的基本准则

• 进度管理的基本准则：划分、相互依赖性、时间分配、工作量确认、确定责任、明确输出结果、确定里程碑。

进度安排

• 为监控软件项目的进度计划和工作的实际进展情况，表示各项任务之间进度的相互依赖关系，需要采用图示的方法。在图中明确标明如下内容。

  (1)各个任务的计划开始时间和完成时间。
  (2)各个任务的完成标志。
  (3)各个任务与参与工作的人数，各个任务与工作量之间的衔接情况。
  (4)完成各个任务所需的物理资源和数据资源。
  

Gantt图

• Gantt图是一种简单的水平条形图,它以日历为基准描述项目任务。水平轴表示日历时间线(如时、天、周、月和年等)，每个条形表示一个任务，任务名称垂直地列在左边的列中，图中水平条的起点和终点对应水平轴上的时间，分别表示该任务的开始时间和结束时间，水平条的长度表示完成该任务所持续的时间。当日历中同一时段存在多个水平条时，表示任务之间的并发。

PERT图

• PERT图是一个有向图，用箭头表示任务，它可以表示完成该任务所需的时间，箭头指向节点表示流入节点的任务的结束，并开始流出节点的任务，这里把节点当成事件。
• 只有当流入该节点的所有任务都结束时，节点所表示的事件才出现，流出节点的任务才可以开始。事件本身不消耗时间和资源，它仅表示某个时间点。一个事件有一个事件号和出现该事件的最早时刻和最迟时刻。每个任务还有一个松弛时间，表示在不影响整个工期的前提下，完成该任务有多少机动余地。
• PERT图不仅给出了每个任务的开始时间、结束时间和完成该任务所需的时间，还给出了任务之间的关系，即哪些任务完成后才能开始另外一些任务，以及如期完成整个工程的关键路径。松弛时间则反映了完成某些任务时可以推迟其开始时间或延长其所需的完成时间。但是PERT图不能反映任务之间的并行关系。

5.7.4、软件项目的组织

• 组织原则：尽早落实责任、减少交流接口、责权均衡
• 组织结构的模式：按项目划分的模式、按职能划分的模式、矩阵模式
• 程序设计小组的组织方式：主程序员制小组、民主制小组（无主程序员组）、层次式小组
• 主程序员制小组沟通渠道：N-1
• 民主制小组沟通渠道：N*(N-1)/2

5.7.5、软件配置管理

• 基线：基线是软件生存周期中各开发阶段的一个特定点，它的作用是使各开发阶段的工作划分更加明确，使本来连续的工作在这些点上断开，以便于检查与肯定阶段成果。
• 软件配置项：软件配置项(Software Configure Item，SCI)是软件工程中产生的信息项，它是配置管理的基本单位，对于已经成为基线的 SC，虽然可以修改，但必须按照一个特殊的、正式的过程进行评估，确认每一处修改。
• 版本控制：软件配置实际上是一个动态的概念，它一方面随着软件生存周期向前推进，SCI的数量在不断增多，一些文档经过转换生成另一些文档，并产生一些信息;另一方面又随时会有新的变更出现，形成新的版本。
• 变更控制：软件工程过程中某一阶段的变更均要引起软件配置的变更，这种变更必须严格地加以控制和管理，保持修改信息，并把精确、清晰的信息传递到软件工程过程的下一步骤。

5.7.6 风险管理

• 风险是指"损失或伤害的可能性"。
• 商业风险：市场风险、策略风险、销售风险、管理风险、预算风险
• 风险管理包含：风险识别、风险预测、风险评估、风险控制

5.8、软件质量

• 软件质量模型由3个层次组成：第一层是质量特性，第二层是质量子特性，第三层是度量指标。该模型的质量特性和质量子特性的含义如下。
• 软件质量特性
  
• 软件质量方面强调以下3个要点

  (1)软件必须满足用户规定的需求，与用户需求不一致的软件无质量可言。
  (2)软件应遵循规定标准所定义的一系列开发准则，不遵循这些准则的软件，其质量难以得到保证。
  (3)软件还应满足某些隐含的需求，例如希望有好的可理解性、可维护性等，而这些隐含的需求可能未被明确地写在用户规定的需求中，如果软件只满足它的显式需求而不满足其隐含需求，那么该软件的质量是令人质疑的。
  

• 软件质量保证7个任务：应用技术方法、进行正式的技术评审、测试软件、标准的实施、控制变更、度量、记录保存和报告。
• 软件评审：设计质量的评审内容、程序质量的评审内容、运行环境的接口
• 容错冗余技术：结构冗余、信息冗余、时间冗余、冗余附加技术

5.9、软件度量

McCabe度量法

• McCabe复杂性度量又称为环路度量，它认为程序的复杂性很大程度上取决于控制的复杂性。单一的顺序程序结构最为简单，循环和选择所构成的环路越多，程序就越复杂。根据图论，在一个强连通的有向图G中，环的个数V(G)由以下公式给出：V(G)=m-n+2 式中，V(G)为有向图G中的环路数， m为图G中弧的个数， n为图G中的节点数。

5.10、软件工具与软件开发环境

• 软件开发工具：需求分析工具、设计工具、编码与排错工具、测试工具等。
• 软件维护工具：版本控制工具、文档分析工具、开发信息库工具、逆向工程工具和再工程工具。
• 软件管理和软件支持工具：项目管理工具、配置管理工具和软件评价工具。

6、结构化开发方法

6.1、系统分析概述

• 系统分析过程图
  
• 系统设计的基本原理：抽象、模块化、信息屏蔽、模块独立
• 系统结构设计原则：分解-协调原则、自顶向下的原则、信息隐蔽、抽象的原则、一致性原则、明确性原则、模块之间的耦合尽可能小模块的内聚度尽可能高的原则、模块的扇入系数和扇出系数要合理、模块的规模适当。
• 子系统划分原则：子系统要具有相对独立性、子系统之间数据的依赖性尽量小、子系统划分的结果应使数据几余较小、子系统的设置应考虑今后管理发展的需要、子系统的划分应便于系统分阶段实现
• 模块的概念：模块是组成系统的基本单位，它的特点是可以组合、分解和更换。
• 模块4个要素：输入和输出、处理功能、内部数据、程序代码
• 模块结构图的基本符号
  

6.2、结构化分析方法

6.2.1、结构化分析方法概述

• 手段：抽象和分解
• 分析结果：一套分层的数据流图、一本数据词典、一组小说明(也称加工逻辑说明)、补充材料。

6.2.2、数据流图(Data Flow Diagram，DFD)

• 在面向数据流的设计方法中，一般把数据流图中的数据流划分为两种类型，一种是变换流，一种是事务流。DFD由数据流、加工、数据存储和外部实体4个要素构成。
  

6.2.3、数据字典（DD）

• 条目类型：数据流、数据项、数据存储和基本加工
• 数据词典管理：词典管理主要是把词典条目按照某种格式组织后存储在词典中，并提供排序、查找和统计等功能。
• 加工逻辑的描述方法：结构化语言、判定表、判定树

6.3、结构化设计方法

• 结构化设计的步骤：建立初始结构图、对结构图的改进、书写设计文档、设计评审
• 数据流的类型：变换流、事务流

6.4、WebApp分析与设计

• WebApp 适合采用敏捷开发过程模型进行开发
• WebApp的特性：网络密集性、并发性、无法预知的负载量、性能、可用性、数据驱动
• WebApp需求模型：内容模型、交互模型、功能模型、导航模型、配置模型
• WebApp设计：架构设计、构件设计、内容设计、导航设计

6.5、用户界面设计

• 黄金原则：用户操纵控制、减少用户的记忆负担、保持界面一致
• 用户界面设计问题：系统响应时间、帮助设施、错误信息处理、菜单和命令标记

7、面向对象技术

7.1、面相对象基础

• 面向对象=对象(Object)+分类(Classification)+继承(Inheritance)+通过消息的通信(Communication with Messages )
• 面向对象分析5个活动：认定对象、组织对象、描述对象间的相互作用、确定对象的操作、定义对象的内部信息。
• OOA的5个活动：识别类及对象、定义属性、定义服务、识别关系、识别包。
• 面向对象设计的原则：单一责任原则、开放-封闭原则、里氏替换原则、依赖倒置原则、接口分离原则、重用发布等价原则、共同封闭原则、共同重用原则、无环依赖原则、稳定依赖原则、稳定抽象原则
• 面向对象测试4个层次：算法层、类层、模块层、系统层

7.2、UML（统一建模语言）

• UML4种事物：结构事物、行为事物、分组事物和注释事物
• UMI 4 种关系：依赖、关联、泛化和实现
• UML 2.0 提供了 13 种图，分别是类图、对象图、用例图、序列图、通信图、状态图、活动图、构件图、组合结构图、部署图、包图、交互概览图和计时图。序列图、通信图、交互览图和计时图均被称为交互图。

7.3、设计模式

• 设计模式4个基本要素：模式名称、问题、解决方案、效果
• 创建型设计模式：Abstract Factory（抽象工厂）、Builder（生成器）、Factory Method（构造方法）、Prototype（原型）、Singleton（单例）
• 结构型设计模式：Adapter（适配器）、Bridge（桥接）、Composite(组合)、Decorator(装饰)、Facade(外观)、Flyweight(享元)、Proxy(代理)、
• 行为设计模式：Chain of Responsibility(责任链)、Command(命令)、Interpreter(解释器)、Iterator(迭代器)、Mediator(中介者)、Memento(备忘录)、Observer(观察者)、State(状态)、Strategy(策略)、Template Method(模板方法)、Visitor(访问者)

8、算法设计与分析

8.1、算法设计与分析的基本概念

• 算法5个重要特性：有穷性、确定性、可行性、输入、输出
• 算法设计技术主要有分治法、动态规划法、贪心法、回溯法、分支限界法、概率算法和近似算法等。
• 算法设计技术主要有：分治法、动态规划法、贪心法、回溯法、分支限界法、概率算法和近似算法等。
• 算法选择的主要标准首先是算法的正确性、可靠性、简单性和易理解性，其次是算法的时间复杂度和空间复杂度要低
• 常用的表示算法的方法有自然语言、流程图、程序设计语言和伪代码等。

8.2、算法分析基础

• 在设计算法时，通常应考虑以下原则：首先说设计的算法必须是正确的，其次应有很好的可读性，还必须具有健壮性，最后应考虑所设计的算法具有高效率和低存储量。

8.3、分治法

• 对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题,然后将各子问题的解合并得到原问题的解。
• 要求:
  该问题的规模缩小到一定的程度就可以容易地解决。
  该问题可以分解为若干个规模较小的相同问题。
  利用该问题分解出的子问题的解可以合并为该问题的解。
  该问题所分解出的各个子问题是相互独立的。

8.4、动态规划法

• 基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
• 与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。
• 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题一个值，我们希望找到具有中，可能会有许多可行解，每个解都对应于最优值的那个解。当然，最优解可能会有多个，动态规划算法能找出其中的一个最优解。
• 动态规划法：最优子结构、重叠子问题
• 区别贪心法：整体最优

8.5、贪心法

• 总是做出在当前来说是最好的选择，而并不从整体上加以考虑,它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不必为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但得不到最优解。也常用于解决最优化的问题。
• 最优子结构。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。问题的最优子结构是该问题可以采用动态规划法或者贪心法求解的关键性质。
• 贪心选择性质。指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。这是贪心法和动态规划法的主要区别。
• 局部最优，不关心整体。

8.6、回溯法

• 回溯法是种选优搜索法,按选优条件向前搜索,以达到目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术就是回溯法。
• 经典问题：迷宫

8.7、分支限界法

• 分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

8.8、概率算法

• 前面讨论的算法对于所有合理的输入都给出正确的输出，概率算法将这一条件放宽，把随机性的选择加入到算法中。在算法执行某些步骤时，可以随机地选择下一步该如何进行，同时允许结果以较小的概率出现错误，并以此为代价，获得算法运行时间的大幅度减少。概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次，可能得到完全不同的效果。这两次求解所需的时间甚至所得到的结果可能会有相当大的差别。如果一个问题没有有效的确定性算法可以在一个合理的时间内给出解，但是该问题能接受小概率错误，那么采用概率算法就可以快速找到这个问题的解。

8.9、近似算法

• 近似算法是这样一个过程:虽然它可能找不到个最优解，但它总会给待求解的问题提供一个解。为了具有实用性，近似算法必须能够给出算法所产生的解与最优解之间的差别或者比例的一个界限，它保证任意一个实例的近似最优解与最优解之间相差的程度。显然，这个差别越小，近似算法越具有实用性。

8.10、数据挖掘算法

• 数据挖掘利用机器学习方法对多种数据，包括数据库数据、数据仓库数据、Web 数据等进行分析和挖掘。数据挖掘的核心是算法，其主要功能包括分类、回归、关联规则和聚类等。

8.11、智能优化算法

• 人工神经网络
• 遗传算法
• 模拟退火算法
• 禁忌搜索算法
• 蚁群算法
• 粒子群优化算法

9、数据库技术基础

10、网络与信息安全基础知识

10.1、网络概述

• 计算机网络发展的4个阶段：具有通信功能的单机系统、具有通信功能的多机系统、以共享资源为目的的计算机网络、以局域网及因特网为支撑环境的分布式计算机系统
• 计算机网络的功能：数据通信、资源共享、负载均衡、高可用性
• 计算机网络的分类：局域网、城域网、广域网
• 网络拓扑结构：总线型、星型、环型、树型和分布式结构等。
• ISO/OSI的参考模型：物理层、数据链路层网络层、传输层、会话层、表示层和应用层。
  

10.2、网络互联硬件

10.2.1、网络的设备

• 网络传输介质互连设备：T形头、收发器、RJ-45
• 物理层的互连设备：中继器(Repeater)、集线器(Hub)
• 数据链路层的互连设备：网桥(Bridge)、交换机(Switch)
• 网络层互连设备：路由器
• 应用层互联设备：网关

10.2.2、网络的传输介质

• 有线介质：双绞线、同轴电缆、光纤
• 无线介质：微波、红外线和激光、卫星

10.2.3、组建网络

• 在一个局域网中，其基本组成部件为服务器、客户端、网络设备、通信介质和网络软件等。

10.3、网络协议与标准

• 电信标准、国际标准、Internet标准
• 局域网协议：IEEE 802.3(CSMA/CD，以太网)、IEEE 802.4(Token Bus，令牌总线)和 IEEE 802.5(Token Ring，令牌环)
• 以太网主要包括3种类型:IEEE 8023中定义的标准局域网，速度为10Mbps，传输介质为细同轴电缆;IEEE 802.3u 中定义的快速以太网,速度为 100Mbps,传输介质为双绞线:IEEE 802.3z 中定义的千兆以太网，速度为 1000Mbps，传输介质为光纤或双绞线。
• 广域网协议： PPP(点对点协议)、DDN、ISDN(综合业务数字网)、ER(帧中继)和 ATM(异步传输模式)
• TCP/IP特性：逻辑编址、路由选择、域名解析、错误检测和流量控制以及对应用程序的支持等。

10.4、Internet及应用

• 从用户的角度来看，整个 Internet 在逻辑上是统一的、独立的，在物理上则由不同的网络互连而成。从技术角度看，Internet 本身不是某一种具体的物理网络技术，它是能够互相传递信息的众多网络的一个统称，或者说它是一个网间网，只要人们进入了这个互联网，就是在使用Internet 。正是由于 Internet 的这种特性，使得广大 Internet 用户不必关心网络的连接，而只关心网络提供的丰富资源。
• Internet 地址类型：A类、B 类、C类、D类和E类
  
  
• Ipv6基本首部格式
  

10.5、信息安全基础知识

• 信息安全5个要素：机密性、完整性、可用性、可控性与可审查性。
• 计算机信息系统安全保护等级：用户自主保护级、系统审计保护级、安全标记保护级、结构化保护级、访问验证保护级

10.6、网络安全概述

• 网络安全威胁：非授权访问、信息泄露或丢失、破坏数据完整性、拒绝服务攻击、利用网络传播病毒
• 网络安全控制技术：防火墙技术、加密技术、用户识别技术、访问控制技术、网络反病毒技术、网络安全漏洞扫描技术、入侵检测技术
• 防火墙技术：包过滤防火墙、应用代理网关防火墙、状态检测技术防火墙
• 入侵检测系统(Intrusion Detection System，IDS)：入侵检测系统作为防火墙之后的第二道安全屏障，通过从计算机系统或网络中的若干关键点收集网络的安全日志、用户的行为、网络数据包和审计记录等信息并对其进行分析，从中检查是否有违反安全策略的行为和遭到入侵攻击的迹象，入侵检测系统根据检测结果，自动做出响应。

11、标准化和软件知识产权基础知识

11.1、标准的分类与标准的编号

分类

• 国际标准:ISO、IEC等国际标准化组织
• 国家标准:GB-中国、ANSI一美国、BS一英国、JIS一日本
• 区域标准:又称为地区标准，如PASC一太平洋地区标准会议、CEN一欧洲标准委员会、ASAC一亚洲标准咨询委员会、ARSO一非洲地区标准化组织
• 行业标准:GJB一中国军用标准、MIT-S一美国军用标准、IEEE一美国电气电子工程师协会。
• 地方标准:国家的地方一级行政机构制订的标准
• 企业标准
• 项目规范

编号

• 国际、国外标准代号：标准代号+专业类号+顺序号+年代号
• 我国国家标准代号：强制性标准代号为GB、推荐性标准代号为GB/T指导性标准代号为GB/Z、实物标准代号GSB
• 行业标准代号：由汉语拼音大写字母组成(如电子行业为SJ)
• 地方标准代号：由DB加上省级行政区划代码的前两位企业标准代号:由Q加上企业代号组成

11.2、知识产权基础知识

11.2.1、基本概念

• 知识产权又称为智慧财产权，是指人们通过自己的智力活动创造的成果和经营管理活动中的经验、知识而依法所享有的权利。传统的知识产权可分为“工业产权”和’著作权”。
• 知识产权包括以下内容:
  1、关于文学、艺术和科学作品的权利。
  2、关于表演艺术家的表演以及唱片和广播节目的权利。
  3、关于人类一切活动领域的发明的权利。
  4、关于科学发现的权利。
  5、关于工业品外观设计的权利。
  6、关于商标、服务标记以及商业名称和标志的权利。
  7、关于制止不正当竞争的权利。
  8、在工业、科学、文学艺术领域内由于智力创造活动而产生的一切其他权利。
• 从所涉及的法律法规角度
  1、著作权法
  2、计算机软件保护条例
  3、商标法
  4、专利法
• 从试题考点分布的角度
  1、保护期限
  2、知识产权人确定
  3、侵权判断

11.2.2、保护期限

11.2.2、知识产权人确定

11.2.3、侵权判定

著作权

• 中国公民、法人或者其他组织的作品,不论是否发表，都享有著作权。
• 开发软件所用的思想、处理过程、操作方法或者数学概念不受保护。
• 著作权法不适用于下列情形：
  1、法律、法规，国家机关的决议、决定、命令和其他具有立法、行政、司法性质的文件，及其官方正式译文;
  2、时事新闻。
  3、历法、通用数表、通用表格和公式。

常见的侵权判定

• 不侵权

个人学习、研究或者欣赏;
适当引用;
公开演讲内容
用于教学或科学研究
复制馆藏作品;
免费表演他人作品;
室外公共场所艺术品临摹、绘画、摄影、录像
将汉语作品译成少数民族语言作品或盲文出版。

• 侵权

未经许可，发表他人作品;
未经合作作者许可，将与他人合作创作的作品当作自己单独创作的作品发表的。
未参加创作，在他人作品署名;
歪曲、篡改他人作品的;
剽窃他人作品的;
使用他人作品，未付报酬;
未经出版者许可，使用其出版的图书期刊的版式设计的。

12、软件系统分析与设计

12.1、结构化分析与设计

• 结构化分析将数据和处理(加工)作为分析对象，数据的分析结果表示了现实世界中实体的属性及其之间的相互关系，而处理的分析结果则展现了系统对数据的加工和转换。

  (1)确定系统边界，画出系统环境图。
  (2)自顶向下画出各层数据流图。
  (3)定义数据字典。
  (4)定义加工说明。
  (5)将图、字典以及加工组成分析模型。
  

12.2、数据库分析与设计

• 数据库设计策略：自顶向下(Top Down)和自底向上(Bottom Up)
• 数据库设计步骤：用户需求分析、概念设计、逻辑设计、物理设计
• 概念结构设计策略：自顶向下、自底向上、逐步扩张和混合策略。
• E-R图冲突类型：属性冲突、命名冲突、结构冲突
• E-R图3种联系：一对一，一对多、多对多
• 数据库的物理设计：确定数据分布、确定数据的存储结构、确定数据的访问方式
• 数据库完整性描述：有效性、正确性和一致性

12.3、面向对象分析与设计

• 面向对象分析3个活动：建模系统功能、发现并组织业务对象、组织对象并记录其关系

12.4、算法分析与设计

• 程序=数据结构+算法
• 算法的主要步骤：理解问题、确定相关因素、设计算法、证明算法的正确性、分析算法的效率、根据算法编写代码
• 算法问题类型：查找问题、排序问题、图问题、组合问题、几何问题

12.5、面向对象的程序设计与实现

• 软考-软件设计师 23种设计模式

参考文档

• 软考-软件设计师 知识点整理（一篇就过了 建议收藏）