考试须知

考试项目

• 软件设计师
• 分数：150分
• 及格线：90分

考试时间

• 11月4日
  • 基础知识：早上9.00-11.30
  • 应用技术：下午14.00-16.30

基础知识

选择题（75分）

知识点	分数	考试内容
软件工程基础知识	11	开发模型、设计原则、测试方法、质量特性、CMM、Pert图、风险管理
面向对象	12	面向对象基本概念、面向对象分析与设计、UML、设计模式
数据结构与算法	10	数组、栈、队列、树与二叉树、图、查找与排序、常见算法
程序设计语言	6	文法、有限自动机、正规式、语句的作用、语句的语义、程序的控制结构、函数调用的参数传递、各种程序语言的特点比较
计算机硬件基础	6	浮点数运算、溢出、算术、逻辑运算、计算机体系结构分类、指令系统基础、CISC与RISC、流水线、Cache存储器可靠性分析、校验方法
操作系统	6	进程状态转换图、信号量与PV操作、死锁问题、银行家算法、段页式存储、页面置换算法、磁盘调度、树形文件系统
数据库系统	6	E-R模型、关系代数、元组演算、规范化理论（键、范式、模式分解)、并发控制
计算机网络	5	OSI模型、TCP/IP协议族、子网划分、常用的网络命令
信息安全知识	3	加密解密技术、网络安全、计算机病毒
多媒体基础	3	多媒体基本概念、计算声音、图像、视频文件的容量、JPEG、MPEG
知识产权与标准化	2	作品保护时间，侵权判定，知识产权归属、标准的分类、标准代号

应用技术

简答题（75分）

题号	试题类型	学科知识点	考查内容
试题1	必答题	数据流图	补充数据流图的缺失部分(补充数据流、补充外部实体、补充数据存储），数据流图的改错（包括修正数据流名称、数据流的起点与终点、删除多余数据流），与数据流图相关的概念简答题。
试题2	必答题	数据库设计	E-R模型、关系模式、主键、外键、SQL语言
试题3	必答题	UML建模	用例图、类图与对象图、顺序图、活动图、状态图
试题4	必答题	C语言算法	链表、栈、二叉树、图基本操作的程序实现、动态规划法、分治法、回溯法、递归法、贪心法
试题5	选答题	C++语言程序设计	C++语法+设计模式
试题6	选答题	Java语言程序设计	C++语法+设计模式

计算机组成原理与体系结构基础知识

进制转换和逻辑运算

十进制转n进制

• 用短除法，将余数从后往前排

n进制转十进制

• 按权展开求和

二进制转八进制

• 以小数点为分隔符，3位一组，每组转换成对应的八进制符号
• 如：11110000010.01101 –> 001 111 000 010 . 011 010 –> 1 7 0 2 . 3 2

二进制转十六进制

• 以小数点为分隔符，4位一组，每组转换成对应的八进制符号
• 如：1111000010.01101 –> 0011 1100 0010 . 0110 1000 –> 3 C 2 . 6 8

逻辑运算

• 与（AND）：全一为一，有零为零
• 或（OR）：全零为零，有一为一
• 非（NOT）：一变零，零变一
• 异或（XOR）：相异为一，相同为零
• 同或（XNOR）：相同为一，相异为零
• 与非（NAND）：先与后非
• 或非（NOR）：先或后非

定点数和浮点数

定点数

• 无符号数：没有符号位，只有数值位。通常只有无符号整数，而没有无符号小数
• 有符号数：0表示+，1表示-

• 原码
  • 如：X=+19D，【X】原=0，0010011，即00010011
  • 如：X=-19D，【X】原=1，0010011，即10010011
  • 说明：D表示十进制，O表示八进制，B表示二进制，H表示16进制，如不说明则默认为10进制
• 反码
  • 正数的反码与原码相同。如：【+19】反=0，0010011
  • 负数的反码，将数值位全部取反。如：【-19】反=1，1101100
• 补码
  • 正数的补码与源码相同。如：【+19】补=0，0010011
  • 负数的补码=反码末位+1。如：【-19】补=1，1101101
  • 注意：补码和移码的真值0只有1种表示形式！【+0】补=【-0】补=00000000
  • 补码的补码就是原码
  • 用补码来运算数据，可以简化计算机运算部件的设计
  • 补码的符号位可以与数值位一起参加运算
• 移码
  • 将补码的符号位取反，移码只能用来表示整数

当机械字长为n时，定点数的补码和移码可表示2^n个数，而其原码和反码只能表示2^n-1个数

浮点数

浮点数： 小数点的位置不固定

• $$
  浮点数通常表示成:N=R^E·F，如10^5·0.5312
  $$
• F称为尾数，R称为基数，E称为阶码
• 阶码E，决定浮点数所能表示的数值范围，它是一个带符号的纯整数，在上面例子中E=5
• 尾数F，决定浮点数所能表示的数值精度，它是一个带符号的纯小数，在上面例子中M=4
• 在计算浮点数时，要先对阶，且应该是小阶向大阶对
• 规格化要将尾数的绝对值限定在区间【0.5，1】或【0.5，1）
• 最小负数的阶数一定是奇数 ；最大正数第一个2的阶一定是偶数，第二个2的阶数一定是奇数。简称：奇偶奇

检错纠错码

海明码

• 在数据为之间插入k个校验码，通过扩大码距来实现检错和纠错。
• 码距>=3
• $$
  设数据位是n位．校验位是k位，则n和k必须满足以下关系:2^k-1>=n+k
  $$

奇偶校验码

• 码距等于2，只能检错，不能纠错
• 只能检测奇数位出错的编码

循环冗余码

• 码距等于2，只能检错，不能纠错
• k个数据位后产生r个校验位
• 在求CRC编码时，采用的是模2运算

冯·诺依曼计算机

特点

• 计算机由五大部件组成：输入设备、运算器、存储器、控制器、输出设备
  • CPU：主要由运算器和控制器组成（运算器、控制器、寄存器组和内部总线）
  • 主存是运行内存，辅存是存储容量
  • 主机：由CPU和主存
  • IO设备：由辅存和输入输出设备组成
  • 主机和io设备统称硬件
• 以运算器为中心
  • 输入输出设备与存储器之间的数据传送通过运算器完成

主存储器

存放数据和程序

• 由存储体、MAR、MDR组成
• 存储体
  • 存储单元：每个存储单元存放一串二进制代码。
  • 存储字(word)：存储单元中二进制代码的组合。
  • 存储字长：存储单元中二进制代码的位数。
  • 存储元：即存储二进制的电子元件，每个存储元可存1bit。
• MAR：地址存储器
  • 可以用来判断存储单元的个数，如：当MAR=4位时，总共有2^4个存储单元
• MDR：数据存储器
  • 表明了每个存储单元存放的位数，如：当MDR=16位时，每个存储单元可以存放16bit
• 计算机中的大小关系
  • 位（比特）：1bit=1b
  • 字节：1Byte=1B=8b
  • KB：1KB=1024B，K=2^10
  • MB：1MB=1024KB ，M=2^20
  • GB：1GB=1024MB，G=2^30
  • TB：1TB=1024GB
  • 最小的数据单位是位：b
  • 最小的存储单位是字节：B

运算器

实现算术运算和逻辑运算

• AC:累加器，用于存放操作数并暂存运算结果。
• ALU:算术逻辑单元，通过内部复杂的电路实现算数运算、逻辑运算。
• DR:数据缓存寄存器。
• PSW:状态条件寄存器，用来保存指令运行标志。

控制器

指挥各部件，处理异常，使程序得以运行

• PC:程序计数器，也称指令计数器，PC的内容是程序第一条指令的地址，并存放下一条指令地址，有自动加1功能。
• IR:指令寄存器，当CPU执行一条指令时，先把它从内存储器取到缓冲寄存器中，再送入IR暂存。指令寄存器对用户是完全透明的，操作码和地址码都应存入指令寄存器
• AR:地址寄存器，保存当前CPU所访问的内存单元地址。
• ID:指令译码器，对操作码进行分析。

完成一条指令需要：取指令-分析指令-执行指令

• 在指令周期的过程中，指令先从程序计数器PC中获取指令的地址，以便让内存把指令读取到缓冲寄存器DR上，再把指令送入到指令寄存器IR中暂存。

输入输出设备

• 将信息转换为机器能识别的形式
• 将结果转换为人们熟知的形式

Flynn分类法

• 多指令流单数据流MISD是不可能实现的

指令系统

• 一台计算机的所有指令的集合构成该机的指令系统，也称为指令集。
• 指令(又称机器指令):是指示计算机执行某种操作的命令，是计算机运行的最小功能单位。

指令格式

• 一条指令就是机器语言的一个语句，它是一组有意义的二进制代码。
• 指令和数据以同等地位存于存储器，可按地址寻访。
• 一条指令通常要包括操作码字段 和地址码字段两部分
  • 操作码：干什么
  • 地址码：对谁操作（地址码是操作数的地址。）

寻址方式

• 指令寻址：下一条欲执行指令的指令地址（始终由程序计数器(PC) 给出）
• 数据寻址：确定本条指令的地址码指明的真实地址
  • 立即寻址。操作数就包含在指令中。
  • 寄存器寻址。操作数存放在某一寄存器中，指令中给出存放操作数的寄存器名。
  • 直接寻址。操作数存放在内存单元中，指令中直接给出操作数所在存储单元的地址。
  • 寄存器间接寻址。操作数存放在内存单元中，操作数所在存储单元的地址在某个寄存器中。
  • 间接寻址。指令中给出操作数地址的地址。
  • 相对寻址。指令地址码给出的是一个偏移量（可正可负)，操作数地址等于本条指令的地址加上该偏移量。
  • 变址寻址。操作数地址等于变址寄存器的内容加偏移量。

CISI和RISI

	RISC（精简指令集计算机）	CISI（复杂指令集计算机）
指令种类	少	多
指令复杂度	简单	复杂
指令长度	固定	不固定
寻址方式	少	多
实现(译码)方式	硬布线控制逻辑 （组合逻辑控制器）	微程序控制技术
通用寄存器数量	多	一般
流水线技术	支持	支持

指令的流水处理

• 指令控制方式有顺序方式、重叠方式和流水方式三种。
• 流水方式：是指并行性或并发性嵌入计算机系统里的一种形式，它把重复的顺序处理过程分解为若干子过程，每个子过程能在专用的独立模块上有效地并发工作。
  • 流水线周期为执行时间最长的一段
  • 流水线计算公式：1条指令执行时间+（指令条数-1）*流水线周期
  • 流水线的吞吐率：TP=指令条数/流水线执行时间
  • 建立时间：To=m*to（流水线开始工作后，须经过—定时间才能达到最大吞吐率，这就是建立时间。若m个子过程所用时间一样，均为△to，则建立时间To=m x △to）
  • 流水线的加速比：S=不使用流水线执行时间/使用流水线执行时间
• 如问题：例:若指令流水线把一条指令分为取指、分析和执行三部分,且三部分的时间分别是取指2ns ,分析2ns ,执行1ns。那么,流水线周期是多少?100条指令全部执行完毕需要的时间是多少?流水线吞吐率为多少？流水线加速比是多少？
  • 流水线周期是：2ns
  • 100条指令全部执行完毕需要的时间是：5+99*2=203ns
  • 流水线吞吐率：TP=100/203
  • 流水线加速比：S=500/203

存储系统

存储器

层次结构

• Cache—主存：解决了主存与CPU速度不匹配的问题.
• 主存—辅存：实现虚拟存储系统，解决了主存容量不够的问题。

存储器的分类

• 按位置分类，可分为内存和外存。
  • 内存(主存)：用来存储当前运行所需要的程序和数据，速度快，容量小。
  • 外存(辅存)：用来存储当前不参与运行的数据，容量大但速度慢。
• 按材料分类，可分为磁存储器、半导体存储器和光存储器。
  • 磁存储器：用磁性介质做成，如磁芯、磁泡、磁盘、磁带等。
  • 半导体存储器：根据所用元件又可分为双极型和MOS型两类;根据是否需要刷新又可分为静态和动态两类。
  • 光存储器：由光学、电学和机械部件等组成，如光盘存储器。
• 按工作方式，可分为读/写存储器和只读存储器。
  • 读/写存储器(RAM)：它指既能读取数据也能存入数据的存储器。
  • 只读存储器(ROM)：工作过程中仅能读取的存储器。
• 按访问方式分类
  • 按地址访问
  • 按内容访问（相联存储器）
• 按寻址方式分类
  • 随机存储器RAM
  • 顺序存储器SAM
  • 直接存储器DAM

其他

• Cache：SRAM（静态随机存储器），功率高、成本高、速度快、集成低
• 主存储器：DRAM（动态随机存储器），周期性地刷新

高速缓存Cache

在计算机的存储系统体系中，Cache是访问速度最快的层次。使用Cache改善系统性能的依据是程序的局部性原理。基于局部性原理，不难想到，可以把CPU目前访问的地址“周围”的部分数据放到Cache中，以提高访问效率。它对程序员来说是透明的

• 空间局部性:在最近的未来要用到的信息(指令和数据)，很可能与现在正在使用的信息在存储空间上是邻近的。
  • Eg:数组元素、顺序执行的指令代码。
• 时间局部性:在最近的未来要用到的信息，很可能是现在正在使用的信息。
  • Eg:循环结构里面的指令代码。

要把主存种的地址映射为Cache存储器里面的地址，地址映像方法有三种(由硬件自动完成Cache 与主存之间的地址映射)

• 直接映像：就是主存的块与Cache中块的对应关系是固定的。冲突最多
  • 优点是，地址变换很简单
  • 缺点是，灵活性差。
• 全相联映像：允许主存的任一块可以调入Cache的任一块的空间。冲突最少
  • 优点是，主存的块调入Cache的位置不受限制，十分灵活。
  • 缺点是，无法从主存块号中直接获得Cache的块号，变换比较复杂，速度比较慢。
• 组相联映像：这种方式是前面两种方式的折中。具体方法是将Cache先分成组再分块。组相联映像就是组间采用直接映像方式，而组内的块采用全相联映像方式。冲突较多

选择替换算法的目标是使Cache获得最高的命中率。常用的替换算法有以下几种

• 随机替换(RAND)算法：用随机数发生器产生一个要替换的块号，将该块替换出去。
• 先进先出(FIFO)算法：将最先进入的Cache信息块替换出去。 修
• 近期最少使用(LRU)算法：将近期最少使用的Cache中的信息块替换出去。这种算法较先进先出算法要好些，但此法也不能保证过去不常用的将来也不常用。
• 优化替换(OPT)算法：先执行一次程序，统计Cache的替换情况。有了这样的先验信息，在第二次执行该程序时便可以用最有效的方式来替换，达到最优目的。

硬盘（磁盘）

• 存取时间=寻道时间＋等待时间(平均定位时间+转动延迟)
  • 寻道时间是指磁头移动到磁道所需的时间;
  • 等待时间为等待读写的扇区转到磁头下方所用的时间。

中断

• 中断向量提供中断服务程序的入口地址
• 中断响应时间：发出中断请求开始到进入中断服务程序
• 保存现场：返回来执行原程序，用堆栈来实现

总线系统

• 总线结构可以减少信息传输线的数量
• 系统总线：系统总线是计算机系统内各功能部件(CPU、主存、I/O接口）之间相互连接的总线。
• 按系统总线传输信息内容的不同，又可分为3类，数据总线、地址总线和控制总线。
  • 字长决定数据总线的宽度，容量决定地址总线的宽度
• 片内总线：片内总线是芯片内部的总线。它是CPU芯片内部寄存器与寄存器之间、寄存器与ALU之间的公共连接线。

输入输出的控制方式

• 程序查询方式：指在完成数据的输入/输出中，整个输入/输出过程是在CPU执行程序的控制下完成的。
  • 无条件地与CPU交换数据。先通过CPU查询外设状态，准备好之后再与CPU交换数据。由CPU将数放入内存
  • 一次只能读写一个字
  • CPU和I/O只能串行工作
• 中断驱动方式
  • CPU利用率得到提高，由CPU将数放入内存
  • CPU和I/O可并行工作
  • 一次只能读写一个字
  • I/O设备通过中断信号主动报告I/O操作已完成
• 直接存储器方式DMA：在存储器与I/O设备间直接传送数据，即在内存与I/O设备之间传送一个数据块的过程中，不需要CPU的任何干涉，是—种完全由DMA硬件完成I/O操作的方式。
  • 仅在传送数据块的开始和结束时才需要CPU的干预，由外设直接将数据放入内存
  • CPU和I/0（外设)可并行工作
  • 一次读写的单位为“块”而不是字
  • DMA控制器和中断控制器发出的数据地址是主存物理地址
  • CPU是在一个总线周期结束时响应DMA请求

加密技术与认证技术

对称加密和非对称加密

• 对称加密（私有密钥加密）
  • 加密和解密是同一把密钥，只有一把密钥
  • 缺点：密钥分发有缺陷
  • 优点：加密解密速度很快，适合大量明文数据
  • 加密算法：DES、3DES、RC-5、IDEA、AES、RC4
• 非对称加密（公开密钥加密）
  • 加密和解密不是同一把密钥，一共有两把密钥，分别是公钥和私钥，公钥是共有的，私钥是独有的
  • 用公钥加密只能用私钥解密，用私钥加密只能用公钥解密，所以应该用接收方的公钥加密
  • 私钥用于解密和签名，公钥用于加密和认证
  • 缺点：速度慢
  • 优点：可以实现防窃听的效果
  • 加密算法：RSA、ECC、DSA
• 混合加密
  • 对明文进行对称加密，将对称加密密钥进行非对称加密

认证技术

• 摘要
  • 将发送的明文进行Hash算法后得到摘要放在密文后一起发送过去，与接收方解密后的明文进行相同的Hash算法得到的摘要进行对比如果一致，则没有篡改，否则有篡改
  • 加密算法：HASH、MD5
• 数字签名
  • 发送方用自己的私钥对摘要进行签名（加密）得到数字签名放在密文（消息）后一起发送过去
• 数字证书
  • 用户向CA机构申请数字证书将个人信息和公钥发给CA机构CA机构颁给用户数字证书，数字证书用CA的私钥进行签名（加密)用CA的公钥验证（解密）数字证书得到用户的公钥

程序设计语言

编译程序和解释程序

机械语言和汇编语言为低级语言

• 机械语言：只能识别0和1的机械指令序列
• 汇编语言：汇编指令的集合，汇编指令用符号表示

高级语言

• JAVA、C、Python、C++、PHP等
• 高级语言需要翻译才能让计算机理解
• 翻译的方式：汇编、解释、编译

编译程序和解释程序

• 编译器和解释器都不可省略词法分析、语法分析、语义分析且顺序不可交换

解释程序

• 翻译源程序时不生成独立的目标程序
• 解释程序和源程序要参与到程序的运行过程中
• 解释方式:词法分析、语法分析、语义分析

编译程序

• 翻译时将源程序翻译成独立保存的目标程序，机器上运行的是与源程序等价的目标程序，
• 编译是将高级语言源程序翻译成机器语言程序（汇编形式或机器代码形式)，反编译是编译的逆过程。反编译通常不能把可执行文件还原成高级语言源代码，只能转换成功能上等价的汇编程序。
• 源程序和编译程序都不再参与目标程序的运行过程
• 编译方式:词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成（中间代码生成和代码优化不是必要，可省略）
  • 词法分析
    • 输入：源程序
    • 输出：记号流
    • 作用：分析构成程序的字符及由字符按照构造规则构成的符号是否符合程序语言的规定
  • 语法分析
    • 输入：记号流
    • 输出：语法树（分析树）
    • 作用：对各条语句的结构进行合法性分析，分析程序中的句子结构是否正确
    • 语法分析阶段可以发现程序中的所有语法错误，递归下降分析法和预测分析法是常用的自顶向下的语法分析。
  • 语义分析
    • 输入：语法树（分析树）
    • 作用：进行类型分析和检查
    • 语法制导翻译是一种静态语义分析方法
    • 语义分析阶段不能发现程序中所有的语义错误（可以发现静态语义错误，不能发现动态语义错误，动态语义错误运行时才能发现）
  • 中间代码生成
    • 常见的中间代码有：后缀式、三地址码、三元式、四元式和树（图）等形式。
    • 中间代码可以跨平台，与具体的机器无关
    • 有利于进行与机器无关的优化处理和提高编译程序的可移植性
  • 目标代码生成
    • 目标代码生成阶段的工作与具体的机器密切相关
    • 寄存器的分配处于目标代码生成阶段

符号表

• 不断收集、记录和使用源程序中一些相关符号的类型和特征等信息，并将其存入符号表中。
• 记录源程序中各个字符的必要信息，以辅助语义的正确性检查和代码生成。

传值调用和地址调用

传值调用

• 将实参的值传递给形参，实参可以是变量、常量和表达式。

地址调用

• 将实参的地址传递给形参，形参必须有地址，实参不能是常量（值），表达式。
• 可以实现形参和实参间双向传递数据的效果，即改变形参的值同时也改变了实参的值。

正规式

正规式	正规集
Ab	字符串ab构成的集合
a|b	字符串a、b构成的集合
a*	由0个或多个a构成的字符串集合
(a|b)*	所有字符a和b构成的串的集合
a(a|b)*	以a为首字符的a、b字符串的集合
(a|b)*abb	以abb 结尾的a、b字符串的集合

有限自动化

• 有限自动化是词法分析的一个工具，它能够正确地识别正规集，初态是一个圈，终态是两个圈
• 确定的有限自动机（DFA）：对每一个状态来说识别字符后转移的状态是唯一的
• 不确定的有限自动机（NFA）：对每一个状态来说识别字符后转移的状态是不确定的

上下文无关文法CFG

• 上下文无关文法被广泛地用于表示各种程序设计语言的语法规则
• 终结符号集：不能继续往下推的
• 产生式：包含非终结符号

中缀、后缀表达式

• 中缀：a ？b
  • 中序遍历 得到 中缀式
• 后缀（逆波兰）：ab？
  • 后序遍历 得到 后缀式
• 中缀转后缀：正常转
  • 如：1-2*(3+4)/5 == 1234+ * 5 / –
• 后缀转中缀：从左到右，用栈的方式转，先进后出,先进的出之后放在b的位置
  • 如：1234+ * 5 / – – ==1-2*(3+4)/5

杂知识点

• 静态绑定在编译时进行的，动态绑定在运行时进行的
• 脚本语言都是动态语言（弱类型语言），动态语言都是解释型语言，其程序结构可以在运行中改变，不产生独立保存的目标程序。如：python、php、js、
• 静态语言其所有成分可在编译时确定。如：C、C++。C或C++中的指针变量可以是全局的也可以是局部的
• Lisp是函数式编程语言，Prolog是逻辑式程序语言
• 编译过程中为变量分配存储单元所用的地址是逻辑地址，程序运行时再映射为物理地址。
• 程序运行时的用户内存空间一般划分为代码区、静态数据区、栈区和堆区，其中栈区和堆区也称为动态数据区。全局变量的存储空间在静态数据区。
• 链表中的结点空间需要程序员根据需要申请和释放，因此，数据空间应采用堆存储分配策略。

面向对象

类对象消息

类

• 描述一组对象的共同行为和属性
• 类是对象的抽象，对象是类的具体化
• 类可以分为三种：实体类、接口类(边界)、控制类
  • 实体类的对象表示现实世界中真实的实体，如：人和物
  • 接口类的对象为用户提供一种与系统合作交互的方式，分为人和系统两大类
  • 控制类的对象用来控制活动流，充当协调者
• 有些类之间存在一般和特殊的关系，一般即父类，特殊即子类

对象

• 对象是基本的运行时的实体
• 一个对象通常由对象名、属性(状态）、方法三个部分组成

消息

• 对象之间进行的一种构造叫做消息

方法重载和重写

重载

• 重载(overloading) 是在一个类里面，方法名字相同，而参数不同。返回类型可以相同也可以不同。
  • 参数不同可以是：参数的个数不同、参数的类型不同、参数类型的顺序不同

重写

• 重写是子类对父类的允许访问的方法的实现过程进行重新编写, 返回值和形参都不能改变
• 重写的好处在于子类可以根据需要，定义特定于自己的行为。 也就是说子类能够根据需要实现父类的方法

封装继承多态

• 多态：不同的对象收到同一消息可以产生完全不同的结果，多态的实现受到继承的支持，利用类的继承的层次关系。
• 多态的类型
  • 参数多态：被称为最纯的多态
  • 包含多态：子类型化，即一个类型是另一个类型的子类型
  • 过载多态：同一个名字在不同的上下文中所代表的含义不同。

设计原则

• 单一责任原则：就一个类而言，应该仅有一个引起它变化的原因
• 开发封闭原则：可以拓展，不可以修改
• 里氏替换原则：子类必须能够替换掉他们的基类
• 依赖倒置原则：依赖于抽象，而不依赖于实现（细节）
• 接口分离原则：依赖于抽象，而不依赖于具体
• 共同重用原则：重用了包中的一个类，就要重用包中的所有类
• 共同封闭原则：一个变化若对一个包产生影响，则将对该包中的所有类产生影响

分析设计程序设计测试

分析（OOA）

• 5个活动：认定对象、组织对象、描述对象间的相互作用、确定对象的操作、定义对象的内部信息。

设计（OOD）

• 5个活动：识别类及对象。定义属性。定义服务。识别关系。识别包。

程序设计

• 选择合适的面向对象程序设计语言，将程序组织为相互协作的对象

测试

• 算法层：测试类中定义的每个方法
• 类层：测试封装在同一个类中的所有方法与属性之间的相互作用。
• 模板层：测试一组协同工作的类之间的相互作用
• 系统层：把各个子系统组装成完整的面向对象软件系统，在组装过程中同时进行测试。

知识产权

著作权和专利

著作权

• 也称为版权，是指作者对其创作的作品享有的人身权和财产权
• 人身权包括：发表权（有时间性），署名权，修改权，保护作品完整权

专利

• 两个或者两个以上的人分别就同样的发明创造申请专利的，专利权授给最先申请人。
• 各国主管机关依照本国法律授予的知识产权，只能在其本国领域内受法律保护

计算机软件著作权

• 主体指享有著作权的人，客体指计算机程序及计算机软件文档
  • 计算机程序包括：源程序和目标程序
  • 文档包括：程序设计说明书，流程图，用户手册
• 两个文件：著作权法和计算机软件保护条例
• 权利：人身权和财产权
• 人身权包括：发表权，署名权（开发者身份权）
• 保护期：50年（除署名权外）

职务作品和委托开发

职务作品

• 职务作品只享有署名权，其他的著作权属于该单位
• 个人作品要同时符号以下条件
  • 所开发的软件作品不是执行其本职工作的结果。
  • 开发的软件作品与开发者在单位中从事的工作内容无直接联系。
  • 开发的软件作品未使用单位的物质技术条件。

委托开发

• 委托开发软件著作权的归属与所签合同一致，若如何中未指明，则归属于受委托方

商业秘密权和商标

商业秘密权

• 指不为公众所知悉的、能为权利人带来经济利益、具有实用性并经权利人采取保密措施的技术信息和经营信息

商标权

• 我国商标权的保护期限自核准注册之日起10年内有效，但可以根据其所有人的需要无限地延长权利期限。

商标注册权

• 先注册先得，同一天注册的先使用先得，再不行就协商解决。

信息安全

信息安全包括5个基本要素:机密性、完整性、可用性、可控性与可审查性

防火墙

• 对通过受控干线的任何通信行为进行安全处理，如控制、审计、报警和反应等
• 防火墙工作层次越高，安全性越高，效率越低
• DMZ位于内网和外网之间，用于保存公用的服务器
• 通过在出口防火墙上配置ACL功能可以阻止外部未授权用户访问内部网络。
• 防火墙技术经历了包过滤、应用代理网关和状态检测技术三个发展阶段。
• 包过滤防火墙（透明，快）
  • 包过滤器处在网络层和数据链路层（即TCP和IP层)之间
  • 对用户完成透明，速度快
  • 每个IP包的字段都被检查，如：源地址、目的地址、协议、端口号等
  • 对包实习低水平控制，安全性低，不支持应用层协议
• 应用代理网关防火墙（难配置，慢）
  • 彻底隔离：内网用户对外网的访问变成防火墙对外网的访问，然后再由防火墙转发给内网用户
• 状态检测防火墙：结合了代理防火墙的安全性和包过滤防火墙的高速度等优点

病毒

• 病毒的特征：传播性、隐蔽性、感染性、潜伏性、触发性、破坏性等
• Worm表示蠕虫病毒、Trojan表示特洛伊木马、Backdoor表示后门病毒、Macro表示宏病毒
  • 宏病毒感染的对象主要是文本文档、电子表格等
  • 特洛伊木马：感染后会有未知程序试图建立网络连接
  • 蠕虫病毒:欢乐时光、熊猫烧香、红色代码、爱虫病毒、震网
• 冰河是木马软件，X卧底是木马病毒

网络攻击

• 入侵检测技术:专家系统、模型检测、简单匹配

常见的网络攻击

• 拒绝服务攻击（Dos攻击）:目的是使计算机或网络无法提供正常的服务
  • 拒绝服务攻击是不断向计算机发起请求来实现的
• 重放攻击:攻击者发送一个目的主机已经接受过的报文来达到攻击目的
  • 攻击者利用网络监听或者其他方式盗取认证凭据，之后再重新发送给认证服务器。主要用于身份认证过程,目的是破坏认证的正确性。
• Sql注入攻击:是黑客对数据库进行攻击的常用手段之一。
  • 没有对用户输入数据的合法性进行判断，使应用程序存在安全隐患。
  • 攻击者可以提交一段数据库查询代码，根据程序返回的结果，获得某些他想得知的数据，首先获取数据库的权限，就可获取用户账号和口令信息，以及对某些数据修改等。
• 口令入侵攻击:使用某些合法用户的账号和口令登录到目的主机，然后再实施攻击活动
• 特洛伊木马:被伪装成程序或游戏，当用户下载了带有木马的软件或附件时，这个程序就会向黑客发起连接请求，建立连接后黑客就实施攻击活动。
• 网络监听:攻击者可以接收某一网段在同一条物理通道上传输的所有信息，使用网络监听可以轻松截取包括账号和口令在内的信息资料
  • 防范网络监听最有效的方法是：数据加密
• IP欺骗攻击:产生的IP数据包为伪造的源IP地址，以便冒充其他系统或发件人的身份。
• 端口欺骗攻击:采用端口扫描找到系统漏洞从而实施攻击
• ARP攻击：通过伪造IP地址和MAC地址，造成无法跨网段通信

主动攻击：重放、IP地址欺骗、拒绝服务、系统干涉、修改数据命令

被动攻击：流量分析、会话拦截

网络安全

• SSL（安全套接层）：传输层安全协议，端口号是443
• TLS：传输层安全协议，是SSL3.0的后续版本
• SSH：在终端设备与远程站点之间建立安全连接的协议，建立在应用层和传输层基础上
• HTTPS：以安全为目标的HTTP通道，即使用SSL加密算法的HTTP
• MIME：是一个互联网标准，扩展了电子邮件标准 ，与安全无关
• PGP：是一个基于RSA公钥加密体系的邮件加密软件

计算机网络

计算机网络的分类

按范围分

• 局域网（LAN）、城域网（MAN）、广域网（WAN）、因特网

按拓扑结构分

• 总线型、星型、环型

七层网络体系结构（OSI）

• DHCP：使网络环境中的主机动态的获得IP地址、Gateway地址、DNS服务器地址等信息，并能够提升地址的使用率。
• 169.254.X.X是 Windows系统在DHCP信息租用失败时自动给客户机分配的IP地址。0.0.0.0是Linux的

TCP/IP协议族

• TCP/IP协议是Internet的基础和核心,从上而下分为：应用层、传输层、网际层、网络接口层
• 网际层协议：ARP、RARP、IP、ICMP
  • ARP：地址解析协议(Address Resolution Protocol, ARP)，ARP的作用是将IP地址转换为物理地址，以广播请求，单播响应
  • RARP：反地址解析协议(RARP)，RARP的作用是将物理地址转换为IP地址
  • IP协议是网际层的核心，通过路由选择将下一跳IP封装后交给网络接口层。IP数据报是无连接服务。
  • ICMP：ICMP是网际层的补充，可以回送报文。用来检测网络是否通畅（使用ping命令)。
• TCP和UDP
  • TCP：TCP(Transmission Control Protocol,传输控制协议)，为应用程序提供了一个可靠的、面向连接的数据传输服务。只能点到点的连接
  • UDP：用户数据报协议(User Datagram Protocol, UDP)是一种不可靠的、无连接的协议，可以保证应用程序进程间的通信。面向报文，没有拥塞控制，开销小，支持多种连接方式
  • TCP有助于提供可靠性，而UDP则有助于提高传输的高速率性。

IP地址和IPv6

IP地址

• IP地址的长度为32位，分为4段，每段8位，每段数字范围为0-255
• IP地址由两部分组成，一部门为网络地址，一部分为主机地址
  • 网络地址又被分为网络号和子网号（子网号是从主机地址借来的）
  • 主机地址全为1时称为广播地址，全0时为网络地址
• IP地址分为5类
  • A类：由1个字节的网络地址和3个字节的主机地址组成，网络地址的最高位必须是0，地址范围是1.0.0.1～126.255.255.254。可用的A类网络有126个，每个网络地址能容纳2^24-2个主机
  • B类IP地址。由2个字节的网络地址和2个字节的主机地址组成，网络地址的取同位必须是“10”，地址范围是128.0.0.0～191.255.255.254。可用的B类网络有16384个，每个网络能容纳65534个主机。
  • C类P地址。由3个字节的网络地址和1个字节的主机地址组成，网络地址的取同位必须是“110”，地址范围是192.0.1.1~223.255.255.254。可用的C类网络有2^21-2个个，每个网络能容纳254个主机。
  • D类IP地址。第一个字节以“1110”开始，是专门保留的地址。它并不指向特定的网络，目前这一类地址被用在多点广播(Multicast)中。多点广播地址用来一次寻址一组计算机，它标识共享同一协议的一组计算机。D类P地址的地址范围是224.0.0.1~239.255.255.254。
  • E类IP地址。以“1111”开始，为将来使用保留，仅做实验和开发用。

IPV6

• IPv6地址长度为128位，地址空间增大了2^96倍
• 简化了报文头部格式，字段只有8个，加快了报文处理速度

Internet服务及端口

• 公共端口号：0-1023
• DNS域名服务：DNS用的是UDP端口，端口号是53。
  • 协议名://主机名.域名.域名后缀.域名分类/目录/网页文件
• 远程登录服务：Telnet协议用的是TCP端口，端口号一般是23。他是不安全的
• 电子邮件服务：传送协议SMTP和接收邮件的POP3，两者均利用TCP端口
  • S 口号是25 ，只能传送ASCII格式的报文
  • POP3所用的端口号是110，用CS模式进行通信，
• WWW服务：WWW服务（HTTP）是一种交互式图形界面的Internet服务，具有强大的信息连接功能。WWW用的是TCP端口，端口号是80。
• 文件传输服务：FTP在客户机与服务器的内部建立两条TCP连接
  • 一条是控制连接，主要用于传输命令和参数(端口号是21)
  • 另一条是数据连接，主要用于传送文件(端口号是20)。

Windows命令

windows

• ipconfig:显示所有网络适配器的IP地址、子网掩码和缺省网关值
• ipconfig/release: DHCP客户端手工释放IP地址
• ipconfig/flushdns:清除本地DNS缓存内容
• ipconfig/displaydns:显示本地 DNS内容
• ipconfig/registerdns: DNS客户端手工向服务器进行注册
• ipconfig/all:显示所有网络适配器的完整TCP/IP配置信息，包括DHCP服务是否已启动
• ipconfig/renew: DHCP客户端手工向服务器刷新请求（重新申请IP地址)
• netstat：显示网络连接、路由表和网络接口信息
• nslookup：用于查询Internet域名信息
• tracert：是路由跟踪实用程序，用于确定P数据包访问目标所采取的路径

路由

路由类型

路由类型	说明
直连网络ID	用于直接连接的网络，Interface(或next hop）可以为空
远程网络ID	用于不直接连接的网络，可以通过其他路由器到达这种网络Interface字段是本地路由器的P地址
主机路由	到达特定主机的路由，子网掩码为255.255.255.255
默认路由	无法找到确定路由时使用的路由，目标网络和网络掩码都是0.0.0.0
持久路由	利用route add -p命令添加的表项，每次初始化时，这种路由都会加入Windows的注册表中，同时加入路由表

• 当Windows服务器收到一个IP数据包时，先查找主机路由，再查找网络路由(直连网络和远程网络)，这些路由查找失败时，最后才查找默认路由。

路由的管理距离

• 如果路由器收到了由多个路由协议转发的、关于某个目标的多条路由，则比较各个路由的管理距离，并采用管理距离小的路由来源提供的路由信息。

其他

• 广播域：网络中的某一设备同时向网络中所有的其它设备发送数据，这个数据所能广播到的范围
• 冲突域：两台计算机在同时通信时会发生冲突，就是一个冲突域
• 物理层不能隔离广播域和冲突域
• 数据链路层不能隔离广播域，但能隔离冲突域
• 网络层能隔离广播域和冲突域
• 集线器是一种多端口的中继器 ，交换机是多端口的网桥
• 蓝牙的覆盖范围是最小的，通信距离是最短的
• DNS域名查询的次序是:本地的hosts文件→本地DNS缓存→本地DNS服务器→根域名服务器。
• 主域名服务器在接收到域名请求后，查询顺序是：本地缓存→本地hosts文件→本地数据库→转发域名服务器。
• 三网合一：电信网、广播电视网、互联网
• 网络的可用性：用户可利用网络时间的百分比
• IE浏览器的安全级别：受限站点 > Internet >本地Internet > 可信站点
• 人耳能听到声音频率范围：20Hz-20000Hz

操作系统

操作系统的地位

进程

• 进程管理也称处理机管理。在多道程序批处理系统和分时系统中有多个并发执行的程序
• 进程是资源分配和独立运行的基本单位。
• 进程管理重点需要研究诸进程之间的并发特性，以及进程之间相互合作与资源竞争产生的问题。

程序顺序执行

• 特征：顺序性、封闭性、可再线性
• 前趋图
  • PV操作
    • P操作在结点执行前（-1操作），V操作在结点执行后（+1操作）
  • 前趋图中有n个箭头就有n个信号量S

程序并发执行

• 特征：失去了程序的封闭性，程序和机器的执行程序的活动不再一一对应，并发程序间的相互制约性。

三态模型

• 运行：有cpu和资源
• 就绪： 没有cpu但有资源
• 阻塞：cpu和资源都没（正在等待某一事件（如IO）发生而暂时停止运行）

同步和互斥

• 同步是合作进程间的直接制约问题
• 互斥是申请临界资源进程间的间接制约问题。
  • 临界区管理的原则：有空即进、无空则等、有限等待、让权等待

进程资源图

• 先分配，再申请

文件目录和多级索引结构

文件目录

• 文件控制块中包含以下三类信息：基本信息类、存取控制信息类和使用信息类。
• 如果文件目录损坏了将会对系统产生很大的影响
• 全文件名就是绝对路径 （要从根路径/开始）

多级索引结构

• 直接地址索引、一级间接地址索引、二级间接地址索引
• 直接地址索引直接指向磁盘数据块
• 间接地址索引指向的是磁盘索引块
• 磁盘索引块指向磁盘数据块
• 用磁盘索引块大小/地址项大小，即可得每个索引块所能容纳的数据块
• 地址项和磁盘数据块一般都是从0开始

调度算法

磁盘（移臂）调度算法

• 先来先服务（FCFS）：按请求访问者的先后次序启动磁盘驱动器
• 最短寻道时间优先（SSTF）：让离当前磁道最近的请求访问者启动磁盘驱动器
• 电梯调度算法或扫描算法（SCAN）：总是从磁头当前位置开始，沿磁头的移动方向去选择离当前磁头最近的那个柱面的请求。如果沿磁头的方向无请求访问时，就改变磁头的移动方向。
• 循环扫描算法或单向扫描算法（CSCAN）
• 注：平均寻道长度=磁头移动总数/请求总次数

旋转调度算法

• 每个记录的读取时间=磁盘旋转速度/记录的总数
• 优化处理后的时间：扇区数*（每个记录的读取时间+每个记录的处理时间）

在磁盘调度管理中和访问不同柱面的信息时，通常应先进行移臂调度，再进行旋转调度

在访问同一磁道的信息时，只需要进行旋转调度。

缓冲区和存储管理

缓冲区

• 单缓冲区
  • 时间=（输入时间 + 传送时间）* 作业个数+处理时间
• 双缓冲区
  • 时间=（输入时间 * 作业个数）+传送时间+处理时间

存储管理

• 分页存储管理
  • 进制数的第一个数的物理块号+后三个数=物理地址
• 段页式存储管理
  • 2^(头-尾+1)

死锁和线程

死锁

• 死锁的发生
  • 当m>=n*(K-1)+1时不会死锁，m为资源数量，n为进程数量，k为每个进程需要的资源数量
• 死锁避免资源分配
  • 剩余可用资源数=可用资源数-已分配资源数
  • 仍需资源数=最大需求量-已分配资源数
    • 死锁预防
      • 预先静态分配法：预先分配所需资源，保证不等待资源。
      • 资源有序分配法：把资源分类按顺序排列
• 死锁避免
  • 银行家算法

线程

• 传统的进程有两个基本属性：可拥有资源的独立单位，可独立调度和分配的基本单位。引入线程的原因是较大的时空开销。
• 线程作为调度和分配的基本单位，进程作为独立分配资源的单位。
• 线程是进程中的一个实体，是被系统独立分配和调度的基本单位。线程基本上不拥有资源，只拥有一点运行中必不可少的资源（如程序计数器、一组寄存器和栈)，它可与同属一个进程的其他线程共享进程所拥有的全部资源
• 线程也具有就绪、运行和阻塞3种基本状态。由于线程具有许多传统进程所具有的特性，故称为“轻型进程”，传统进程称为“重型进程”
• 线程可创建另一个线程，同一个进程中的多个线程可并发执行。
• 线程分为用户级线程和内核支持线程。
  • 用户级线程不依赖于内核，该类线程的创建、撤销和切换都不利用系统调用来实现;
  • 内核支持线程依赖于内核，即无论是在用户进程中的线程，还是在系统中的线程，它们的创建、撤销和切换都利用系统调用来实现。某些系统同时实现了两种类型的线程。

数据库

• 闭包：找只有左边的字符看能不能推出U（所有属性），不行再加左右都有的字符，直到推出U
• 派生属性：派生属性可以从其他属性得来。
• 复合属性：复合属性可以细分为更小的部分

三级模式两级映像

三级模式

• 外模式(用户模式 子模式)=》视图、概念模式
• 概念模式(模式)=》基本表、逻辑
• 内模式(存储模式)=》存储文件、索引、物理

两级映像

• 外模式/模式映像(逻辑独立性)
• 模式/内模式映像(物理独立性)

关系模式

• X->Y Y依赖于X 如果Y不包含X，那么是非平凡依赖(正常) 有包含则是平凡
• X–f–>Y Y完全函数依赖 X里面的子集都不可以单独推出Y 一推一 一定是完全
• X–p–Y Y部分(局部)函数依赖 X里面的子集就可以推出来Y
• X->Y Y->Z 得到X->Z 传递函数依赖
• 伪传递率：若X->Y,WY->Z,则XW->Z
• 元组(行)一条记录、属性(列)第一行是属性名，后面是属性值(数据项)
• 候选码(候选键)能够唯一地标识一个元组
• 主码(主键)候选码中，从中选一个作为主码(有时候主码等于候选码)
• 超键是候选键的超集，因为候选键是最小的超键，即不包含任何冗余属性的超键。
• 主属性:包含在候选码中的属性，不包含为非主属性
• 外码：不是本关系中的主码，确是另外一个关系的主码
• 全码：所有属性组成才是这个关系模式的候选码
• 超码:在原有的候选码的基础上加一个属性作为候选码
• 关系模型由关系数据结构、关系操作集合、关系完整性约束
• 完整性约束
  • 实体完整性（主键）
  • 参照完整性（外键）
  • 用户自定义完整性
• 推理规则

关系代数

• 笛卡尔积
  • 列相加，行相乘
• 自然连接
  • 列去重，行找同
• 专门的关系运算符:选择(出来满足的行)投影(出来列)连接除
  • 都要先笛卡尔积后在筛选 theat连接 等值连接(符号=)
    • 自然连接
    • 先笛卡尔积后，挑共同属性的列当列都相等的时候，然后去除其中一个关系中的列，剩下的就是
    • 左(右)外连接，先自然连接，然后左(右)记录保存，没有的为null
    • 全外连接，先自然连接后左右连接
  • 转SQL语句
    • π 投影就是select xx from xx
    • σ 选择就是where xxx
    • 笛卡尔积 select xxx from R,S
    • 自然连接 select xxx from R,S where xx and xx 把一样的列杀掉

范式

求候选码和主属性（R{BC->E，DC->B，D->A，B->G，D->E，E->G，B->C}）

1. 先找出箭头左边的集合，再找出箭头右边的集合，把她两相同的元素划掉
   • 左{B、C、D、E}、右{E、B、A、G、C}
2. 划掉后左边剩下的集合一定是候选码，右边剩下的集合一定不是候选码
   • D一定是，A和G一定不是
3. 看看现在的部分候选码能不能推出全集U
   • D可以推出：A、E、G（发现不能推出全集U）
4. 若能则现在的部分候选码为候选码，若不能则将左右两边相同的元素拿出来
   • 左右相同的元素(B、C、E)
5. 将部分候选码与左右相同的元素依次组合，看看组合后能不能推出全集U
   • DB可以推出：A、E、G、C（可以推出U，所以DB为候选码）
   • DC可以推出：A、E、G、B（可以推出U，所以DC为候选码）
   • DE可以推出：A、G（不能推出U）
6. 所有候选码的元素的集合为主属性，其他为为主属性
   • 主属性（B、C、D）、非主属性（A、E、G）

第一范式

• 每个原子项都是不可分割的数据项

第二范式[2NF]

• 2NF在1NF的基础之上，消除了非主属性对于主属性的部分函数依赖
• 简单的说，是表中的非主属性必须完全依赖于主属性(所谓完全依赖是指不能存在仅依赖候选键一部分的属性)
• 学生基本信息表(学号，身份证号，姓名)中，当然学号属性取值是唯一的。而(学号，身份证号)->(姓名)， (学号)->(姓名)， (身份证号)->(姓名)所以姓名部分函数依赖于(学号，身份证号) ;

第三范式[3NF)

• 第三范式(3NF)就是指表中的所有数据元素不但要能唯一地被主关键字所标识而且它们之间还必须相互独立,不存在其他的函数关系。
• 也就是说，在2NF的基础上消除传递函数依赖
• 所谓传递函数依赖，指的是如果存在“A一B一C”的决定关系，则C传递函数依赖于A

第四范式[4NF]

• 第四范式是 消除表中的多值依赖以解决信息冗余，达到“一事一地”也就是一对一的关系（左边都是超键）

锁

排它锁

• 若事务T对数据对象 A 加上X锁，则只允许T读取和修改A
• 其他事务都不能再对 A加任何类型的锁，直到T释放 A 上的锁

共享锁

• 若事务T对数据对象 A 加上S 锁，则只允许T读取 A，但不能修改 A，其他事务只能再对 A 加S 锁，直到T释放 A 上的S 锁
• 这就保证了其他事务可以读 A，但在T释放 A 上的 S 锁之前不能对 A 进行任何修改。

分布式数据库

• 分片透明: 指用户或应用程序不需要知道逻辑上访问的表具体是怎么分块存储的
• 复制透明:指采用复制技术的分布方法，用户不需要知道数据是复制到哪些节点，如何复制的。
• 位置透明:指用户无须知道数据存放的物理位置
• 逻辑透明:指用户或应用程序无需知道局部场地使用的是哪种数据模型
• 共享性:指数据存储在不同的结点数据共享
• 自治性:指每结点对本地数据都能独立管理
• 可用性:指当某一场地故障时，系统可以使用其他场地上的副本而不至于使整个系统瘫痪
• 分布性:指数据在不同场地上的存储

事务和视图

事务

• 原子性(要么都做要么都不做)
• 一致性(一个一致性状态变成另外一个一致性状态)
• 隔离性(相互隔离，多个事务执行，对其他事务是不可见的)
• 持久性(事务成功提交，对数据库操作也永久有效)

视图

• 视图是一个或者从多个基本表或视图中导出的表，是一个虚表
• 创建 create view 视图名 as select xxx
• 最后如果加了这句 with check option后 对视图就是update insert delete的时候要遵守 定义视图的时候where后的条件所有条件

数据库设计

• 需求分析(了解用户需求确定系统边界)
  • 作为概念结构设计的依据、建立需求说明文档、数据字典、数据流图
• 概念设计(E-R图)
• 逻辑设计(关系模式、关系规范化)
  • 将E-R图转换为指定的数据模型、确定完整性约束和确定用户视图

结构化开发

• 模块化用的是“分而治之”的思想

耦合

耦合是模块之间的相对独立性的度量

• 无直接耦合：指两个模块之间没有直接的关系
• 数据耦合：指两个模块之间有调用关系，传递的是简单的数据值相当于高级语言中的值传递。
• 标记耦合：指两个模块之间传递的是数据结构
• 控制耦合：指一个模块调用另一个模块时，传递的是控制变量，被调用模块通过该控制变量的值有选择地执行模块内的某一功能。因此，被调用模块应具有多个功能，哪个功能起作用受调用模块控制。
• 外部耦合：模块间通过软件之外的环境送结（如IO将模块耦合到特定的设备、格式、通信协议上）时称为外部耦合。
• 公共耦合：指通过一个公共数据环境相互作用的那些模块间的耦合。
• 内容耦合：当一个模块直接使用另一个模块的内部数据

内聚

内聚是对一个模块内部各个元素彼此结合的紧密程度的度量。

• 偶然内聚(巧合内聚)：指一个模块内的各处理元素之间没有任何联系
• 逻辑内聚：指模块内执行若干个逻辑上相似的功能,通过参数确定该模块完成哪一个功能。
• 过程内聚。指一个模块完成多个任务，这些任务必须按指定的过程执行。
• 通信内聚指模块内的所有处理元素都在同一个数据结构上操作，或者各处理使用相同的输入数据或者产生相同的输出数据。
• 功能内聚。这是最强的内聚，指模块内的所有元素共同作用完成一个功能,缺一不可。

设计原则

1. 分解-协调原则：整个系统是一个整体，具有整体目的和功能，但这些目的和功能的实现又是由相互联系的各个组成部分共同工作的结果。
2. 自顶向下的原则：首先抓住系统总的功能目的，然后逐层分解，即先确定上层模块的功能，再确定下层模块的功能。
3. 信息隐蔽、抽象的原则：上层模块只规定下层模块做什么和所属模块间的协调关系，但不规定怎么做，以保证各模块的相对独立性和内部结构的合理性
4. 一致性原则：要保证整个软件设计过程中具有统一的规范、统一的标准和统一的文件模式等。
5. 明确性原则：每个模块必须功能明确、接口明确，消除多重功能和无用接口。
6. 模块之间的耦合尽可能小，模块的内聚度尽可能高。
7. 模块的扇入系数和扇出系数要合理。
8. 模块的规模适当
9. 模块的作用范围在控制范围内

系统文档

• 用户与系统分析人员：可行性研究报告、总体规划报告、系统开发合同和系统方案说明书。
• 系统开发人员与项目管理人员：系统开发计划(包括工作任务分解表、PERT图、甘特图和预算分配表等）
• 系统测试人员与系统开发人员：系统方案说明书、系统开发合同、系统设计说明书和测试计划。
• 系统开发人员与用户：用户手册和操作指南。
• 系统开发人员与系统维护人员：系统设计说明书和系统开发总结报告。
• 用户与维修人员：系统运行报告和维护修改建议。

数据流图

• 数据流图中的基本图形元素包括：数据流、加工 、数据存储、外部实体
  • 外部实体:当前系统之外的人、物、外部系统
  • 加工:将输入数据处理后得到输出数据，一个加工至少有一个输入数据流和一个输出数据流
  • 数据存储:存储数据和提供数据
  • 数据流：表示数据的流向，起点或终点必须有一个是加工
• 数据流、加工和数据存储用于构建软件系统内部的数据处理模型
• 用数据流图来建立系统的逻辑模型。顶层数据流图描述了系统的输入与输出
• 判断数据流图错误的依据
  • 数据流的两端必须有一个是加工
  • 加工最少要有一个输入数据流和一个输出数据流
  • 数据流名称在上午题中不能重名

数据字典

• 数据字典就是为数据流图中的每个数据流、文件、加工，以及组成数据流或文件的数据项做出说明。
• 数据字典有以下4类条目：数据流、数据项、数据存储和基本加工。
  • 数据项是组成数据流和数据存储的最小元素。
  • 源点、终点不在系统之内，故一般不在字典中说明。
• 加工逻辑也称为“小说明”。常用的加工逻辑描述方法有结构化语言、判定表和判定树3种。
  • 结构化语言介于自然语言和形式化语言之间，分为外层和内层
    • 外层：用来描述控制结构，采用顺序、选择、重复3种基本结构
    • 内层：一般采用祈使语句的自然语言短语
  • 判定表：在有些情况下，数据流图中某个加工的一组动作依赖于多个逻辑条件的取值。这时，用自然语言或结构化语言都不易于清楚地描述出来，而用判定表能够清楚地表示复杂的条件组合与应做的动作之间的对应关系。

其他

• 模块
  • 传入模块：取得数据或输入数据，经过某些处理,再将其传送给其他模块
  • 传出模块：输出数据,在输出之前可能进行某些处理，数据可能被输出到系统的外部,或者会输出到其他模块进行进—步处理。
  • 变换模块：从上级调用模块得到数据,进行特定的处理,转换成其他形式,在将加工结果返回给调用模块。
  • 协调模块：—般不对数据进行加工，主要是通过调用、协调和管理其他模块来完成特定的功能。
• 结构化设计
  • 体系结构设计：定义软件的主要结构元素及其关系。
  • 数据设计：基于实体联系图确定软件涉及的文件系统的结构及数据库的表结构。
  • 接口设计：描述用户界面，软件和其他硬件设备、其他软件系统及使用人员的外部接口，以及各种构件之间的内部接口。
  • 过程设计：确定软件各个组成部分内的算法及内部数据结构
• 结构化开发不适合解决大规模的、特别复杂的项目，而且难以适应需求的变化。
• 结构化分析由：数据流图、数据字典、加工逻辑说明组成
• 系统测试阶段的测试目标来自需求分析
• 人机交互“黄金三原则”包括:置于用户控制之下、减少用户的记忆负担、保持界面的一致性。
• 结构图的基本成分：模块、调用、通信、控制

软件工程

软件工程的基本要素：方法、工具、过程

能力模型

CMM（能力成熟度模型）

• CMM将软件过程改进分为以下5个成熟度级别。
  • 初始级(Initial）：软件过程的特点是杂乱无章，有时甚至很混乱，几乎没有明确定义的步骤
  • 可重复级(Repeatable)：建立了基本的项目管理过程和实践来跟踪项目费用,进度和功能特性，有必要的过程准则来重复以前在同类项目中的成功。
  • 已定义级(Defined)：所有项目都采用根据实际情况修改后得到的标准软件过程来开发和维护软件。使用标准开发过程或方法论构建或集成系统，管理和工程两方面的软件过程已经文档化
  • 己管理级(Managed)：管理层寻求更主动地应对系统的开发问题，制定了软件过程和产品质量的详细度量标准，对软件过程和产品都有定量的理解与控制。
  • 优化级(Optimized)：连续地监督和改进标准化的系统开发过程，加强了定量分析，通过来自过程质量反馈和来自新观念、新技术的反馈使过程能不断持续地改进。

CMMI（能力成熟度集成模型）

• 阶段性模式
  • 初始的：过程不可预测且缺乏控制。
  • 已管理的：为项目服务。
  • 已定义的：为组织服务。
  • 定量管理的：过程已度量和控制。
  • 优化的：集中于过程改进。
• 连续性模式
  • CL0(未完成的)
  • CL1(已执行的)：将可标识的输入工作产品转换成可标识的输出工作产品
  • CL2(已管理的)：已管理
  • CL3(已定义级的)：已定义。关注过程的组织标准化和部署
  • CL4(定量管理的)：可定量管理
  • CL5(优化的)：使用量化（统计学）手段改变和优化过程域

开发模式

瀑布模型（需求明确）

• 瀑布模式适合开发需求明确的，需求大致固定不会随意变更的系统
• V模式（瀑布模式的变体）的关键字在于质量保证活动和沟通，基本问题逐步细化

增量模式（快速构建）

• 增量模型拥有瀑布模型的所有优点，它主要的特点是可以快速构造可运行的产品，第一个可交付版本所需要的成本低，时间少。但不容易划分

原型模型（需求模糊 规模小）

• 适合需求模糊不清且系统规模不大

螺旋模型（风险分析 规模大）

• 螺旋模型的特点是加入了风险分析，适合大规模高风险的，需求变化的系统

喷泉模型（面向对象）

• 以用户需求为动力，适合于面向对象的开发方法，具有迭代性和无间隙性，不利于项目的管理

统一过程(UP)模型

• 用例和风险驱动，以架构为中心，迭代并且增量
• 起始阶段：生命周期目标。产生的主要工作产品有构想文档
• 精华阶段：生命周期架构。开行需求分析和架构演进
• 构建阶段：初始运作功能。构建阶段关注系统的构建，产生实现模型
• 移交阶段：产品发布。产生软件增量
• 产生阶段

敏捷开发

• 尽可能早地、持续地对有价值的软件的交付
• 极限编程(XP)
  • XP是一种轻量级（敏捷)、高效、低风险、柔性、可预测的、科学的软件开发方式
  • 4大价值观：沟通、简单性、反馈和勇气。
  • 5个原则：快速反馈、简单性假设、逐步修改、提倡更改和优质工作。
  • 12个最佳实践
    • 计划游戏（快速制定计划、随着细节的不断变化而完善)
    • 小型发布(系统的设计要能够尽可能早地交付)
    • 隐喻（找到合适的比喻传达信息)
    • 简单设计(只处理当前的需求,使设计保持简单)
    • 测试先行(先写测试代码,然后再编写程序)
    • 重构（重新审视需求和设计，重新明确地描述它们以符合新的和现有的需求)
    • 结对编程
    • 集体代码所有制
    • 持续集成（可以按日甚至按小时为客户提供可运行的版本)
    • 每周工作40个小时
    • 现场客户
    • 编码标准。
• 水晶法
  • 水晶法认为每一个不同的项目都需要一套不同的策略、约定和方法论
• 并列争求法（Scrum)
  • 并列争求法使用迭代的方法，其中，把每30天一次的迭代称为一个“冲刺”
• 敏捷统一过程(AUP)
  • 采用“在大型上连续”以及在“在小型上迭代“的原理。
  • 采用经典的UP阶段性活动（初始、精化、构建和转换)
  • AUP迭代的活动：建模，实现，测试，部署，配置及项目管理，环境管理

开发过程

需求分析：指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。

• 功能需求：考虑系统要做什么，在何时做，在何时以及如何修改或升级。
• 性能需求：考虑软件开发的技术性指标。如：存储容量限制、执行速度、响应时间、吞吐量
• 数据需求：考虑输入、输出数据的格式，接收、发送数据的频率，数据的准确性和精度。
• 其他：环境需求、界面需求、文档需求、资源使用需求、安全保密要、可靠性要求、软件成本消耗与开发进度需求、其他非功能性需求

概要设计

• 包括：模块、接口、数据结构、数据块

详细设计

• 包括：数据结构、算法、数据块

测试

系统测试

• 成功的测试是发现了至今尚未发现的错误，以最少的人力和时间发现潜在的各种错误和缺陷，系统测试是保证系统质量和可靠性的关键步骤
• 测试原则
  • 应尽早并不断地进行测试。
  • 测试工作应该避免由原开发软件的人或小组承担
  • 在设计测试方案时，不仅要确定输入数据，而且要根据系统功能确定预期输出结果
  • 不仅要设计有效、合理的输入条件，也要包含不合理、失效的输入条件
  • 不仅要检验程序是否做了该做的事，还要检验程序是否做了不该做的事
  • 严格按照测试计划来进行，避免测试的随意性。
  • 妥善保存测试计划、测试用例
  • 测试例子都是精心设计出来的，可以为重新测试或追加测试提供方便
  • 系统测试阶段的测试目标来自于需求分析阶段。

单元测试（模块测试）

• 侧重于模块中的内部处理逻辑和数据结构。如果选用机器测试，一般用白盒测试法
• 检查特征：模块接口、局部数据结构、重要的执行路径、出错处理、边界条件
• 测试过程：驱动模块、桩模块（存根模块）

集成测试

• 自顶向下集成不需要驱动模块，自底向上不需要桩模块
• 回归测试：有助于保证变更不引入无意识行为或额外的错误
• 冒烟测试：一种常用的集成测试方法

测试方法

• 静态测试
  • 人工检测
  • 计算机辅助静态分析
• 动态测试：动态测试是指通过运行程序发现错误。

黑盒测试（功能测试）

• 常用的黑盒测试技术有等价类划分、边界值分析、错误推测和因果图等

白盒测试（结构测试）

• 根据程序的内部结构和逻辑来设计测试用例
• 白盒测试常用的技术是逻辑覆盖、循环覆盖和基本路径测试
• 逻辑覆盖
  • 语句覆盖：选择足够的测试数据，使被测试程序种的每条语句至少执行一次
  • 判定（分支）覆盖：每个判断的取真分支和取假分支至少经历一次
  • 条件覆盖：判定表达式的所有条件都要最少取得一真一假
  • 判定/条件覆盖：要同时满足判定覆盖和条件覆盖
  • 条件组合覆盖：判定表达式的所有条件的真假不同组合必须都有，两个条件就是四种组合
  • 路径覆盖：覆盖被测试程序中所有可能的路径

McCabe度量法

• 环路复杂度V(G)=m-n+2=闭合区域+1
• m是G中的有向弧数（箭头），n是G中的节点数。
• 代码行数是度量软件复杂性的一个主要参数

维护

系统可维护性评估指标

• 可理解性、可测试性、可修改性

软件维护

• 正确性维护：改正在系统开发阶段已发生而系统测试阶段尚未发现的错误
• 适应性维护：使应用软件适应信息技术变化和管理需求变化而进行的修改
• 完善性维护：这是为扩充功能和改善性能而进行的修改
• 预防性维护：为了改进应用软件的可靠性和可维护性

图

Gantt图

• 不能清晰地反映出各任务之间的依赖关系
• 不能清晰地确定影响进度的关键任务
• 清晰地描述每个任务从何时开始到何处结束，任务的进展情况以及各个任务之间的并行性

PERT图（计划图）

• 最早时刻：表示在此时刻之前从该事件出发的任务不可能开始
  • 在关键路径上，从开始到该任务的最早执行的时间，如：FG最早开始时间为AD＋DF（关键路径)=18
• 最迟时刻（最晚开始时间）：表示从该事件出发的任务最迟必须在此时刻开始
  • 关键路径的总时间-反向得出该任务的时间，如：FG的最晚开始时间为46-（FG+GJ）=36
• 松弛时间（最多可以晚）（Slack Time)，表示在不影响整个工期的前提下，任务可以被推迟完成的最大时间
  • 第一种求法：最晚开始时间-最早开始时间，如：FG的松弛时间为36-18=18
  • 第二种求法：关键路径的总时间-包含该任务的关键路径花的时间，如FG的松弛时间为46-28=18

• 关键路径：做大权值和路径

风险

• 风险的特性：不确定性和损失
• 风险识别：系统化地指出对项目计划（估算、进度、资源分配等）的威胁
• 风险测试：风险发生的可能性或概率
• 风险评估：定义风险参照水准
• 风险优先级：通常根据风险暴露设定
• 风险控制
  • 风险控制的目的是辅助项目组建立处理风险的策略
  • 方法：风险避免、风险监控、RMMM计划
    • RMMM计划将所有风险分析工作文档化

其他

软件模型ISO/IEC9126

• ISO/IEC9126软件模型:第一层质量特性，第二层质量子特性，第三层度量指标

软件文档

• 编写高质量文档可以提高软件开发的质量
• 文档也是软件产品的一部分，没有文档的软件就不能称之为软件。
• 软件文档的编制在软件开发工作中占有突出的地位和相当大的工作量高质量文档对于软件产品的效益有着重要的意义
• 总的来说，软件文档只好不坏，选项中说软件文档不好的就是不正确的

软件配置管理

• 软件配置管理其主要目标包括:变更标识、变更控制、版本控制、确保变更正确的实现、变更报告、
• 两个不同的版本
  • 软件配置管理其主要内容包括：版本管理、配置支持、变更支持、过程支持、团队支持、变化报告、审计支持。
  • 软件配置管理其主要内容包括：软件配置标识、变更管理、版本控制、系统建立、配置审核、配置状态报告。
• 核心是：版本、变更、配置、过程、变化、团队、审计、系统
• 配置数据库的三类：开发库，受控库，产品库

软件评审

• 设计的规格说明书符合用户的要求称为设计质量
  • 评价软件的规格说明是否合乎用户的要求
  • 可靠性:是否能避免输入异常、一间失效及软件失效所产生的失效
  • 评审软件是否有复用性、可测试性、可修改性、可扩充性、可互换性、可移植性
  • 评审性能，保密措施、操作特性实现情况
• 程序按照设计规格说明所规定的情况正确执行称为程序质量
  • 软件本身的结构、运行环境的接口以及变更带来的影响而进行的评审活动
  • 结构：功能结构、功能的通用性、模块的层次(静态)、模块结构、处理过程的结构
    • 模块结构：控制类结构、数据流结构、模块结构与功能结构直接的对应消息
  • 与运行环境的结构
    • 与硬件的接口、与用户的接口
  • 正式技术评审的目标发现软件中的错误

软件工具

• 用来辅助软件开发、运行、维护、管理和支持等过程中的活动的软件
• 软件开发工具
  • 需求分析工具、设计工具、编码与排错工具、测试工具
• 软件维护工具
  • 版本控制工具、文档分析工具、开发信息库工具、逆向工程工具、再工程工具

容错技术

• 实现容错的主要手段是冗余
• 结构冗余(静态动态冗余、混合冗余)、信息冗余、时间冗余、冗余附加技术（不包括关键程序和数据的冗余存储和调用）

可靠性、可用性、可维护性

• 可靠性：无失效运作的概率，MTTF/(1+MTTF)
• 可用性：正确运作的概率，MTBF/(1+MTBF)
• 可维护性：完成维护活动的概率，1/(1+MTTR)

沟通路径

• 沟通路径无主程序员的公式 n x (n-1) / 2，就是求和公式
• 有主程序员n-1，其中n为程序员的个数

COCOMO估算模型

• COCOMO模型：是一种精确的、易于使用的成本估算模型
  • 基本COCOMO模型是静态单变量模型
  • 中级COCOMO模型是静态多变量模型，分为系统和部件
  • 详细COCOMO模型，分为系统、子系统和模块
• COCOMOII模型(规模估算选择)
  • 应用组装模型(对象点)
  • 早期设计阶段模型(功能点)
  • 体系结构阶段模型(代码行)

UML

UML构造快

• 事物 是对模型中最具有代表性的成分的抽象
  • 结构事物(名词静态)：类、接口、协作、用例、主动类、构件、制品、结点
  • 行为事物(动词动态):交互(消息)、状态机(状态)、活动(动作)
  • 分组事物(组织部分):包
  • 注释事物(解释部分):注解
• 关系 把事物结合在一起
• 图 聚集了相关的事物
• UML接口可用于声明对象类所需要的服务

UML的四种关系

• 依赖:一个独立事物A发生变化会影响另一个依赖事物B的语义，B—->A（用虚线表示，B依赖于A）
• 关联：关联是一种结构关系，描述了一组链，链是对象之间的连接
  • 关联是一条直线，在上面可以标注多重度(重复度)和角色 0..1— 0..* 一对多
  • 聚集：特殊的类型关联，描述部分和整体间的结构关系
    • 聚合：—◇ 部分整体生命周期不一致，整体消失，部分仍然存在，部分可以脱离整体存在
    • 组合：—◆ 部分整体生命周期一致，整体消失，部分也消失，部分不可以脱离整体存在
  • 关联的多重度：一个类的实例能够与另一个类的多少个实例相关联
  • 多对多需要创建关联类(新类)
• 泛化：子类 —▷父类，子元素(特殊元素)的对象可替代父元素(一般元素)的对象(一个类与多个类的关系)，子共享了父的结构和行为
• 实现：类 – – -▷接口 ，一个类元指定了由另一个类元保证执行的契机。

UML的图

图	关系	图的特征
类图	一组对象、接口、协作和它们之间的关系。是最常见的图	类、接口、关系
对象图	某一时刻一组对象之间的关系。描述了实例的静态快照	对象跟链
用例图	一组用例与参与者之间关系 。系统在它的周边环境的语境中所提供的外部可见服务	椭圆、小火柴人
序列图（顺序图）	以时间顺序组织的对象之间的交互活动，展示了一个用例和多个对象的行为	虚线、瘦高的矩形
通信图（协作图）	强调收发消息的对象的结构组织(展现了对象之间的消息流及其顺序)	链的旁边有消息（箭头），消息有序号
状态图	一个状态机，由状态、转换、事件、和活动组成 。	初态(黑圆点)、终态(黑圆点加一个圆
活动图	一种特殊的状态图，从一个活动到另一个活动的流程。	初态、终态、分支、合并、分岔和汇合
构件图（组件图）	一组构件之间的组织和依赖。静态实现视图，与类图相关。	哑铃、半圆、整圆
部署图	软件与硬件之间的关系。在实施阶段使用，用来对面向对象的物理方面建模的方法，(立体图)静态与构件图相关。	立体图

类图

• 展现一组对象、接口、协作和它们之间的关系，是最常见的图
• 类图中通常包括：类（类名，属性，方法）、接口、协作、关系（依赖，泛化，关联）
• 修饰符 : ＋共有的 – 私有的 # 受保护的 ~包的
• 用于对系统的静态设计视图建模，视图支持功能需求，三种建模方式使用类图
  • 对系统的词汇建模、对简单的协作建模、对逻辑数据库模式建模

对象图

• 展现某一时刻一组对象以及它们之间的关系，描述了实例的静态快照
• 一般包括对象跟链
• 图就 对象名:类名和属性(一般都有值了) ，没有方法

用例图

• 展现了一组用例、参与者以及它们的关系 。系统在它的周边环境的语境中所提供的外部可见服务
• 用例用椭圆表示，参与者用一个小人表示
• 关系
  • 用例和用例之间有扩展关系和包含关系
    • 包含关系《include》：A基本用例(包含用例)- – ->B被包含用例，执行A之前必定要执行B
    • 扩展关系《extend》：A扩展用例(特殊的情况)- – – >基本用例，一个用例执行的时候，可能会发生一些特殊的情况或可选的情况，这种情况就是这个用例的扩展用例
  • 用例与用例以及参与者参与者之间的泛化：子类 —▷父类
  • 参与者与用例之间有关联关系
• 对系统的静态用例视图建模：对系统的语境建模，对系统的需求建模

交互图

• 对系统的动态方面进行建模，之间的消息传递。交互图一般包含对象、链、消息，表现为序列图、通信图，他两可以相互转换
• 序列图(顺序图):描述了以时间顺序组织的对象之间的交互活动，场景的图形化表示。交互的对象放图的上方，发起交互的左边，下级的对象右边 ,展示了一个用例和多个对象的行为
  • 序列图有对象生命线，是一条垂直的虚线，表示一个对象在一段时间内存在 X就是生命线消失(结束)
  • 序列图有控制焦点，是一个瘦高的矩形，表示一个对象执行一个动作所经历的时间段(对象交互的时间段)，既可以是直接执行，也可以是通过下级程序执行。
  • 消息—> <——-返回消息 同步需要等待返回消息 异步则不需要

• 通信图(协作图):强调收发消息的对象的结构组织(展现了对象之间的消息流及其顺序)
  • 对象与对象之间有一条链（直线），链的旁边有消息（箭头），消息有序号
  • 通信图有顺序号，表示一个消息的时间顺序（执行顺序）
  • 通信图有路径，指出一个对象如何与另外一个对象链接

状态图

• 展现了一个状态机，由状态、转换、事件、和活动组成 。
• 关注系统的动态视图，强调对象行为的事件顺序。反应型对象建模(一个对象)
  • 状态是可以被观察到的系统行为模式，可以既改变状态，又做动作。
  • 状态有:初态(黑圆点)、终态(黑圆点加一个圆)、中间状态。
  • 状态用一个圆角四边形(分为上中下)，上是状态名称(必须有)中是状态变量的名称和值(可选)下面是活动表(可选)
  • 状态之间为状态转换，开始为点火或者触发，初态只能有一个 终态可以多个或者没有
  • 活动由多个动作组成：事件名(ps响铃)/动作表达式(ps接电话)
    • 三种标准事件名
  • 转换(迁移):状态之间为状态转换，是由一条带箭头的线表示
    • 有两个状态 原状态=====》目标状态
  • 事件(会触发转换):就是转换标识上面的事件，是某个时刻发生的事情，它对引起系统动作从一个状态到另外一个状态的外界事件的抽象
    • 事件表达式:事件说明[监护条件]/动作表达式
      • 同时使用事件说明和监护条件(布尔)，当且仅当事件发生加条件为真，状态转换才发生
      • 只有监护条件(布尔)没有事件说明，则只要条件为真，状态转换就可以发生动作表达式(没有标明事件，则内部活动结束后自动转换)
  • 活动(动作)可以在状态内执行，也可以在状态转换(迁移)时执行
• 组合状态(超状态)包含嵌套状态(子状态)

活动图

• 一种特殊的状态图，从一个活动到另一个活动的流程。与状态不同的是实线箭头上没有事件，有也是只有[监护表达式]，活动用的是椭圆形
• 他展现了在系统内从一个活动到另一个活动的流程，他对系统的功能建模特别重要，并强调对象间的控制流程
• 两种使用活动图方式：对工作流建模、对操作建模
• 活动图可以表示分支、合并、分岔和汇合。

构件图(组件图)

• 一组构件之间的组织和依赖。静态实现视图，与类图相关，构件映射为一个或者多个类、接口和协作。
• 构件图有个类似哑铃的特有符号 ，还有两个接口：半圆的需接口，整圆的供接口

部署图

• 用来对面向对象的物理方面建模的方法，(立体图)静态与构件图相关
• 展现了系统的软件与硬件之间的关系，在实施阶段使用
• 部署组件之间的依赖关系类似于包依赖

设计模式

设计模式分类

采用设计模式以复用成功的设计

• 创建型对象：单抽原生 4
• 结构型对象：外桥组装享适代 7
• 行为型对象：责命迭中备观状策访 9

设计模式	意图
工厂方法模式	定义一个用于创建对象的接口，让子类决定实例化哪一个类，工厂方法使一个类的实例化延迟到其子类
抽象工厂模式	提供一个创建一系列相关或者相互依赖对象的接口，而无须指定它的具体的类
生成器模式	将一个复杂对象的构件与它的表示分离，使得同样的构造过程可以创建不同的表示
原型模式	原型实例指定创建对象的种类，并且通过复制这些原型创建新的对象
单例模式	保证一个类仅有一个实例，并提供一个访问它的全局访问点
适配器模式	将一个类的接口转换成客户希望的另外一个接口
桥接模式	将抽象部分与其实现部分分离，使它们都可以独立地变化
组合模式	将对象组合树型结构以表示“部分-整体”的层次结构，组合使得用户对单个对象的组合对象的使用具有一致性
装饰模式	动态地给一个对象添加一些额外的职责
外观模式	为子系统的一组接口提供一个一致的界面
享元模式	运用共享技术有效地支持大量细粒度的对象
代理模式	为其他对象提供一种代理以控制对这个对象的访问
责任链模式	使多个对象都有机会处理请求，从而避免请求的发送者和接收者之间的耦合关系。将这些对象连成一条链，并沿着这条链传递该请求，直到有一个对象处理它为止。
命令模式	将一个请求封装成一个对象，从而使得可以用不同的请求对客户进行参数化，对请求哦爱对或者记录请求日志，以及支持可撤销的操作
解释器模式	给定一个语言，定义它的文法的一种表示，并定义一个解释器，这个解释器使用该表示来解释语言中的句子
迭代器模式	提供一种方法顺序访问一个聚合对象的各个元素，且不需要暴露该对象的内部表示
中介模式	用一个中介对象来封装一系列的对象交互。
备忘录模式	在不破坏封装性的前提下捕获一个对象的内部状态，并在对象之外保存这个状态，这样以后就可以将对象恢复到原先保存的状态
观察者模式	定义对象间的一种一对多的依赖关系，当一个对象的状态发生改变时，所有依赖它的对象都得到通知并被自动更新
状态模式	允许一个对象在其内部状态改变时改变它的行为。对象看起来似乎修改了它的类
策略模式	定义一系列的算法，把它们一个个封装起来，并且使它们可以相互替换。此模式使得算法可以独立于使用它们的客户而变化
模板方法模式	定义一个操作中的算法骨架，而将一些步骤延迟到子类中。模板使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤
访问者模式	表示一个作用于对象结构中的各元素的操作。它在不改变各元素的类的前提下定义作用于这些元素的新操作（Accept）

创建型设计模式

各种类的信息封装起来，整个系统关于这些对象所知道的是抽象锁定义的接口

简单工厂模式

• 简单工厂模式（静态工厂模式）属于创建型模式，但不属于23种设计模式之一。
• 意图是：定义一个工厂类，他可以根据参数的不同返回不同类的实例
• 在简单工厂模式中用于被创建实例的方法通常为静态(static)方法
• 三类角色
  • 工厂(核心）:负责实现创建所有产品的内部逻辑，工厂类可以被外界直接调用，创建所需对象
  • 抽象产品:工厂类所创建的所有对象的父类，封装了产品对象的公共方法，所有的具体产品为其子类对象
  • 具体产品:简单工厂模式的创建目标，所有被创建的对象都是某个具体类的实例。它要实现抽象产品中声明的抽象方法
• 例如：有一家饺子店，当客户需要某种饺子时，饺子店生成对应的饺子给客户。这里就可以把饺子店看成工厂(Factory) ，饺子看成产品（ Product) ,饺子的名称看成参数，饺子店根据不同的参数返回不同的饺子。

工厂方法模式

factory method

• 意图是：定义一个用于创建对象的接口，让子类决定实例化哪一个类，工厂方法使一个类的实例化延迟到其子类
• 当一个类不知道它所创建的对象的类的时候
• 当一个类希望由它的子类来指定它创建的对象的时候

抽象工厂模式

abstract factory

• 意图是：提供一个创建一系列相关或者相互依赖对象的接口，而无须指定它的具体的类
• 一个系统要独立于它的产品的创建、组合和表示时
• 一个系统要由多个产品系列中的一个来配置时
• 当要强调一些列相关的产品对象的设计以便进行联合使用时
• 当提供一个产品类库，只想显示它们的接口而不是实现时
• 为图形用户界面组件定义不同平台的并行类层次结构，适合采用抽象工厂

生成器模式

Builder

• 意图是：将一个复杂对象的构件与它的表示分离，使得同样的构造过程可以创建不同的表示
• 当创建复杂对象的算法应该独立于该对象的组成部分以及它们的装配方式时
• 当构造过程必须允许被构造的对象有不同的表示时

原型模式

Prototype

• 意图是：原型实例指定创建对象的种类，并且通过复制这些原型创建新的对象
• 当一个系统应该独立于它的产品创建、构成和表示时
• 当要实例化的类是在运行时刻指定时，例如，通过动态装载
• 为了避免创建一个与产品类层次平行的工厂类层次时
• 当一个类的实例只能有几个不同状态组合中的一种时，建立相应数目的原型并克隆它们，可能比每次用合适的状态手工实例化该类更方便一些

单例模式

singleton

• 意图是：保证一个类仅有一个实例，并提供一个访问它的全局访问点
• 当类只能有一个实例而且客户可以从一个众所周知的访问点访问它时
• 当这个唯一实例应该是子类化可扩展的，并且客户无须更改代码就能使用一个扩展的实例时

结构型设计模式

如何组合类和对象以获得更大的结构，采用继承机制来组合接口或实现

适配器模式

adapter

• 意图是：将一个类的接口转换成客户希望的另外一个接口
• 类适配器使用多重继承对一个接口与另一个接口进行匹配
• 对象适配器依赖于对象组合
• 想使用一个已经存在的类，而它的接口不符合要求
• 想创建一个可以复用的类，该类可以与其他不相关的类或不可预见的类协同工作(了解)
• 想使用一个已经存在的子类，但是不可能对每一个进行子类化以匹配它们的接口，对象适配器可以适配它的父类接口(仅适用于对象)

桥接模式

Bridge

• 意图是：将抽象部分与其实现部分分离，使它们都可以独立地变化
• 不希望在抽象和它的实现部分之间有一个固定的绑定关系。
• 类的抽象以及它的实现都应该可以通过生成子类的方法加以扩充。
• 对一个抽象的实现部分的修改应对客户不产生影响，即客户代码不必重新编译。
• 有许多类要生成的类层次结构。
• 想在多个对象间共享实现（可能使用引用计数)，但同时要求客户并不知道这一点。

组合模式

composite

• 意图是：将对象组合树型结构以表示”部分-整体”的层次结构，组合使得用户对单个对象的组合对象的使用具有一致性
• 适用于想表示对象的部分-整体层次结构
• 希望用户忽略组合对象与单个对象的不同，用户将统一地使用组合结构中的所有对象

装饰模式

decorator

• 意图是： 动态地给一个对象添加一些额外的职责
• 在不影响其他对象的情况下，以动态、透明的方式给单个对象添加职责
• 处理那些可以撤销的职责

外观模式

Facade

• 意图是：为子系统的一组接口提供一个一致的界面
• 要为一个复杂子系统提供一个简单接口时
• 客户程序与抽象类的实现部分之间存在着很大的依赖性
• 当需要构建一个层次结构的子系统，使用它定义子系统中每层的入口点

享元模式

Flyweight

• 意图是：运用共享技术有效地支持大量细粒度的对象
• 一个应用程序使用了大量的对象，造成很大的存储开销
• 对象的大多数状态都可变成外部状态
• 如果删除对象的外部转态，那么可以用相对较少的共享对象取代很多组对象
• 应用程序不依赖于对象标识

代理模式

Proxy

• 意图是：为其他对象提供一种代理 以控制对这个对象的访问
• Proxy模式适用于在需要比较通用和复杂的对象指针代替简单的指针的时候
• 远程代理(Remote Proxy)为一个对象在不同地址空间提供局部代表。
• 虚代理( Virtual Proxy)根据需要创建开销很大的对象。
• 保护代理(Protection Proxy)控制对原始对象的访问，用于对象应该有不同的访问权限的时候。
• 智能引用(Smart Reference）取代了简单的指针，它在访问对象时执行一些附加操作。

行为型设计模式

设计算法和对象间职责的分配，描述对象和类的模式，还有它们之间的通信模式

责任链模式

Chain Of Responsibility

• 意图是：使多个对象都有机会处理请求，从而避免请求的发送者和接收者之间的耦合关系。将这些对象连成一条链，并沿着这条链传递该请求，直到有一个对象处理它为止。
• 有多个的对象可以处理一个请求，哪个对象处理该请求运行时刻自动确定
• 想在不明确指定接收者的情况下想多个对象中的一个提交一个请求
• 可处理一个请求的对象集合应被动态指定

命令模式

Command

• 意图是：将一个请求封装成一个对象，从而使得可以用不同的请求对客户进行参数化，对请求哦爱对或者记录请求日志，以及支持可撤销的操作。
• 抽象出待执行的动作以及参数化某对象
• 在不同时刻指定、排列和执行请求
• 支持取消操作 支持修改日志
• 用构建在原语操作上的高层操作构造一个系统

解释器模式

Interpreter

• 意图是：给定一个语言，定义它的文法的一种表示，并定义一个解释器，这个解释器使用该表示来解释语言中的句子
• 一个语言需要解释执行，并且可将语言中的句子表示为一个抽象语法树时
• 该文法简单，效率不是一个关键问题

迭代器模式

Iterator

• 意图是：提供一种方法顺序访问一个聚合对象的各个元素，且不需要暴露该对象的内部表示
• 访问一个聚合对象的内容而无须暴露它的内部表示
• 支持对聚合对象的多种遍历
• 为遍历不同的聚合结构提供一个同一的接口

中介模式

Mediator

• 意图是：用一个中介对象来封装一系列的对象交互。
• 一组对象以定义良好但是复杂的方式进行通信，产生的相互依赖关系结构混乱且难以理解
• 一个对象引用其他很多对象并且直接与这些对象通信吗，导致难以复用该对象
• 想定制一个分布在多个类中的行为，而又不想生成太多的子类

备忘录模式

Memento

• 意图是：在不破坏封装性的前提下捕获一个对象的内部状态，并在对象之外保存这个状态，这样以后就可以将对象恢复到原先保存的状态
• 必须保存一个对象在某一个时刻的状态，这样以后需要时它才能恢复到先前的状态
• 如果一个用接口来让其他对象直接得到这些状态，将会暴露对象的实现细节并破坏对象的封装性

观察者模式

Observer(例子：发布/订阅消息模式)

• 意图是：定义对象间的一种一对多的依赖关系，当一个对象的状态发生改变时，所有依赖它的对象都得到通知并被自动更新
• 当一个抽象模型有两个方面，其中一个方面依赖于另一个方面，将这两者封装在独立的对象中以使它们可以各自独立地改变和复用
• 当对一个对象的改变需要同时改变其他对象，而不知道具体有多少对象有待改变时
• 当一个对象必须通知其他对象，而它又不能假定其他对象是谁，既不希望这些对象是紧耦合的

状态模式

State

• 意图是：允许一个对象在其内部状态改变时改变它的行为。对象看起来似乎修改了它的类
• 一个对象的行为决定于它的状态，并且它必须在运行时候根据状态改变它的行为
• 一个操作中有庞大的多分支条件语句，且这些分支依赖于该对象的状态。这个状态常用一个多个枚举常量表示

策略模式

Strategy

• 意图是：定义一系列的算法，把它们一个个封装起来，并且使它们可以相互替换。此模式使得算法可以独立于使用它们的客户而变化
• 许多相关的类仅仅只是行为有异
• 需要使用一个算法的不同变体
• 算法使用客户不应该知道的数据
• 一个类定义了多种行为，并且这种行为在这个类的操作中以多个条件语句的形式出现，将相关的条件分支移入它们各自的策略类中，以代替这些条件语句。(顾客 初级会员中级会员高级会员对应的折扣不同)

模板方法模式

Template Method

• 意图是：定义一个操作中的算法骨架，而将一些步骤延迟到子类中。模板使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤
• 一次性实现一个算法的不变的部分，把将可变的行为留给子类来实现
• 各子类中公共的行为应被提取出来并集中到一个公共父类中，以避免代码重复
• 控制子类扩展

访问者模式

Visitor

• 意图是：表示一个作用于对象结构中的各元素的操作。它在不改变各元素的类的前提下定义作用于这些元素的新操作（Accept）
• 一个对象结构包含很多类对象，它们有不同的接口，而用户想对这些对象实施一些依赖于其具体类的操作
• 定义对象结构的类很少改变，但经常需要在此结构上定义新的操作
• 需要对一个对象结构中的对象进行很多不同的并且不相关的操作

数据结构

排序

可将排序分为内排序和外排序两种

内排序

内排序：排序时不涉及数据的内外存交换

稳定性：若序列中，存在多个关键字相同的元素，如果排序前和排序后这些元素的位置不变，则称该排序方法是稳定的，反之则是不稳地的。

排序方法	时间复杂度平均情况	最好情况	最坏情况	空间复杂度	稳定性
直接插入排序	n²	n	n²	1	稳定
希尔排序	n^1.3	n	n²	1	不稳定
冒泡排序	n²	n	n²	1	稳定
快速排序	nlog2n	nlog2n	n²	nlog2n	不稳定
简单选择排序	n²	n²	n²	1	不稳定
堆排序	nlog2n	nlog2n	nlog2n	1	不稳定
归并排序	nlog2n	nlog2n	nlog2n	n	稳定

口诀：

插冒龟，他很稳

选冒插，他慌了

快归堆，是n老

基于比较的排序

两种基本操作：比较和移动

插入排序

基本思路：每一趟将一个待排序的元素，按其关键字值的大小插入到已经排序的部分文件中的适当位置上，直到全部插入完成。

直接插入排序

• 对一个基本有序的数组进行排序

练手：（75，87，68，92，88，61，77，96，80，72）

• 思路步骤：依次将每个元素插入到一个有序的序列中去

1. 从第一个元素开始，可以认为第一个元素已经排好顺序。
2. 取出后面一个元素 n，在前面已经排好顺序的数组里从尾部往头部遍历，放到合适的位置上
3. 重复上面的步骤 2，直到所有元素都插入到正确的位置。

• 说明：直接插入排序中每趟产生的有序区并不一定是全局有序区，就是说有序区中的元素并不一定放在最终的位置上。

希尔排序

练手：（75，87，68，92，88，61，77，96，80，72）

• 思路步骤：

1. 选择一个增量 gap，一般开始是数组的一半，将数组元素按照间隔为 gap 分为若干个小组。
2. 对每一个小组进行直接插入排序。
3. 将 gap 缩小为一半，重新分组，重复步骤 2（直到 gap 为 1 的时候基本有序，稍微调整一下即可）

• 说明：希尔排序每趟并不产生有序区，在最后一趟排序结束前，所有元素并不一定归位。但是希尔排序每趟完成后，数据越来越接近有序

交换排序

基本思路：两两比较待排序元素的关键字，并交换不满足次序要求的那些偶对，直到全部满足为止

冒泡排序

练手：（75，87，68，92，88，61，77，96，80，72）

• 思路步骤通过无序区中相邻元素关键字间的比较和位置的交换，使最后一个数字一定是最大的，即最后一个元素已经排好序，下一轮只需要保证前面 n-1 个元素的顺序即可。

1. 从头开始，比较相邻的两个数，如果第一个数比第二个数大，那么就交换它们的位置
2. 从开始到最后一对比较完成，一轮结束后，最后一个元素的位置已经确定。
3. 除了最后一个元素以外，前面的所有未排好序的元素重复前面两个步骤。
4. 重复前面 1 ～ 3 步骤，直到所有元素都已经排好序。

• 说明冒泡排序每趟产生的有序区一定是全局有序区

快速排序

• 分治算法

练手：（75，87，68，92，88，61，77，96，80，72）

• 思路步骤在待排序的n个元素中任取一个元素作为基准数（通常取第一个），经过一趟排序，将数组分割成为两部分，一部分均小于/等于基准数，另外一部分大于/等于基准数。然后分别对基准数的左右两部分继续排序，直到数组有序。这体现了分而治之的思想。
  1. 从数组中挑一个元素作为基准数，一般情况下我们选择第一个 nums[i]，保存为 standardNum，可以理解为 nums[i] 坑位的数被拎出来了，留下空的坑位。
  2. 取数组的左边界索引指针 i，右边界索引指针 j，j 从右边往左边，寻找到比 standardNum 小的数，停下来，写到 nums[i] 的坑位，nums[j] 的坑位空出来。 索引指针 i 从左边往右边找，寻找比 standardNum 大的数，停下来，写到 nums[j] 的坑位，这个时候，num[i] 的坑位空出来（前提是 i 和 j 不相撞）。
  3. 上面的 i 和 j 循环步骤 2，直到两个索引指针 i 和 j 相撞，将基准值 standardNum 写到坑位 nums[i] 中，这时候，standardNum 左边的数都小于等于它本身，右边的数都大于等于它本身
  4. 分别对 standardNum 左边的子数组和右边的子数组，循环执行前面的 1，2，3，直到不可再分，并且有序。
• 说明快速排序每趟仅将一个元素归为，在最后一趟排序前整个序列不一定有序快速排序在待排序的数据随机分布时效率最高

选择排序

基本思路：每步从待排序的元素中选出关键字最小的元素，按顺序放在已排序的元素序列的最后，直到全部排完为止。

简单选择排序

练手：（75，87，68，92，88，61，77，96，80，72）

• 思路步骤每一趟都是直接从无序区中选择一个最小的元素，放在有序区的最后面
  1. 从第 1 个元素开始，遍历其后面的元素，找出其后面比它更小的且最小的元素，若有，则两者交换，保证第 1 个元素最小
  2. 对第 2 个元素一样，遍历其后面的元素，找出其后面比它更小的且最小的元素，若存在，则两者交换，保证第 2 个元素在未排序的数中（除了第一个元素）最小
  3. 依次类推，直到最后一个元素，那么数组就已经排好序了
• 说明简单选择排序每趟产生的有序区一定是全局有序区无论元素的初始排列如何，所需进行的关键字比较相同

堆排序

练手：（75，87，68，92，88，61，77，96，80，72）

• 介绍堆排序是一种完全二叉树大顶堆：每个节点的数值都大于或者等于其左右孩子节点的数值。小顶堆：每个节点的数值都小于或者等于其左右孩子节点的数值。
• 思路步骤
  1. 将无序的数组构建出一个大顶堆，也就是上面的元素比下面的元素大。(第一个非叶子节点：n/2-1)
  2. 将堆顶的元素和堆的最末尾的元素交换，将最大元素下沉到数组的最后面（末端）
  3. 重新调整前面的顺序，继续交换堆顶的元素和当前末尾的元素，直到所有元素全部下沉。
• 说明堆排序每趟产生的有序区一定是全局有序区

归并排序

• 分治算法

练手：（75，87，68，92，88，61，77，96，80，72）

第一趟排序结果：75，87，68，92，61，88，77，96，72，80

第二趟排序结果：68，75，87，92，61，77，88，96，72，80

第三趟排序结果：61，68，71，77，87，88，92，96，72，80

第四趟排序结果：61，68，71，72，77，80，87，88，92，96

• 思路步骤归并的总体思想是先将数组分割，再分割 … 分割到一个元素，然后再两两归并排序，做到局部有序，不断地归并，直到数组又被全部合起来。
• 说明归并排序每趟产生的有序区只是局部有序的，也就是说在最后一趟排序结束前，所有元素并不一定归位了。

不基于比较的排序

基数排序

练手：（75，87，68，92，88，61，77，96，80，72）

• 思路步骤它只能用在整数（自然数）排序，而且不是基于比较的，其原理是将整数按照位分成不同的数字，按照每个数各位值逐步排序。

树

树的基本术语和性质

树构造森林：左子树是n1-1，右子树是n2+n3

树的基本术语

• 根：树的顶端结点
• 结点的度：每个结点具有的后继结点数
• 树的度：树中所有结点的度的最大值
• 叶子结点（终端结点）：度为0的结点
• 单分支结点：度为1的结点
• 双分支结点：度为2的结点

树的性质

• 性质1：树中的结点数等于所有结点的度数加1。
  • 度之和=分支数=n-1，所以n=度之和+1
• 性质2：性质2：度为m的树中第i层上至多有m^(i-1)个结点，i≥1。
• 性质3：高度为h的m次树至多有(m^h-1)/m-1个结点

二叉树

二叉树的定义

• 定义：二叉树或者是一颗空树，或者是一棵由一个根结点和两棵互不相交的分别称做根结点的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树。
• 二叉树与度为2的树是不同的
  1. 度为2的树至少有3个结点，而二叉树的结点数可以为0。
  2. 度为2的树不区分子树的次序，而二叉树中的每个结点最多有两个孩子结点，且必须要区分左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。

二叉树的性质

• 性质1：非空二叉树上叶结点数等于双分支结点数加1。即n0=n2+1。
• 性质2：非空二叉树上第i层上至多有2^(i-1)个结点，i≥1。
• 性质3：高度为h的二叉树至多有2^h-1个结点（h≥1）。

常见的二叉树

• 满二叉树（完美二叉树）：最后一层完全填充的树，即一棵高度为h且有2^h-1个结点的二叉树称为满二叉树。
• 完全二叉树：完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。
• 满二叉树肯定是完全二叉树,而完全二叉树不一定是满二叉树
• 若对完全二叉树从根结点为1开始，按照层次从小到大、同一层从左到右的次序顺序编号。其编号为i的结点有以下性质：
  1. 若i<[n/2],则编号为i的结点为分支结点，否则为叶子结点
  2. 若n为奇数，则每个分支结点都既有左孩子结点，也有右孩子结点；
  3. 若n为偶数，则编号最大的分支结点只有左孩子结点，没有右孩子结点，其余分支结点都有左、右孩子结点。
  4. 若编号为i的结点有左孩子结点，则左孩子结点的编号为2i；若编号为i的结点有右孩子结点，则右孩子结点的编号为(2i+1)。
• 平衡二叉树(AVL) ︰它或者是一颗空树，或者它的左子树和右子树的深度之差的绝对值不超过1，完全二叉树一定是平衡二叉树
• 最优二叉树:哈夫曼树
• 二叉排序树(二叉查找树)：其左子树上所有结点的关键字均小于根结点的关键字，右子树上所有结点的关键字均大于根结点的关键字；二叉排序树的中序遍历是一个递增有序的序列。
• 线索二叉树：为了保存结点在任一序列中的前驱和后继信息，利用空指针域来存储

二叉树的遍历

• 先序遍历（中左右）
  • 若二叉树非空，则：① 访问根结点；② 先序遍历左子树；③ 先序遍历右子树。
  • 先序遍历序列的特点：其第一个元素值为二叉树中根结点值。
• 中序遍历（左中右）
  • 若二叉树非空，则：① 中序遍历左子树；② 访问根结点；③ 中序遍历右子树。、
  • 中序遍历序列的特点：若已知二叉树的根结点值，以该值为界，将中序遍历序列分为两部分，前半部分为左子树的中序遍历序列，后半部分为右子树的中序遍历序列。
• 后序遍历（左右中）
  • 若二叉树非空，则：① 后序遍历左子树；② 后序遍历右子树；③ 访问根结点。
  • 后序遍历序列的特点：最后一个元素值为二叉树中根结点值。
• 层次遍历
  • 层次遍历是从根结点出发，按照从上向下，同一层从左向右的次序访问所有的结点。
  • 层次遍历序列的特点：其第一个元素值为二叉树中根结点值。

二叉树的构造

• 由先序遍历序列和中序遍历序列能够唯一确定一棵二叉树。
• 由后序遍历序列和中序遍历序列能够唯一确定一棵二叉树。
• 由先序遍历序列和后序遍历序列不能唯一确定一棵二叉树。

哈夫曼树

• 定义：二叉树具有n个带权值的叶子结点，从根结点到每个叶子结点都有一个路径长度。从根结点到各个叶子结点的路径长度与相应结点权值的乘积的和称为该二叉树的带权路径长度，记作：WPL。具有最小带权路径长度的二叉树称为哈夫曼树。
• 构造哈夫曼树
  1. 对给定的n个权值{W1,W2,W3,…,Wi,…,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,…,Ti,…,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。
  2. 在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
  3. 从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。
  4. 重复二和三两步，直到集合F中只有一棵二叉树为止。
• 哈夫曼编码
  • 左子树的分支表示为0，右子树的分支表示为1
  • 哈夫曼编码基于贪心策略
  • 没有一个字符的哈夫曼编码是另一个字符的哈夫曼编码的前缀。如某个字符的哈夫曼编码为01，则该组字符中不可能出现以01开头的哈夫曼编码了。
• 等长编码x：2^x>=n，n是字符个数

图

图的基本术语

• 端点和相邻点
  • 在一个无向图中，若存在一条边(i,j)，则称i和j为该边的两个端点，并且它们互为相邻点
  • 在一个有向图中，若存在一条边<i,j>，则称i为起始端点，j为终止端点。此边也是i的出边，j的入边
• 度、入度、出度
  • 顶点v的度记为D（v）
  • 对于无向图，每个顶点的度定义为以该顶点为一个端点的边数
  • 对于有向图，顶点v的度分为入度和出度。该顶点的度=入度数+出度数
    • n个顶点的有向图中，每个顶点的度最大可达(n-1)*2
  • 一个图中所有顶点的度之和=边数的两倍
• 完全无向图和完全有向图
  • 完全无向图：具有n(n-1)/2条边的无向图，n为顶点数。
  • 完全有向图：具有n(n-1)条边的有向图。
• 路径长度和简单路径
  • 路径长度：一条路径上经过的边的数目。
  • 简单路径：顶点序列中顶点不重复出现的路径
• 回路（环）和简单回路（简单环）
  • 回路：开始点和结束点为同一个顶点的路径
  • 简单回路：开始点和结束点为同一个顶点，且其余顶点不重复出现的路径
• 连通，连通图，强连通图，强连通分量
  • 连通：在无向图中，若两个顶点间有路径，则称这两个顶点是连通的
  • 连通图：在无向图中，若任意两个顶点之间都是连通的，则称该图为连通图，n个顶点的连通图至少有n-1条边
  • 强连通图：在有向图中，若任意两个顶点之间都是连通的，即从顶点i到j和从顶点j到i都有路径，则称该图为强连通图，n个顶点的强连通图至少有n条边
  • 有向图中的极大强连通子图称为该有向图的强连通分量。 强连通分量的求法：
    1. 找出入度或出度为0的点
    2. 依次删去这些点，并将这些点在另外的地方写下，每删一次都要重新检查一边
    3. 直到没有存在入度或出度为0的点
• 权和网
  • 权：图中每条边上可以标某种数值，该数值就称为该边的权
  • 网：边上带权的图，称为网。也称为带权图
• 拓扑排序
  • 顶点Vi到顶点Vj有一条有向路径，则顶点Vi是Vj的前驱
  • 可能存在Vi到Vj的路径，一定不存在Vj到Vi的路径

图的存储结构

邻接矩阵

• n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为（ O(n^2) ）。
• 无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵可能是对称的（完全有向图）

无向图的

有向图的

有向权图的

邻接表

• n个顶点e条边的有向图，若采用邻接表存储，则空间复杂度为（O(n+e) ）。

有向图的

无向图的

图的遍历

深度优先遍历

深度优先搜索是类似于树的先序遍历（一条路走到黑）

步骤

1. 首先，选定一个出发点后进行遍历，如果有邻接的未被访问过的节点则继续前进。
2. 若不能继续前进，则回退一步再前进
3. 若回退一步仍然不能前进，则连续回退至可以前进的位置为止。
4. 重复此过程，直到所有与选定点相通的所有顶点都被遍历。

广度优先遍历

广度优先搜索类似于树的层次遍历，是按照一种由近及远的方式访问图的顶点。在进行广度优先搜索时需要使用队列存储顶点信息。

步骤

1. 从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点
2. 然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。
3. 如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

最小生成树及其构造

• 最小生成树：由一个带权无向图可能产生多棵生成树， 把具有权之和最小的生成树称为图的最小生成树

普里姆算法

• 步骤
  1. 在生成树的构造过程中，图中n个顶点分属两个集合：已落在生成树上的顶点集合U 和 尚未落在生成树上的顶级集合V-U
  2. 则应在所有连通U中顶点和V-U中的顶点的边中选取权值最小的边。
• 分析
  • 普利姆算法的时间复杂度为：O(n2)，执行时间主要取决于图的顶点数，与边数无关。
  • 该算法适用于稠密图的操作。

克鲁斯卡尔算法

• 克鲁斯卡尔（Kruskal）算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。
• 步骤
  1. T的初始化状态 T = (V, 空 ) ，即最小生成树T是图G的生成零图。
  2. 将图G中的边按照权值从小到大的顺序排序
  3. 依次选取每条边，若选取的边未使生成树T形成回路，则加入TE中，否则舍弃。直至TE中包含n-1条边为止
• 分析
  • 克鲁斯卡尔算法的执行时间主要取决于图的边数。
  • 该算法适用于针对稀疏图的操作。

查找

静态查找

顺序查找、折半查找、分块查找

若在查找的同时不适合对表做修改运算（如插入和删除），这样的表称之为静态查找表。

顺序查找

• 基本思路：从表的一端开始顺序扫描顺序表，依次将扫描到的元素关键字和给定值k相比较
• 查找成功时的平均查找长度为：（n+1）/2
• 查找不成功时的平均查找长度为：n
• 若查找成功，则比较关键字的次数最多为：n 次；
• 若查找不成功，则比较关键字的次数为：n 次。

折半查找

• 折半查找采用分治思想，查找表采用顺序存储结构并有序存储
• 平均查找长度:log2(n+1)-1
• 最多是[log2n]+1 向下取整
• 基本思路
  1. 设R[low..high]是当前的查找区间，首先确定该区间的中点位置mid=(low+high)/2；然后将待查的k值与R[mid].key比较：
  2. 若R[mid].key>k，则该元素必定在位置mid左子表R[0..mid-1]中，故新的查找区间是左子表R[0..mid-1]；
  3. 若R[mid].key<k，则要查找的k必在位置mid的右子表R[mid+1..n-1]中，即新的查找区间是右子表R[mid+1..n-1]。
  4. 若R[mid].key=k，则查找成功并返回该元素的逻辑序号；

动态查找

平衡二叉树、二叉排序树、B树、哈希表

若在查找的同时适合对表做修改运算（如插入和删除），这样的表称之为动态查找表。

哈希表查找

哈希表的基本概念

• 哈希表又称散列表
• 哈希表存储的基本思路：用关键字的值k，决定数据元素的存储地址h(k)。
• 尽可能使用关键字的所有组成部分都能起作用
• 哈希冲突：h(ki)=h(kj)

哈希函数的构造方法

• 直接地址法：h(k)=k+c
• 除留余数法：h(k)=k % p（p<=m,通常假设p=m）

哈希冲突的解决方法

装填因子α：α=n/m，m是哈希表的长度。当α越小时，冲突的可能性越小。当α越大时，冲突的可能性越大

• 开发地址法
  • 线性探测法：d0=h(k),di=(d(i-1)+1) % m
  • 平方探测法
• 拉链法

其他

复杂度

• 时间复杂度：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n²)<O(n^3)
• 空间复杂度：定义的数据占用多少空间就是空间复杂度

B-树

一棵m阶的B-树，或为空树，或为满足下列特性的m叉树。

• 树中每个结点最多有m棵子树。
• 所有的叶子结点都出现在同一层次上，并且不带信息
• 结点中的关键字有序排列
• 若根结点不是叶子结点，则最少有两棵子树。

线性表

• 最简单、最基本也是最常用的一种线性结构，采用顺序存储和链式存储
• 非空的线性表，除了第一个外，其他元素都只有一个直接前驱，除了最后一个，其他元素都只有一个直接后继

顺序存储

• 一组地址连续的存储单元依次存储在线性表中的数据元素。只有数据
• 优点：查找时间复杂度O(1)
• 缺点:插入删除都需要移动元素
  • 插入需要平均移动：n/2 时间复杂度O(n)
  • 删除需要移动（n-1）/2

链式存储

• 通过指针链接起来的结点来存储数据元素。 数据域|指针域
• 带头(不带头)单链表插入、删除、查找平均复杂度O(n) 平均移动 0

栈和队列

栈

• 只能访问它的一端来实现数据的存储和检索的一种线性数据结构
• 特点：先进后出，进行插入跟删除的一端是栈顶，另外一端是栈底。没有数据元素就是空栈
• 实现函数或过程的递归调用及返回处理时
• 出栈跟入栈是不需要遍历的

队列

• 先进先出的线性表，只允许在表的一端插入元素(队尾Rear)，而在表的另外一端删除元素(对头Front)

杂题

• 三元顺序表和十字链表是对稀疏矩阵压缩存储的方式

常见计算题

公式计算题

1. • 2^(头-尾+1)
2. 当m>=n*(K-1)+1时不会死锁
   • m为资源数量，n为进程数量，k为每个进程需要的资源数量
3. 分页存储管理：进制数的第一个数的物理块号+后三个数=物理地址
4. 缓冲区
   • 单缓冲区时间=（输入时间 + 传送时间）* 作业个数+处理时间
   • 双缓冲区时间=（输入时间 * 作业个数）+传送时间+处理时间
5. • 设数据位是n位．校验位是k位，则n和k必须满足以下关系:2^k-1>=n+k
6. 沟通路径
   • 沟通路径无主程序员的公式 n x (n-1) / 2，就是求和公式
   • 有主程序员n-1，其中n为程序员的个数
7. • 串联部件的可靠度=各部件的可靠度的乘积
   • 并联部件的可靠度=1-部件失效率的乘积（1-部件的可靠度）。

复杂计算题

1. • （2000-4）/2000=0.998
2. • 最长处理时间：27*（9-1）+27/9+3=222
   • 最少处理时间：（27/9+3）*9=54
3. • 第一个空：
     • 字长为32位,所以每个字可以表示32个物理块
     • （物理块号数/系统的字长位数）=16385/32=512……1
   • 第二个空
     • 磁盘存放的物理块数=1000*1024/4=256000
     • （磁盘存放的物理块数/系统的字节位数）=256000/32=8000

• 总结点数 = sum（非0度*结点数）+1=（4 * 7 + 3 * 5 +2 * 8 + 1 * 10）+ 1 = 69 + 1 = 70
• 叶子节点数 = 总结点数 – sum （非0度的结点） = 70 -（7+5+8+10）=70-30 = 40

试题一：数据流图

四道题

数据流图DFD的基本图形

• 实体：E
• 数据存储：D
• 加工：P

• 外部实体：当前系统之外的人、物、外部系统
• 数据存储：存储数据和提供数据（存储加工的输出数据和提供加工的输入数据），常见的有xxx表，xxx文件
• 加工：将输入数据处理后得到输出数据，一个加工至少有一个输入数据流和一个输出数据流
  • 加工只有输入没有输出称为:黑洞
  • 加工只有输出没有输入称为:奇迹
  • 加工的输入数据不足以产生输出数据:灰洞
• 数据流：表示数据的流向，起点或终点必须有一个是加工

问题一

• 分值：3-5分
• 问题形式：一般是问你图中的实体E的名称
• 解题技巧：结合子图和文字说明直接找答案就行
• 答题格式：E1:xxx E2:xxx E3:xxx

问题二

• 分值：3-5分
• 问题形式：一般是问你图中的数据存储D的名称
• 解题技巧：结合子图和文字说明直接找答案就行。有些找不到的直接在相应的数据流名称后面加个表或文件
• 答题格式：D1:xxx D2:xxx D3:xxx

问题三

• 分值：3-6分
• 问题形式：一般是让你补充子图中缺少的数据流及其起点和终点。
• 解题技巧
  • 方法一：父图子图平衡（父图中出现的数据流也应在子图中出现）
  • 方法二：加工既有输入数据流也有输出数据流
  • 方法三：数据守恒（结合文字说明分析）
  • 数据流的起点或终点必须有一个是加工
  • 注意关键字：“根据” ，”将“，”从“，”对“，”存储“
• 答题格式
  • 格式一：数据流名称:xxx 起点:xxx(可以写字母,也可以写具体的文字） 终点:xxx(可以写字母,也可以写具体的文字）
  • 格式二：写成表格形式(可以写字母,也可以写具体的文字）

问题四

• 问题形式不固定，常见问题有：
  • 给出某数据流的组成
    • 答题格式：该数据流=xx+xxx+xxxx…
  • 采用结构化语言对xxxx的加工逻辑进行描述
    • 答题格式：xxx IF xxx Then xxx else xxx endif
  • xxxx可以分解为哪些子加工？
    • xxxx可以分解为：xxx、xxxx、xxxxx
  • 建模图 1-1 和图 1-2 时如何保持数据流图平衡。
    • 答案：
      • 图1-1（或父图)中某加工的输入输出数据流必须与图1-2(或子图）的输入输出数据流在数量和名字上相同;
      • 图 1-1(或父图）中的一个输入（或输出）数据流对应于图1-2(或子图）中几个输入（或输出）数据流，
      • 而图1-2(或子图）中组成这些数据流的数据项全体正好是父图中的这一条数据流。
      • 什么是父图与子图的平衡，就是父图的数据流和子图的数据流在数量、方向、名称上保持一致。

试题二：数据库设计

E-R图基本图形

• 矩形：实体
  • 通常指现实世界中的人或物
  • 弱实体：用双边矩形表示，这种实体对于另一些实体具有很强的依赖关系
  • 子实体：用一个躺着的目字表示，这种实体是某个实体的子类
• 椭圆：属性（实体的属性）
  • 简单属性：简单属性是原子的，不可再分的
  • NULL属性：NULL属性上没有值或属性值未知
  • 派生属性：派生属性可以从其他属性得来
• 菱形：联系（实体间的联系）
  • 一对一（1：1）：
  • 一对多（1：n）：
  • 多对多（m：n）：

关系模式

关系模式

• 格式：关系名（属性名1，属性名2，属性名3，…）
• 候选码（或候选键）：属性或属性组合，其值能够唯一地标识一个元组。
• 主码（或主键）：在一个关系中可能有多个候选码，从中选择一个作为主码。一般用下划线标识
• 外码（或外键）：如果一个关系中的属性或属性组并非该关系的码，但它们是另外一个关系的码，则称其为该关系的外码。一般用下滑虚线标识

超类和子类的转换

• 超类，子类实体都可以转换为一个关系，只需将超类实体的主码加到子类实体中

完整性约束关系

• 即主键和外键

联系的转换

一般能归并的都很少转成独立的关系模式

• 一对一联系的转换
  • 方式一：转换成一个独立的关系模式，关系的码取自任一方实体的码，关系模式的属性包括该联系所关联的两个实体的码及联系的属性，
  • 方式二：归并到关联的两个实体的任一方，归并方实体的码保持不变，给归并方实体属性集中增加另一方实体的码和该联系的属性即可，
• 一对多联系的转换
  • 方式一：转换成一个独立的关系模式，关系的码是多方实体的码，关系模式的属性取该联系所关联的两个实体的码及联系的属性
  • 方式二：归并到关联的两个实体的多方，多方实体码保持不变，多方实体属性集中增加一方实体的码和该联系的属性即可，
• 多对多联系的转换：只能转换成一个独立的关系模式，码取多方实体的码构成的属性组，属性取自身的属性和所关系实体的码。
• 三个实体的联系的转换：只能转换成一个独立的关系模式，码取三个实体的码构成的属性组，属性取自身的属性和所关系实体的码

问题一

• 分值：4-6分
• 问题形式：补充E-R图中缺少的联系
• 解题技巧：从需求分析结果分析得出结果即可。

问题二

• 问题形式：补充关系模式中缺少的属性 或 给出某几个关系的主键和外键
• 解题技巧：结合需求分析结果和补充好的E-R图分析得出结果即可。

试题三：UML

类图

• 展现一组对象、接口、协作和它们之间的关系，是最常见的图
• 类图中通常包括：类（类名，属性，方法）、接口、协作、关系（依赖，泛化，关联）
• 修饰符 : ＋共有的 – 私有的 # 受保护的 ~包的

关系

• 依赖：B—->A（B依赖于A），一个独立事物A发生变化会影响另一个依赖事物B的语义。
• 关联：关联是一种结构关系，描述了一组链，链是对象之间的连接。关联是一条直线，在上面可以标注多重度(重复度)和角色 0..1— 0..* 一对多
  • 聚合：—◇ 部分整体生命周期不一致，整体消失，部分仍然存在，部分可以脱离整体存在
  • 组合：—◆ 部分整体生命周期一致，整体消失，部分也消失，部分不可以脱离整体存在
• 泛化：子类 —▷父类，子元素(特殊元素)的对象可替代父元素(一般元素)的对象(一个类与多个类的关系)，子共享了父的结构和行为
• 实现：类 – – -▷接口 ，一个类元指定了由另一个类元保证执行的契机。

用例图

• 展现了一组用例、参与者以及它们的关系
• 用例用椭圆表示，参与者用一个小人表示
• 关系
  • 用例之间
    • 包含关系《include》：A基本用例(包含用例)- – ->B被包含用例，执行A之前必定要执行B
    • 扩展关系《extend》：A扩展用例(特殊的情况)- – – >基本用例，一个用例执行的时候，可能会发生一些特殊的情况或可选的情况，这种情况就是这个用例的扩展用例
    • 泛化关系：子类 —▷父类
  • 参与者之间：子类 —▷父类
  • 参与者与用例之间：关联关系

问题形式

• 给出用例图中所对应的参与者A的名称
• 给出用例图中所对应的用例U的名称
  • 用例一般都是动词，且为参与者所能执行的动作
• 给出用例图中用例U之间存在的关系
• 给出类图中所对应的类名C
• 给出用例图中的类的关键属性

试题四：C算法

算法策略

算法名称	关键点	特征	典型问题
分治法	递归技术	把一个问题拆分成多个小模块的相同子问题，一般可用递归解决。	归并排序、快速排序、二分搜索
动态规划法	最优子结构和递归式	划分子问题（最优子结构），并把子问题结果使用数组存储，利用查询子问题结果构造最终问题结果。	矩阵乘法、背包问题、LCS最长公共子序列
贪心法	一般用于求满意解，特殊情况可求最优解（部分背包）	局部最优，但整体不见得最优。每步有明确的，既定的策略。	背包问题（如装箱）、多机调度、找零钱问题
回溯法	探索和回退	系统的搜索一个问题的所有解或任一解。有试探和回退的过程。	N皇后问题、迷宫、背包问题

问题一

• 分值8-10分
• 问题形式：代码填空

问题二

• 问题形式：时间空间复杂度，算法策略

试题六：JAVA设计模式

• 接口中public abstract可以省略不写，抽象类不行
• 对于方法返回值为List< xxx >的对象，其方法类型是xxx，而不是List< xxx >

问题形式

• 代码填空，一般是5个空

错题

选择题

• RUP应用了角色、活动、制品和工作流4种重要的模型元素其中
  • 角色表述谁做
  • 制品表述做什么
  • 活动表述怎么做
  • 工作流表述什么时
• 数据处理领域的不太复杂、规模不大、需求变化也不大的系统，适于用结构化方法进行开发
• 软件过程改进的框架：过程改进基础设施、过程改进线路图、软件过程评估方法和软件过程改进计划。
• 功能性特性的质量子特性包括：适合性、准确性、互用性、依从性和安全性。
• 在屏蔽硬件错误的容错技术中，冗余附加技术包括：关键程序和数据的冗余存储及调用:检测、表决、切换、重构、纠错和复算的实现。
• 在屏蔽软件错误的容错技术中，冗余附加技术包括：冗余备份程序的存储及调用实现错误检测和错误恢复的程序:实现容错软件所需的固化程序。
• 高质量的文档包括：针对性、精确性、清晰性、完整性、灵活性、可追溯性
• 概要设计阶段进行：软件体系结构的设计、数据设计和接口设计;
• 详细设计阶段进行：数据结构和算法的设计。