导图社区 软件设计师
- 268
- 17
- 3
- 举报
软件设计师
软件设计师的思维导图，包括计算机基础知识、计算机结构、指令系统、计算机可靠性、计算机性能指标等内容。
编辑于2022-11-11 12:02:40 上海- 软件设计
- 相似推荐
- 大纲
计算机组成原理与体系结构
计算机基础知识
数据的表示
进制

R进制转十进制：按权展开法

十进制转R进制：短除法

编码，机器字长为n
 
原码
首位为符号位，其余n-1用二进制表示，◇表示小数点
1+（-1） = -2
反码
在原码的基础上，首位符号位不变，其余位，正数不变，负数全部取反
1+（-1） = -0
补码
正数不变，负数在反码的基础上+1
1+（-1） = 0
移码
在补码的基础上，首位取反
用于，浮点运算中的阶码运算
浮点数运算
M：尾数；e：指数，阶码；R：基数
逻辑运算

校验码

码距
一个编码系统中任意两个合法编码之间至少有多少个二进制为不同
在一个码组内为了检测e个误码，要求最小码距d应该满足d>=e+1
在一个码组内为了纠正t个误码，要求最小码距d应该满足d>=2t+1
奇偶校验

通过在编码中增加一位校验位来使编码中1的个数为奇数（奇校验）或者偶数（偶校验），使码距变为2，奇校验仅能检测奇数位出错的编码，偶校验仅能检测偶数位出错的编码
可检错，不可纠错
循环冗余校验码CRC

利用多项式为k个数据位产生r个校验位来进行编码，其编码长度为k+r； CRC左边为信息码（数据），右边是校验码， 若n为CRC吗的字长，信息码占k位，则校验码占n-k位，CRC又称为（n,k）码
可检错，不可纠错
模2除法

海明码

设数据位是n位，校验位是k位，n和k必须满足：
校验位与具体的数据位之间的关系

每一位校验码的计算公式

检错与纠错原理

计算机结构
CPU
运算器
是数据加工处理部件，用于完成计算机的各种算数和逻辑运算。 接受控制器的命令进行动作，是执行部件
算数逻辑单元ALU
负责处理数据，实现对数据的算数运算和逻辑运算
累加寄存器AC
当运算器的算数逻辑单元执行算数或逻辑运算的时候，为ALU提供一个工作区。至少有一个
数据缓冲寄存器DR
写内存时，暂存指令或数据
状态条件寄存器PSW
保存状态标志和控制标志
控制器
控制整个CPU的工作
程序计数器PC
存储下一条将要执行的指令
指令寄存器IR
存储即将执行的指令
指令译码器ID
对指令中的操作码字段进行分析解释
时序部件
提供时序控制信号
存储系统
层次化存储结构

包括
CPU内部通用寄存器
Cache
内存
外存
局部性原理
时间局部性
被引用过一次的存储器位置在未来会被多次引用（通常在循环中）。
如果程序中的某条指令一旦执行，不久以后该指令可能再次执行;如果某数据被访问过，不久以后该数据可能再次被访问。产生时间局部性的典型原因，是由于在程序中存在着大量的循环操作。
空间局部性
如果一个存储器的位置被引用，那么将来他附近的位置也会被引用。（顺序结构）
一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，这是因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的。
工作集理论
工作集是进程运行时被频繁访问的页面合集
分类
按位置
内存
外存
按存取方式
按地址存取
随机存取存储器 RAM
顺序存取存储器 SAM
直接存取存储器 DAM
按内容存取
相联存储器（如Cache）
按工作方式
随机存取存储器 RAM

只读存储器 ROM

Cache
概念

地址映象方法
在CPU工作时，送出的是主存单元的地址，而应从Cache存储器中读写信息。这就需要将主存地址转换成Cache存储器的地址，这种地址的转换，称为地址映象 
直接相联映象

硬件电路较简单，但冲突率很高
全相联映象

电路难于设计和实现，只适用于小容量的Cache，冲突率较低
组相联映象

折中办法
注：主存与Cache之间的地址映射由硬件直接完成
主存-编址计算

单位转换
1K = 1024；1k = 1000
位（bit）：二进制数中的一个数位，可以是0或者1，是计算机中数据的最小单位
字节（Byte，B）：计算机中数据的基本单位，1B = 8bit
KB：1KB=1024B
MB：1MB=1024KB
GB：1GB=1024MB
TB：1TB=1024GB
输入输出技术
数据传输控制方式
5种方式占用主机CPU时间按多到少排序为： 程序查询方式（程序控制方式）、 程序中断方式、 DMA工作方式、 通道方式、 I/O处理机
程序控制（查询）方式
分类
无条件传送
程序查询方式
CPU主动查询外设是否完成数据传输，效率极低
方法简单，硬件开销小，但/O能力不高，严重影响CPU的利用率
程序中断方式
与程序控制方式相比，中断方式因为CPU无需等待而提高了传输请求的响应速度
中断处理过程
CPU无需等待也不必查询I/O状态。
当I/O系统准备好以后，发出中断请求信号通知CPU;
CPU接到中断请求后，保存正在执行程序的现场（保存现场），打断的程序当前位置即为断点；
(通过中断向量表)转入I/O中的服务程序的执行，完成I/O系统的数据交换；
返回被打断的程序继续执行(恢复现场)。
DMA方式（直接主存存取）
DMA方式是为了在主存与外设之间实现高速、批量数据交换而设置的。 DMA方式比程序控制方式与中断方式都高效
AC向总线裁决逻辑提出总线请求；CPU执行完当前总线周期即可释放总线控制权。 此时DMA响应，通过DMAC通知I/O接口开始DMA传输
计算机总线
广义上讲，任何连接两个以上电子元器件的导线 
根据所处位置分为
内部总线
用于芯片一级的互连
芯片内总线
用于集成电路芯片内部各部分的连接
元件级总线
用于一块电路板内各元器件的连接
系统总线
用于插件板一级的互连
数据总线 DB
传递数据信息，是双向的。DB的宽度决定了CPU和计算机其他设备之间每次交换数据的位数
地址总线 AB
传送CPU发出的地址信息，是单向的。AB的宽度决定了CPU的最大寻址能力
控制总线 CB
传送控制信号、时序信号、状态信息，CB中的每一条线是单向的，作为一个整体是双向的，以双向线标识。
外部总线
又称通讯总线，用于设备一级的互连
指令系统

基本概念
操作码
支出计算机要执行什么性质的操作，例如：加法、减法、取数、存数等
地址码
需要包含个操作数的地址及操作结果的存放地址等，按地址结构分为
三地址指令
二地址指令
一地址指令
零地址指令
寻址方式

立即寻址
操作数直接在指令中，速度快，灵活性差
直接寻址
指令中存放的是操作数的地址
间接寻址
指令中存放了一个地址，这个地址对应的内容是操作数的地址
寄存器寻址
寄存器存放操作数
寄存器间接寻址
寄存器内存放的是操作数的地址
CISC与RISC
 
CISC（复杂）
RISC（精简）
Flynn分类法

单指令流 单数据流 SISD
单指令流 多数据流 SIMD
多指令流 单数据流 MISD
多指令流 多数据流 MIMD
流水线

流水线计算
 
流水线周期
执行时间最长的一段
流水线吞吐率计算

计算机可靠性

计算机可靠性模型
串联模型

并联模型

N模冗余模型

计算机性能指标
字长和数据通路宽度
主存容量和存取速度
运算速度
主频与CPU时钟周期
时钟周期 = 1/主频 （S）
CPI（平均每条指令的平均时钟周期个数）与 IPC（每（时钟）周期运行指令条数）
MIPS（百万条指令每秒）与 MFLOPS（每秒百万个浮点操作）
MIPS=指令条数/（执行时间×10^6）=主频/CPI=主频×IPC
MFLOPS=浮点操作次数/（执行时间×10^6）
吞吐量与吞吐率
响应时间(RT)与完成时间(TAT)
兼容性
操作系统基本原理
概述

作用
特征
并发性
共享性
虚拟性
不确定性
功能
管理系统的硬件、软件、数据资源
控制程序运行
人机之间的接口
应用软件与硬件之间的接口
工作

进程管理
文件管理
存储管理
设备管理
作业管理
特殊的操作系统
实时操作系统
实时控制系统和实时信息系统
交互能力要求不高，可靠性要求高(规定时间内响应并处理)
嵌入式操作系统
运行在智能芯片环境中
特点：微型化、可定制（针对硬件变化配置）、 实时性、可靠性、易移植性（HAL和RSP支特）
批处理操作系统
单道批：一次一个作业入内存，作业由程序、数据、作业说明书组成
多道批：一次多个作业入内存，特点：多道、宏观上并行微观上串行
分时操作系统
采用时间片轮转的方式为多个用户提供服务，每个用户感觉独占系统
特点：多路性、独立性、交互性和及时性
网络操作系统
方便有效共享网络资源，提供服务软件和有关协议的集合
主要的网络操作系统有：Unix、Linuxi和Windows Server系统
分布式操作系统
任意两台计算机可以通过通信交换信息
是网络操作系统的更高级形式，具有透明性、可靠性和高性能等特性
微机操作系统
Windows:Microsoft;开发的图形用户界面、多任务、多线程操作系统
Linux:免费使用和自由传播的类Unix操作系统，多用户、多任务、多线程和多CPU的操作系统
进程管理
概念
进程是独立资源分配基本单位
线程是独立调度的基本单位
进程的基本属性

可拥有资源的独立单位
可独立调度和分配资源的基本单位
组成
程序块
能被多个进程同时执行，程序执行时，不可修改的部分
程序顺序执行
特征
顺序性
封闭性
可在现行
程序并发执行
特征
失去了程序的封闭性
程序和机器的执行程序的活动不再一一对应
并发程序间的相互制约性
数据块
只能被一个进程所用，程序执行时，可以修改的部分
进程控制块（PCB）
是进程存在的唯一标志
内容
进程标识符、状态、位置信息、控制信息、 队列指针(链接同一状态的进程)、优先级、现场保护区等
进程与程序的区别
进程是程序的一次执行过程，没有程序就没有进程
程序是一个静态的概念，而进程是一个动态的概念，它由创建而产生，完成任务后因撒销而消亡；进程是系统进行资源分配和调度的独立单位，而程序不是
状态

三态模型
运行
当一个进程在CPU上运行时。
(单处理机处于运行态的进程只有一个)
就绪
一个进程获得了除CPU外的一切所需资源，一旦得到处理机即可运行
阻塞
阻塞也称等待或睡眠状态，一个进程正在等待某一事件发生（例如请求I/O等待I/O完成等)而暂时停止运行，此时即使把CPU分配给进程也无法运行，故称进程处于阻塞状态
五态模型
运行
静止就绪
活跃就绪
静止阻塞
活跃阻塞
挂起原因
(1)进程过多，主存资源不足，此时必须将某些进程挂起，放到磁盘对换区，暂时不参与调度，以平衡系统负载
(2)系统出现故障，或者是用户调试程序，也可能需要将进程挂起检查问题
调度
临界资源
诸进程间需要互斥方式对其进行共享的资源
进程中访问临界资源的那段代码称为临界区
进程的同步与互斥
同步

在计算机系统中，多个进程可以并发执行，每个进程都以各自独立的，不可预知的速度向前推进，暂时需要在某些确定点上协调互相合作进程间的工作。
互斥

指系统中对个进程因争用临界资源而互斥执行
信号量机制
信号量
S，一个整型变量，是一种特殊的变量，根据控制对象不同被赋予不同的值
物理意义：S>=0表示某资源的可用数；S<0其绝对值表示阻塞队列中等待该资源的进程数
PV操作
是实现进程同步与互斥的常用方法； 是低级通用原语，在职信期间不可分割； P操作表示申请一个资源，V操作表示释放一个资源 
P操作
S>=0，执行P操作的进程继续执行
S<0，置该进程为阻塞状态，并将其插入阻塞队列
V操作
S>0，执行V操作的进程继续执行
S<=0，从阻塞状态唤醒一个进程，将其插入就绪队列，然后执行V操作的进程继续执行
信号量与PV操作
PV操作与互斥模型

PV操作与同步模型

互斥与同步模型结合

前趋图与PV操作

前趋图

有向无循环图
前趋；后继
死锁
定义
两个以上的进程互相都要求对方已经占有的资源，导致无法继续运行下去的现象
产生的条件
互斥条件
资源互斥
请求保持条件
每个进程占用资源并且等待其他资源
不可剥夺条件
系统不能不哦度哦进程资源
环路条件
进程资源图是一个环路
解决方法：打破4个产生条件
预防
预先静态分配法：破坏“不可剥夺条件”
资源有序分配法：破坏“环路条件”
避免
银行家算法

检测
解除
资源剥夺法
撤销进程法
计算问题
假如系统内有n个进程，每个进程都需要R个资源， 那么发生死锁的最大资源数为n*(R-1)， 不发生死锁的最小资源数为n*(R-1)+1
进程资源图
用来表示进程和资源之间的分配和请求关系
P代表进程，R代表资源，R方框中有几个圆球就表示有几个这种资源，在图中，R1指向P1,表示R1有一个资源已经分配给了P1,P1指向R2,表示P1还需要请求一个R2资源才能执行

阻塞节点
某进程所请求的资源已经全部分配完毕，无法获取所需资源，该进程被阻塞了无法继续。如上图中P2
非阻塞节点
某进程所请求的资源还有剩余，可以分配给该进程继续运行。如上图中P1、P3
当一个进程资源图中所有进程都是阻塞节点时，即陷入死锁状态
存储管理
页式存储管理

将程序与内存均划分为同样大小的块，以页为单位将程序调入内存
物理块号又称页帧号
结构
逻辑地址：页号+页内地址
物理地址：页帧号+页内地址
优缺点
优点：利用率高，碎片小（只有最后一页有），分配及管理简单
缺点：增加了系统开销，可能产生抖动
页面置换算法
最佳置换算法 OPT
理论上的算法，无法实现，是在进程执行完后进行的最佳效率计算，用来让其他算法比较差距。原理是选择未来最长时间内不被访问的页面置换，这样可以保证未来执行的都是马上要访问的。
先进先出算法 FIFO
先调入内存的页先被置换淘汰， 会产生抖动现象，即分配的页数越多，缺页率可能越多（即效率越低）
最近最少使用 LRU
在最近的过去，进程执行过程中，过去最少使用的页面被置换淘汰，根据局部性原理，这种方式效率高，且不会产生抖动现象
段式存储管理

按用户作业中的自然段来划分逻辑空间，然后调入内存，段的长度可以不一样。
地址表示：(段号，段内偏移)：其中段内偏移不能超过该段号对应的段长，否则越界错误，而此地址对应的真正内存地址应该是：段号对应的基地址+段内偏移。
优点
程序逻辑完整，修改互不影响
缺点
内存利用率低，内存碎片浪费大
段页式存储管理
 
对进程空间先分段，后分页
优点：空间浪费小、存储共享容易、能动态连接。
缺点：由于管理软件的增加，复杂性和开销也增加，执行速度下降
磁盘管理
磁盘结构

读取磁盘数据的时间包括
(1)找磁道的时间。
(2)找块（扇区）的时间，即旋转延迟时间。
(3)传输时间。
存取时间
存取时间 = 寻道时间+等待时间（平均定位时间 + 转动延时）
磁盘扫描算法
先来先服务(FCFS)
最短寻道时间优先(SSTF)
扫描算法(SCAN)/电梯算法（双向）
循环扫描算法(CSCAN)（单向）
I/O管理软件

硬件
完成具体的I/O操作
中断处理程序
I/O完成后唤醒设备驱动程序
设备驱动程序
设置寄存器，检查设备状态
设备无关I/O层
设备名解析、阻塞进程、分配缓冲区
用户级I/O层
发出I/O调用
文件管理
概念
文件：具有符号名的、在逻辑上具有完整意义的一组相关信息项的集合
文件属性
只执行、隐含、只读、读/写、共享、系统
文件结构
逻辑结构
有结构的记录式文件、无结构的流式文件
物理结构
连续结构、链接结构、索引结构、多个物理块的索引表
文件目录
文件目录项/文件的说明/文件控制块FCB
基本信息类
文件名、文件的物理地址、文件长度和文件块数等
存储控制信息类
文件的存储权限：读写、执行权限等
使用信息类
文件建立日期、最后一次修改/访问日期、当前使用的信息、 打开文件的进程数以及在文件上的等待队列等
目录结构
一级目录结构
线性结构，查找速度慢，不允许重名和实现文件共享等
二级目录结构
主文件目录(MFD)+用户目录(UFD)
三级目录结构
树型目录结构（多级目录结构）
树型目录结构（多级目录结构）

相对路径
是从当前路径开始的路径
绝对路径
是从根目录开始的路径
全文件名
绝对路径+文件名
空闲存储空间管理

位示图法
对每个物理空间用一位标识，为1则使用，为0则空闲，形成一张位示图
空闲区表法
将所有空闲空间整合成一张表，即空闲文件目录
空闲链表法
将所有空闲空间链接成一个链表，根据需要分配
成组链接法
既分组，每组内又链接成链表，是上述两种方法的综合
索引文件结构

作业管理

先来先服务法
时间片轮转法
短作业优先法
最高优先权优先法
高响应比优先法
数据库技术基础
基本概念
数据库系统的体系结构
集中式数据库系统
数据是集中的
数据管理是集中的
数据库系统的素有功能（从形式的用户接口到DBMS核心)都
集中在DBMS所在的计算机
C/S结构
客户端负责数据表示服务
服务器主要负责数据库服务
数据库系统分为前端和后端
ODBC、JDBC
分布式数据库
局部数据库位于不同的物理位置，使用一个全局DBMS将所有局部数据库联网管理，这就是分布式数据库
物理上分布、逻辑上集中
物理上分布、逻辑上分布
分片模式
水平分片
将表中水平的记录分别存放在不同的地方
垂直分片
将表中的垂直的列值分别存放在不同的地方
特点
数据独立性
除了数据的逻辑独立性与物理独立性外，还有数据分布独立性（分布透明性）
集中与自治共享结合的控制结构
各局部的DBMS可以独立地管理局部数据库，具有自治的功能。同时，系统又设有集中控制机制，协调各局部DBMS的工作，执行全局应用
适当增加数据冗余度
在不同的场地存储同一数据的多个副本， 可以提高系统的可靠性和可用性，同时也能提高系统性能
提高系统的可用性，即当系统中某个节点发生故障时，因为数据有其他副本在非故障场地上，对其他所有场地来说，数据仍然是可用的，从而保证数据的完备性
全局的一致性、可串行性和可恢复性
透明性
分片透明性
是指用户不必关心数据是如何分片的，它们对数据的操作在全局关系上进行，即如何分片对用户是透明的
复制透明性
用户不用关心数据库在网络中各个节点的复制情况，被复制的数据的更新都由系统自动完成
位置透明性
是指用户不必知道所操作的数据放在何处，即数据分配到哪个或哪些站点存储对用户是透明的
局部映像透明性（逻辑透明）
是最低层次的透明性，该透明性提供数据到局部数据库的映像，即用户不必关心局部DBMS支持哪种数据模型、使用哪种数据操纵语言，数据模型和操纵语言的转换是由系统完成的。因此，局部映像透明性对异构型和同构异质的分布式数据库系统是非常重要的
并行数据库
共享内存式
无共享式
三级模式-两级映象

三级模式

内模式
又称存储模式，管理如何存储物理的数据，对应具体物理存储文件
模式
又称为概念模式，就是我们通常使用的基本表，根据应用、需求将物理数据划分成一张张表
外模式
又称用户模式，对应数据库中的视图这个级别将表进行一定的处理后再提供给用户使用
两级映象
模式一内模式映像
是表和数据的物理存储之间的映射，存在于概念级和内部级之间， 若修改了数据存储方式，只需要修改此映射，而无需修改应用程序
物理独立性
外模式一模式映像
是表和视图之间的映射，存在于概念级和外部级之间， 若表中数据发生了修改，只需要修改此映射，而无需修改应用程序
逻辑独立性
数据仓库
数据仓库是一种特殊的数据库，也是按数据库形式存储数据的，但是目的不同： 数据库经过长时间的运行，里面的数据会保存的越来越多，就会影响系统运行效率， 对于某些程序而言，很久之前的数据并非必要的， 因此，可以删除掉以减少数据，增加效率，考虑到删除这些数据比较可惜， 因此，一般都将这些数据从数据库中提取出来保存到另外一个数据库中，称为数据仓库
特点
数据仓库的目的不是为了应用，是面向主题的，用来做数据分析，集成不同表， 而且是相对稳定的，一般不会做修改，同时会在特定的时间点，做大量的插入， 反映历史的变化
作用
用来做数据的查询、分析、生成报表
使用数据挖掘工具对这些历史数据进行挖掘，查找数据间的关系，发现剩余价值
数据挖掘的分析方法
关联分析
关联分析主要用于发现不同事件之间的关联性， 即一个事件发生的同时，另一个事件也经常发生
序列分析
序列分析主要用于发现一定时间间隔内接连发生的事件， 这些事件构成一个序列，发现的序列应该具有普遍意义
分类分析
分类分析通过分析具有类别的样本特点，得到决定样本属于各种类别的规则或方法。 分类分析时首先为每个记录赋予一个标记（一组具有不同特征的类别）， 即按标记分类记录，然后检查这些标定的记录，描述出这些记录的特征
聚类分析
聚类分析是根据“物以类聚”的原理，将本身没有类别的样本聚集成不同的组， 并且对每个这样的组进行描述的过程
商业智能（BI）系统

数据预处理
是整合企业原始数据的第一步
过程（ETL过程）
数据的抽取（Extraction）
转换（Transformation）
加载（Load）
建立数据仓库
是处理海量数据的基础
数据分析
是体现系统智能的关键
联机分析处理（OLAP）

不仅进行数据汇总/聚集，同时还提供切片、切块、下钻、上卷和旋转等数据分析功能，用户可以方便地对海量数据进行多维分析
数据挖掘
挖掘数据背后隐藏的知识，通过关联分析、聚类和分类等方法建立分析模型，预测企业未来发展趋势和将要面临的问题
数据展现
保障系统分析结果的可视化
大数据
特点
大量化
多样化
价值密度低
快速化
与传统数据的比较

要处理大数据，一般使用集成平台，称为大数据处理系统
特征
高度可扩展性、高性能、高度容错、支持异构环境、 较短的分析延迟、易用且开放的接口、较低成本、向下兼容性
数据库设计

需求分析
即分析数据存储的要求，产出物有数据流图、数据字典、需求说明书
概念结构设计

就是设计E-R图，也即实体-属性图，与物理实现无关，说明有哪些实体，实体有哪些属性
逻辑结构设计
将E-R图，转换成关系模式，也即转换成实际的表和表中的列属性，这里要考虑很多规范化的东西
物理设计
根据生成的表等概念，生成物理数据库， 聚簇索引
数据库设计过程
概念结构设计阶段
集成
集成的方法
多个局部E—R图一次集成
逐步集成，用累加的方式一次集成两个局部E—R
集成产生的冲突及解决办法：（针对同一对象）
属性冲突
命名冲突
E-R模型

实体-联系模型
使用椭圆表示属性（一般没有）、 长方形表示实体、 菱形表示联系，联系两端要标注联系类型
实体
实体是现实世界中可以区别于其他对象的事件或事物 (实体集一实体的集合)
弱实体

在现实世界中有一种特殊的依赖联系，该联系是指某实体是否存在对于另些实体具有很强的依赖关系，即一个实体的存在必须以另一个实体为前提，而将这类实体称为弱实体，如家属与职工的联系，附件与邮件
特殊化

在现实世界中，某些实体一方面具有一些共性，另一方面还具有各自的特性，一个实体集可以按照某些特征区分为几个子实体
聚集

一个联系作为另一个联系的一端
属性
属性是实体某方面的特性
属性分类
简单属性和复合属性（属性是否可以分割）
单值属性和多值属性（属性有多个取值）
NULL属性（无意义）
派生属性（可由其他属性生成）
联系
实体的联系分为实体内部的联系和实体与实体间的联系
联系类型
一对一1:1
一对多1:N
多对多M:N
逻辑结构设计阶段
数据模型
数据模型三要素
数据结构（所研究的对象类型的集合）
数据操作（对数据库中各种对象的实例允许执行的操作的集合）
数据的约束条件（一组完整性规则的集合）
关系模型

概念
目或度
关系模式中属性的个数
数据库中常用的表
基本关系表
查询表
视图表
键与约束
键
超键
能唯一标识此表的属性的组合
候选键
超键中去掉冗余的属性，剩余的属性就是候选键
唯一标识元组，且无冗余
属性集合
可以是1个或者多个
可以是单属性或者多属性
图示法求候选键

主键
任选一个候选键，即可作为主键
外键
其他表中的主键
主属性
候选键内的属性为主属性，其他属性为非主属性
约束
实体完整性约束
即主键约束，主键值不能为空，也不能重复
参照完整性约束
即外键约束，外键必须是其他表中已经存在的主键的值，或者为空
用户自定义完整性约束
自定义表达式约束，如设定年龄属性的值必须在0到150之间
E-R转换成关系模型
每个实体都对应一个关系模式
联系转关系模式
一对一联系的转换

独立的关系模式：并入两端主键及联系自身属性。（主键：任一端主键）
归并（任意一端）：并入另一端主键及联系自身属性。(主键：保特不变)
一对多联系的转换

独立的关系模式：并入两端主键及联系自身属性。(主键：多端主键)
归并（多端）：并入另一端主键及联系自身属性。(主键：保持不变)
多对多联系的转换

独立的关系模式：并入两端主键及联系自身属性。（主键：两端主键的组合键）
关系代数
关系运算
并
S1US2，结果是两张表中所有记录数合并，相同记录只显示一次
交
S1∩S2，结果是两张表中相同的记录
差
S1-S2，结果是S1表中有而S2表中没有的那些记录
笛卡尔积
S1×S2，产生的结果包括S1和S2的所有属性列， 并且S1中每条记录依次和S2中所有记录组合成一条记录， 最终属性列为S1+S2属性列，记录数为S1×S2记录数
投影
实际是按条件选择某关系模式中的某列A，列也可以用数字表示
选择
实际是按条件选择某关系模式中的某条记录
图示

自然连接
结果显示全部的属性列，但是相同属性列只显示一 次，显示两个关系模式中属性相同且值相同的记录

关系数据库的规范化
函数依赖
定义
给定一个x，能唯一确定一个Y，就称X确定Y（X->Y），或者说Y依赖于x，例如Y=X*X函数
扩展两种规则
部分函数依赖

A可确定C，(A,B)也可确定C，(A,B)中的一部分（即A）可以确定C，称为部分函数依赖
传递函数依赖

当A和B不等价时，A可确定B，B可确定C，则A可确定C，是传递函数依赖； 若A和B等价，则不存在传递，直接就可确定C
公理系统

数据问题
数据冗余
修改异常
插入异常
删除异常
范式
第一范式1NF
所有属性都不可以再分割为两个或多个分量
第二范式2NF
当且仅当R是1NF，且每一个非主属性完全依赖主键（不存在部分依赖）时，R就是2NF。比较典型的例子就是候选键是单属性，单属性是不可能存在部分函数依赖的
第三范式3NF
当且仅当R是2NF，且R中没有非主属性传递依赖于候选键时，R就是3NF（此时，也不会存在部分依赖），一般解决方法是拆分传递依赖的非主属性为一个新的关系模式。本质就是主键要直接决定所有非主属性，不能通过非主属性间接决定
BC范式BCNF
R属于BCNF当且仅当其F中每个依赖的决定因素必定包含R的某个候选码
模式分解
范式之间的转换一般都是通过拆分属性，即模式分解， 将具有部分函数依赖和传递依赖的属性分离出来，来达到一步步优化
分类
保持函数依赖分解
对于关系模式R，有依赖集F，若对R进行分解，分解出来的多个关系模式，保持原来的依赖集不变，则为保持函数依赖的分解。另外，注意要消除掉冗余依赖（如传递依赖）
实例：设原关系模式R(A,B,C)，依赖集F(A->B, B->C, A->C)，将其分解为两个关系模式R1(A,B)和R2(B,C)，此时R1中保持依赖A->B，R2保持依赖B->C，说明分解后的R1和R2是保持函数依赖的分解，因为A->C这个函数依赖实际是一个冗余依赖，可以由前两个依赖传递得到，因此不需要管。
无损分解
分解后的关系模式能够还原出原关系系模式，就是无损分解，不能还原是有损
判断方法
表格法

定理：如果R的分解为p={R1，R2}，F为R所满足的函数依赖集合， 分解p具有无损连接性的充分必要条件是 R1∩R2->(R1-R2)或者R1∩R2->(R2-R1)
SQL
语法关键字

创建表：create table
指定主键：primary key()
指定外键：foreign key()
修改表：alter table
删除表：drop table
索引：index
视图：view
操作
数据库查询 select...from...where...

group by...having...

分组查询
分组时要注意select后的列名要适应分组
having为分组查询附加条件
order by...
排序order by
权限控制

更名运算as
select oldname as newname from t1
字符串匹配like
% 匹配多个字符串
_ 匹配任意一个字符串
数据库插入 insert into...values()
insert into t1 values('a',66)
数据库删除 delete from...where
数据库修改 update...set...where
DISTINCT
过滤重复的选项，只保留一条记录
UNION
出现在两个SQL语句之间，将两个SQL语句的查询结果取或运算， 即值存在于第一句或第二句都会被选出
INTERSECT
对两个SQL语句的查询结果做与运算，即值同时存在于两个语句才被选出
MIN、AVG、MAX
分组查询时的聚合函数
并发控制
事务管理
概念
事务是一个操作序列，这些操作要么都做，要么不做， 是数据库环境中不可分割的逻辑工作单位； 事务和程序是两个不同的概念，一般一个程序可包含多个事务
特性（ACID性质）
（操作）原子性
要么全做，要么全不做
（数据）一致性
事务发生后数据是一致的，例如银行转账，不会存在A账户转出，但是B账户没收到的情况
（执行）隔离性
任一事务的更新操作直到其成功提交的整个过程对其他事务都是不可见的，不同事务之间是隔离的，互不干涉
（改变）持续性
事务操作的结果是持续性的
持久性(Durability):一旦事务成功提交，即使数据库崩渍，其对数据库的更新操作也永久有效
事务定义的语句
事务开始（BEGIN TRANSACTION）
事务提交（COMMIT）
事务回滚（ROLLBACK）
并发控制
事务是并发控制的前提条件，并发控制就是控制不同的事务并发执行，提高系统效率
并发控制中存在三个问题
丢失更新
事务1对数据A进行了修改并写回，事务2也对A进行了修改并写回，此时事务2写回的数据会覆盖事务1写回的数据，就丢失了事务1对A的更新。即对数据A的更新会被覆盖。
不可重复读
事务2读A，而后事务1对数据A进行了修改并写回，此时若事务2再读A，发现数据不对。即一个事务重复读A两次，会发现数据A有误。
读脏数据
事务1对数据A进行了修改后，事务2读数据A，而后事务1回滚，数据A恢复了原来的值，那么事务2对数据A做的事是无效的，读到了脏数据
并发控制技术
封锁
排它锁（X锁）
若事务T对数据对象A加上x锁，则只允许T读取和修改A，其他事务都不能再对A加任何类型的锁，直到T释放A上的锁。
共享锁（S锁）
若事务T对数据对象A加上S锁，则只允许T读取A，但不能修改A，其他事务只能再对A加S锁（也即能读不能修改），直到T释放A上的S锁
数据库设计题
答题技巧

详细分析试题说明 结合题干
详细分析试题说明
“每个部门可以有多名员工，每名员工只属于一个部门”，部门和员工之间存在1：多的联系。
“采购完的商品交由配送员根据顾客订单组合装箱，然后交给托运公司运送”，这里存在配送员、订单、托运公司三元联系，其中订单是联系名称，作为另一个联系的一端，存在聚集形式
关系模式属性判断
“托运公乱信息包括托运公司名称、电话和地址”，托运公司（托运公司名称，电话，地址)（注意关系模式中的属性可能会有联系的归并处理)
主键判断
“系统内部用商品条码唯一标识每种商品”，商品条码是商品的主键。(外键判断来源于其他关系的主健)
熟练掌握基本知识
网络与计算机安全
网络概述
计算机网络
概念
计算机网络是计算机技术与通信技术相结合的产物， 它实现了远程通信、远程信息处理和资源共享
功能
数据通信
资源共享
负载均衡
高可靠性
分类
按分布范围分
局域网（LAN）
城域网（MAN）
广域网（WAN）
因特网
按拓扑结构分
总线型

利用率低、干扰大、价格低
星型

交换机形成的局域网、中央单元负荷大
环型

流动方向固定、效率低扩充难
树型

总线型的扩充、分级结构
分布式

任意节点连接、管理难成本高
ISO/OSI参考模型

物理层
二进制数据传输，物理链路和物理特性相关
中继器
集线器（多端口中继器）
在同一个冲突域
数据链路层
将数据封装成帧进行传送，准确传送至局域网内的物理主机上
网卡，网桥
交换机（多端口网桥）
多个端口在同一个网络，即一个广播域
一个接口对应一个冲突域
网络层
数据分组传输和路由选择，能准确的将数据传送至互联网的网络主机上
路由器
一个端口连接不同的网络
一个接口对应一个广播域，一个冲突域
三层交换机
传输层
端到端的连接，传送数据至主机端口上
会话层
管理主机之间的会话，提供会话管理服务（建立、维护和结束会话）
表示层
提供解释所交换信息含义的服务，包括数据之间的格式转换、压缩、加密等操作，对数据进行处理
应用层
实现具体的应用功能。直接进程间的通信
网关（连接不同类型且协议差别较大的网络，协议转换）
默认网关
一台主机可以有多个网关。 默认网关的意思是一台主机如果找不到可用的网关， 就把数据包发给默认指定的网关，由这个网关来处理数据包。 现在主机使用的网关，一般指的是默认网关
默认网关的IP地址必须与本机IP地址在同一个网段内，即同网络号
TCP/IP协议族
特性
逻辑编址（网卡-物理地址，Internet-逻辑地址）
路由选择（定义路由器如何选择网络路径）
域名解析（域名解析为IP地址）
错误检测和流量控制（可靠性、防止拥塞）
TCP/IP分层模型

应用层
具体应用功能
传输层
提供应用程序间端到端的通信
网际层
又称IP层，处理机器间的通信，数据以分组为单位
网络接口层
又称为数据链路层，负责接收IP数据报，并把数据报通过选定的网络发送出去
协议
网际层协议
IP：最重要核心的协议，无连接、不可靠
ICMP：因特网控制信息协议，用来检测网络通信是否顺畅
ARP和RARP：地址解析协议，ARP是将IP地址转换为物理地址，RARP是将物理地址转换为IP地址
传输层协议
UDP协议：不可靠连接，因为数据传输只管发送，不用对方确认，因此可能会有丢包现象。一般用于视频、音频数据传输
TCP协议：可靠连接，因为有验证机制，每发送一个数据包，都要求对方回复确认 初始建立连接，有三次握手机制，即A发送连接信息给B， B收到后回复确认帧，A收到确认帧后再发送确认，才能建立连接 HTTP、FTP、Telnet、PoP3、SMTP

停止等待协议
TCP保证可靠传输的协议,停止等待”就是指发送完一个分组就停止发送, 等待对方的确认,只有对方确认过,才发送下一个分组
连续ARQ协议
TCP保证可靠传输的协议，它是指发送方维护着一个窗口,这个窗口中不止一个分组,有好几个分组,窗口的大小是由接收方返回的win值决定的,所以窗口的大小是动态变化的,只要在窗口中的分组都可以被发送,这就使得TCP一次不是只发送一个分组了,从而大大提高了信道的利用率.并且它采用累积确认的方式,对于按序到达的最后一个分组发送确认
滑动窗口协议
TCP流量控制协议，可变的窗口是不断向前走的,该协议允许发送方在停止并等待确认前发送多个数据分组。由于发送方不必每发一个分组就停下来等待确认，因此该协议可以加速数据的传输,还可以控制流量的问题
应用层协议

基于TCP的FTP、HTTP等都是可靠传输。基于UDP的DHCP、DNS等都是不可靠传输
FTP：可靠的文件传输协议
HTTP：超文本传输协议，用于上网。使用SSL加密后的安全网页协议为HTTPS
SMTP和POP3：邮件传输协议，邮件报文采用ASCII格式表示
Telnet：远程连接协议，可靠但不安全
TFTP：不可靠的小文件传输协议
SNMP：简单网络管理协议，必须以管理员的身份登录才能完成配置
DHCP：动态分配IP地址协议，客户机/服务器模型，租约默认为8天，当租约过半时，客户机需要向DHCP服务器申请续租，当租约超过87.5%时，如果仍然没有和当初提供IP地址的DHCP服务器联系上，则开始联系其他DHCP服务器

DNS

域名解析协议，将域名解析为IP地址
DNS服务器
维持域名和IP地址对应的表格
层次结构
本地域名服务器
权威域名服务器
顶级域名服务器
根域名服务器
输入网址（即域名）后， 首先会查询本地DNS缓存， 无果后再查询本地DNS服务器
递归查询
主机提出一个查询请求，本地服务器会自动一层一层的查询下去， 直到找到满足查询请求的IP地址，再返回给主机。即问一次，就得最终结果
迭代查询
服务器收到一次查询请求，就回答一次，但是回答的不一定是最终地址， 也可能是其他层次服务器的地址，然后等待客户端再去提交查询请求。 即问一次答一次，而后再去问其他服务器，直至问到结果
主机向本地域名服务器额查询采用递归查询； 本地域名服务器向根域名服务器的查询通常采用迭代查询。 （依据是域名服务器是否空闲）
网络诊断命令
常见网络诊断命令扩展
ping
用于检查网络是否连通
tracert(inux:traceroute)
用于确定IP数据包访问目标所采取的路径，若网络不通，能定位到具体哪个结点不通
ipconfig(linux:ifconfig)
显示TCP/IP网络配置值，如：P地址，MAC地址，网关地址等
nslookup
查询DNS记录
Netstat
用于显示网络连接、路由表和网络接口信息
LISTEN
侦听来自远方的TCP端口的连接请求
SYN-SENT
在发送连接请求后等待匹配的连接请求
SYN-RECEIVED
在收到和发送一个连接请求后等待对方对连接请求的确认
ESTABLISHED
代表一个打开的连接
FIN-WAIT-1
等待远程TCP连接中断请求，或先前的连接中断请求的确认
FIN-WAIT-2
从远程TCP等待连接中断请求
CLOSE-WAIT
等待从本地用户发来的连接中断请求
CLOSING
等待远程TCP对连接中断的确认
LAST-ACK
等待原来的发向远程TCP的连接中断请求的确认
TIME-WAIT
等待足够的时间以确保远程TCP接收到连接中断请求的确认
CLOSED
没有任何连接状态
IP地址与子网划分
IP地址
IP地址分四段，每段八位，共32位二进制数组成， 在逻辑上，这32位IP地址分为网络号和主机号 依据网络号位数的不同，可以将IP地址分为以下几类
A类地址网络号占8位，主机号则为32-8=24位，能分配的主机个数为2^24-2个（注意：主机号为全0和全1的不能分配，是特殊地址） 同理，B类地址网络号为16位，C类地址网络号为24位，同样可推算出主机号位数和主机数。 图中红色的位数表示该位固定为该值，是每类IP地址的标识 
特殊的IP地址
127网段
回播地址，本地环回地址
主机号非全0和非全1
可作为子网中的主机号使用
主机号全0地址
代表这个网络本身，可作为子网地址使用
主机号全1地址
特定子网的广播地址
169.254.0.0
保留地址，用于DHCP失效Win)
0.0.0.0
保留地址，用于DHCP失效(Linux)
子网划分与路由汇聚
按上述划分的AB C三类，一般是最常用的，但是却并不实用， 因为主机数之间相差的太大了，不利于分配
因此，我们一般采用子网划分的方法来划分网络，即自定义网络号位数，就能自定义主机号位数，就能根据主机个数来划分出最适合的方案，不会造成资源的浪费
因此就有子网的概念，一般的IP地址按标准划分为AB C类后，可以进行再一步的划分，将主机号拿出几位作为子网号，就可以划分出多个子网，此时IP地址组成为：
网络号+子网号+主机号
还可以聚合网络为超网，就是划分子网的逆过程，将网络号取出几位作为主机号， 此时，这个网络内的主机数量就变多了，成为一个更大的网络
子网号可以为全0和全1，主机号不能为全0或全1，因此，主机数需要-2，而子网数不用
子网掩码
网络号和子网号都为1，主机号都为0
255.255.255.0
IPv6
为了解决IPv4地址数不够用的情况而提出的设计方案
特性
IPv6地址长度为128位，地址空间增大了2^96倍
灵活的IP报文头部格式，使用一系列固定格式的扩展头部取代了IPv4中可变长度的选项字段。IPv6中选项部分的出现方式也有所变化，使路由器可以简单撸过选项而不做任何处理，加快了报文处理速度
IPv6简化了报文头部格式，加快报文转发，提高了吞吐量；
提高安全性，身份认证和隐私权是IPv6的关键特性
支持更多的服务类型；
允许协议继续演变，增加新的功能，使之适应未来技术的发展
分类
单播地址(Unicast)
用于单个接口的标识符，传统的点对点通信
可聚合全球单播地址
前缀001
本地单播地址
链路本地：前缀为1111111010（一般以fe80开头）
站点本地：前级为1111111011
组播地址(Multicast)
多播地址，一点对多点的通信，数据报交付到一组计算机中的每一个。PV6没有广播的术语，而是将广播看做多播的一个特例
前缀为11111111
任播地址(Anycast)
泛播地址，这是IPv6增加的一种类型。任播的目的站是一组计算机，但数据包在交付时只交付给其中一个，通常是举例最近的一个
前缀固定，其余位置为0
写法

IPV6地址由8个16进制字段构成
IPv4和IPv6的过渡期间，主要采用三种基本技术
双协议栈
主机同时运行IPv4和IPv6两套协议栈，同时支持两套协议
隧道技术
隧道技术通过在IPV4网络中部署隧道， 实现在IPV4网络上对Pv6业务的承载，保证业务的共存和过渡
6to4隧道；6over4隧道；ISATAP隧道
NAT-PT技术
NAT-PT使用网关设备连接IPv6和IPV4网络。 当IPV4和IPV6节点互相访问时，NAT-PT网关实现两种协议的转换翻译和地址的映射
网络规划与设计
需求分析
网络功能要求
网络的性能要求
网络运行环境的要求
网络的可扩充性和可维护性要求
网络规划原则
实用性原则
开放性原则
先进性原则
网络设计与实施原则
可靠性原则
安全性原则
高效性原则
可扩展性原则
层次化网络设计

核心层
主要是高速数据交换，实现高速数据传输、出口路由，常用冗余机制
功能单一，只负责高速的数据交换
汇聚层
网络访问策略控制、数据包处理和过滤、策略路由、广播域定义、寻址
功能多样，可以有多层，包括网络访问策略、数据包的处理、过滤、寻址等中间操作
接入层
主要是针对用户端，实现用户接入、计费管理、MAC地址认证、MAC地址过滤、收集用户信息，可以使用集线器代替交换机
功能单一，向本地网段提供用户接入
网络接入技术
有线接入
公用交换电话网络(PSTN)
数字数据网(DDN)
综合业务数字网(ISDN)
非对称数字用户线路(ADSL)
上行/下行不同
静态IP
PPPOA
ATM
PPPOE
以太网
同轴光纤技术(HFC)
无线接入
IEEE 802.11(WiFi)
IEEE802.15(蓝牙Bluetooth)
红外（IrDA）
WAPI
手机

WWW服务
URL
Internet地址：域名格式和IP地址格式
统一资源定位符，是互联网上标准资源的地址。互联网上的每个文件都有一个唯一的UL,它包含的信息指出文件的位置以及浏览器应该怎么处理它
协议名://主机名.组名.最高层域名
例：http:/www,baidu.com
protocol ://hostname[:port]/path /filename
protocol
指定使用的传输协议，最常见的是HTTP或者HTTPS协议，也可以有其他协议， 如fle、ftp、gopher、.mms、ed2k等
Hostname
指主机名，即存放资源的服务域名或者IP地址
Port
指各种传输协议所使用的默认端口号，例如http的默认端口号为80，一般可以省略
Pth
是指路径，由一个或者多个“/”分隔，一般用来表示主机上的一个目录或者文件地址
filename
指文件名，该选项用于指定需要打开的文件名称
一般情况下，一个UL可以采用"主机名.域名"的形式打开指定页面， 也可以单独使用"域名"打开指定页面，但是这样实现的前提是需进行相应的设置和对应
域名

HTML

其他应用
网络地址翻译NAT
公司内有很多电脑，在公司局域网内可以互联通信，但是要访问外部因特网时，只提供固定的少量P地址能够访问因特网，将公司所有电脑这个大的地址集合映射到能够访问因特网的少量P地址集合的过程就称为NAT
默认网关
一台主机可以有多个网关。默认网关的意思是一台主机如果找不到可用的网关，就把数据包发给默认指定的网关，由这个网关来处理数据包。现在主机使用的网关，一般指的是默认网关
默认网关的P地址必须与本机P地址在同一个网段内，即同网络号
冲突域和广播域
路由器可以阻断广播域和冲突域，交换机只能阻断冲突域，因此一个路由器下可以划分多个广播域和多个冲突域；一个交换机下整体是一个广播域，但可以划分多个冲突域；而物理层设备集线器下整体作为一个冲突域和一个广播域
虚拟局域网VLAN
是一组逻辑上的设备和用户，这些设备和用户并不受物理位置的限制，可以根据功能、部门及应用等因素将它们组织起来，相互之间的通信就好像它们在同一个网段中一样。VLAN工作在OSI参考模型的第2层和第3层，一个VLAN就是一个广播域，VLAN之间的通信是通过第3层的路由器来完成的。与传统的局域网技术相比较，VLAN技术更加灵活，它具有以下优点：网络设备的移动、添加和修改的管理开销减少；可以控制广播活动；可提高网络的安全性
虚拟专用网VPN
是在公用网络上建立专用网络的技术。其之所以称为虚拟网，主要是因为整个VPN网络的任意两个节点之间的连接并没有传统专网所需的端到端的物理链路，而是架构在公用网络服务商所提供的网络平台，如Internet、ATM(异步传输模式）Frame Relay（帧中继）等之上的逻辑网络，用户数据在逻辑链路中传输
局域网的协议
IEEE802.3标准以太网（CSMA/CD），速度为10Mbps，传输介质为同轴电缆
IEEE802.3u为快速以太网，速度为100Mbps，传输介质为双绞线
IEEE802.3z为千兆以太网，速度为1000Mbps，传输介质为光纤或双绞线
IEEE802.4令牌总线网。IEEE802.5令牌环网
无线局域网CSMA/CA（载波侦听多路访问方法）
广域网的协议
点对点协议PPP（拨号上网）
数字用户线xDSL（ADSL上传网速和下载网速不对等，下载网速一般很快）
数字专线DDN（市内或长途的数据电路）
帧中继（以帧为传输单位）
PPP
点对点传输
信息安全
信息系统安全属性
机密性：确保信息不暴露给未授权的实体或进程。
最小授权原则、防暴露、信息加密、物理保密
完整性：只有得到允许的人才能修改数据，并且能够判断出数据是否已被篡改。
消息摘要、数字签名
可用性：得到授权的实体在需要时可访问数据，即攻击者不能占用所有的资源而阻碍授权者的工作。
可控性：可以控制授权范围内的信息流向及行为方式。
可审查性：对出现的信息安全问题提供调查的依据和手段。
审计
加密技术与认证技术
对称加密技术（共享密钥加密）

缺陷：加密强度不高，密钥分发困难
优点：效率高，大量明文加密
AES
DES
3DES(三重DES)
IDEA算法
RC-5
非对称加密技术（公开密钥加密）

缺陷：加密速度慢
RSA
512位（或1024位）密钥、计算量极大、难破解
Elgamal
其基础是Diffie-Hellman密钥交换算法
ECC
椭圆曲线算法
其它
背包算法、Rabin、D-H
应用
信息摘要

单向散列函数（单向Hash函数）、固定长度的散列值
常用的消息摘要算法有MD5,SHA等， 市场上广泛使用的MD5,SHA算法的散列值分别为128和160位， 由于SHA通常采用的密钥长度较长，因此安全性高于MD5
数字签名

确保发送者身份不可假冒（真实性）
发送者身份不可抵赖
信息不被篡改（完整性）
数字信封
发送方将原文用对称密钥加密传输，而将对称密钥用接收方公钥加密发送给对方 接收方收到电子信封，用自己的私钥解密信封，取出对称密钥解密得原文
数字证书

包含
公钥
名称
CA签名
PGP
PGP可用于电子邮件，也可以用于文件存储。
网络安全协议
各个网络层次的安全保障

SSL协议
被设计为加强Web安全传输(HTTP/HTTPS/)的协议（还有SMTP/NNTP等）
用于网银交易
三方面的服务
用户和服务器的合法性验证、加密数据以隐藏被传输的数据、保护数据的完整性
实现过程
接通阶段一一密码交换阶段（客户端和服务器之间交换双方认可的密码)一一会谈密码阶段（客户端和服务器之间产生彼此交谈的会谈密码)一一检验阶段一一客户认证阶段一一结束阶段
SSH被设计为加强Telnet/FTP安全的传输协议
网络安全威胁
主动攻击与被动攻击

被动攻击
监听（保密性）
消息内容获取
业务流分析
主动攻击
中断
可用性
篡改
完整性
伪造
真实性
计算机病毒与木马
病毒
编制或者在计算机程序中插入的破坏计算机功能或者破坏数据， 影响计算机使用并且能够自我复制的一组计算机指令或者程序代码
传染性、隐蔽性、潜伏性、触发性、破坏性、针对性、衍生性、寄生性、未知性
木马
是一种后门程序，场被黑客用作控制远程计算机的工具， 隐藏在被控制电脑上的一个小程序监控电脑一切操作并盗取信息
病毒和木马种类

木马
QQ消息尾巴木马，特洛伊木马
系统引导型病毒
引导盘
文件外壳型病毒
exe文件
网络型病毒
电子邮件
目录型病毒
蠕虫病毒（感染EXE文件）
熊猫烧香，罗密欧与朱丽叶，恶鹰，尼姆达，冲击波
宏病毒（感染word、excel等文件中的宏变量）
美丽沙，台湾1号
CIH病毒
史上唯一破坏硬件的病毒
红色代码
蠕虫病毒+木马
网络安全控制技术
防火墙

是在内部网络和外部因特网之间增加的一道安全防护措施， 它认为内部网络是安全的，外部网络是不安全的
网络级防火墙
层次低，但是效率高
因为其使用包过滤和状态监测手段，一般只检验网络包外在（起始地址、状态）属性是否异常，若异常，则过滤掉，不与内网通信，因此对应用和用户是透明的
但是这样的问题是，如果遇到伪装的危险数据包就没办法过滤。
应用级防火墙
层次高，效率低
因为应用级防火墙会将网络包拆开，具体检查里面的数据是否有问题，会消耗大量时间，造成效率低下，但是安全强度高
包括双宿主主机、屏蔽主机网关、被屏蔽子网等方法
被屏蔽子网方法，是在内网和外网之间增加了一个屏蔽子网，相当于多了一层网络，称为DMZ(非军事区)，这样，内网和外网通信必须多经过一道防火墙，屏蔽子网中一般存放的是邮件服务器、WEB服务器这些内外网数据交互的服务器，可以屏蔽掉一些来自内部的攻击，但是完全来自系统内部服务器的攻击还是无法屏蔽掉
其他

安全防范体系
层次划分
物理环境的安全性
包括通信线路、物理设备和机房的安全等
主要体现
通信线路的可靠性（线路备份、网管软件和传输介质）
软硬件设备的安全性（替换设备、拆卸设备、增加设备)
设备的备份、防灾害能力、防干扰能力、设备的运行环境（温度、湿度、烟尘)和不间断电源保障等
操作系统的安全性
操作系统本身的缺陷带来的不安全因素
身份认证、访问控制和系统漏洞
对操作系统的安全配置问题
病毒对操作系统的威胁
网络的安全性
网络层的安全问题主要体现在计算机网络方面的安全性， 包括网络层身份认证、网络资源的访问控制、数据传输的保密与完整性、远程接入的安全、域名系统的安全、路由系统的安全、入侵检测的手段和网络设施防病毒等
应用的安全性
由提供服务所采用的应用软件和数据的安全性产生， 包括Wb服务、电子邮件系统和DNS等。此外，还包括病毒对系统的威胁。
管理的安全性
包括安全技术和设备的管理、安全管理制度、部门与人员的组织规则等。 管理的制度化极大程度地影响着整个计算机网络的安全， 严格的安全管理制度、明确的部门安全职责划分与合理的人员角色配置， 都可以在很大程度上降低其他层次的安全漏洞。
系统开发基础
软件工程概述
软件基本生存周期
问题定义
确定好要解决的问题是什么
可行性分析与项目开发计划
确定该问题是否存在一个可以解决的方案
需求分析
明确目标系统必须做什么，确定目标系统必须具备哪些功能。通常用数据流图、数据字典和简要的算法表示系统的逻辑模型。用《规格说明书》记录对目标系统的需求
概要设计
应该怎样实现目标系统，设计出实现目标系统的几种可能方案，设计程序的体系结构，也就是确定程序由哪些模块组成以及模块之间的关系
详细设计
实现系统的具体工作，编写详细规格说明，程序员可以根据它们写出实际的程序代码。详细设计也称模块设计，在这个阶段将详细的设计每个模块，确定实现模块功能所需的算法和数据结构
编码
测试
维护
软件过程
软件过程能力成熟度模型CMM
初始级
杂乱无章，甚至混乱，几乎没有明确定义的步骤， 项目的成功完全依赖个人的努力和英雄式核心人物的作用
可重复级
建立了基本的项目管理过程和实践来跟踪项目费用、进度和功能特性，有必要的过程准则来重复以前在同类项目中成功
已定义级
管理和工程两方面的软件过程已经文档化、标准化，并综合成整个软件开发组织的标准过程
已管理级
制定了软件过程和产品质量的详细度量标准
优化级
加强了定量分析，通过来自过程质量反馈和来自新观念、新技术的反馈使过程能不断持续地改进
软件过程能力成熟度模型CMMI
是若干过程模型的综合和改进
阶段式模型

初始的：过程不可预测且缺乏控制。
已管理的：过程为项目服务。
已定义的：过程为组织服务。
定量管理的：过程已度量和控制。
优化的：集中于过程改进。
连续式模型

CLO(未完成的)
未执行或未得到
CL1(已执行的)
可标识的输入工作产品转换成可标识的输出工作产品。
CL2(已管理的)
已管理的过程的制度化
CL3(已定义级的)
已定义的过程的制度化
CL4(定量管理的)
可定量管理的过程的制度化
CL5(优化的)
量化（统计学）手段改变和优化过程域
软件开发方法

结构化方法
以瀑布模型为代表，一旦开发完成，将难以修改不利于复用及后续版本的开发， 现在被面向对象法给代替了
特点
面对过程
用户至上
严格区分工作阶段，每阶段有任务和结果
强调系统开发过程的整体性和全局性
系统开发过程工程化，文档资料标准化
自顶向下，逐步分解（求精）
适用于需求明确的项目
原型方法
适合于需求不明确的开发，以原型模型为代表
面向对象方法
以构件组装模型为代表
更好的复用性
关键在于建立一个全面、合理、统一的模型
分析、设计、实现三个阶段，界限不明确
面向服务的方法
抽象级别：操作、服务、业务流程
Jackson方法
面向数据结构的开发方法，适合于小规模的项目
软件过程模型
定义
即软件开发模型，是软件开发全部过程、活动和任务的结构框架
瀑布模型(SDLC)

结构化方法中的模型，是结构化的开发， 开发流程如同瀑布一般，一步一步的走下去，直到最后完成项目开发， 只适用于需求明确或者二次开发（需求稳定）， 当需求不明确时，最终开发的项目会错误，有很大的缺陷
以文档作为驱动、适合于软件需求很明确的软件项目
V模型

瀑布模型的一个变体
特点是增加了很多轮测试，并且这些测试贯穿于软件开发的各个阶段， 不像其他模型都是软件开发完再测试，很大程度上保证了项目的准确性
演化模型

演化模型是迭代的过程模型，使得软件开发人员能够逐步开发出更完整的软件版本。 演化模型特别适用于对软件需求缺乏准确认识的情况
原型模型

原型方法比较适合于用户需求不清、需求经常变化的情况， 当系统规模不是很大也不太复杂时，采用该方法比较好
螺旋模型

针对需求不明确的项目，
瀑布模型和演化模型结合，加入了风险分析。
特别适用于庞大、复杂并且具有高风险的系统
四步：制定计划-风险分析-实施工程-用户评估
增量模型

首先开发核心模块功能，而后与用户确认，之后再开发次核心模块的功能， 即每次开发一部分功能，并与用户需求确认，最终完成项目开发， 优先级最高的服务最先交付。
特点：由于并不是从系统整体角度规划各个模块，因此不利于模块划分。 难点在于如何将客户需求划分为多个增量。 与原型不用的是增量模型的每一次增量版本都可作为独立可操作的作品， 而原型的构造一般是为了演示。
喷泉模型
是一种以用户需求为动力，以对象作为驱动的模型， 适合于面向对象的开发方法。使开发过程具有迭代性和无间隙性
统一过程模型UP
是一种开发过程
三大特点
用例和风险驱动
以架构为中心
迭代并且增量
四个阶段
起始
确定项目范围和边界
识别系统的关键用例
展示系统的侯选架构
估计项目费用和时间
评估项目风险
精化
分析系统问题领域
建立软件架构基础
淘汰最高风险元素
构建
开发剩余的构件
构件组装与测试
交付
进行β测试
制作发布版本
用户文档定稿
确认新系统
培训、调整产品
UP的每一次迭代都是一次完整的软件开发过程，包括整个软件开发生命周期， 有五个核心工作流（需求、分析、设计、实现、测试）
敏捷开发
基本原则
短平快的会议
小型版本发布
较少的文档
合作为重
客户直接参与
自动化测试
适应性计划调整
结对编程
测试驱动开发
持续集成
重构
总体目标
通过“尽可能早地、持续地对有价值的软件的交付”使客户满意
适用于：“小步快跑”的思想，适合小项目小团队。
敏捷方法

极限编程XP
4大价值观
沟通
简单
反馈
勇气
5个原则
快速反馈
简单性假设
逐步修改
提倡更改
优质工作
12个最佳实践
计划游戏：快速制定计划、随着细节的不断变化而完善
小型发布：系统的设计要能够尽可能早地交付
隐喻：找到合适的比喻传达信息
简单设计：只处理当前的需求，使设计保持简单
测试先行：先写测试代码，然后再编写程序
重构：重新审视需求和设计，重新明确地描述它们以符合新的和现有的需求
结对编程
集体代码所有制
持续集成：可以按日甚至按小时为客户提供可运行的版本
每周工作40小时
现场顾客：系统最终用户代表应该全程配合XP团队
编码标准
并列争球法SCRUM
是一种迭代的增量化过程，把每30天一次的迭代称为一个“冲刺”，并按需求的优先级来实现产品。多个自组织和自治的小组并行地递增实现产品。办调是通过简短的日常情况会议来进行，就像橄榄球中的“并列净球”
水晶方法
认为每一个不同的项目都需要一套不同的策略、约定和方法论，认为人对软件质量有重要的影响（以人为本），因此随着项目质量和开发人员素质的提高，项目和过程的质量也随之提高。通过更好地交流和经常性交付，软件生产力得到提高。
开放式源码
程序开发人员在地域上分布很广
功用驱动开发方法FDD
首席程序员和“类”程序员
自适应开发
核心是三个非线性的、重叠的开发阶段：猜测、合作与学习。 ASD有6个基本的原则： 有一个使命作为指导；，特征被视为客户价值的关键点； 过程中等待是很重要的，因此“重做”与“做”同样关键； 变化不被视为改正，而是被视为对软件开发实际情况的调整； 确定的交付时间迫使开发人员认真考虑每一个生产的版本的关键需求； 风险也包含其中
特性驱动开发
是一套针对中小型软件开发项目的开发模式。是一个模型驱动的快速迭代开发过程，它强调的是简化、实用、易于被开发团队接受，适用于需求经常变动的项目
需求分析
需求分析的概念
需求的任务
需求的过程
问题识别
分析与综合
编制需求分析文档
需求分析与评审
结构化分析的结果
一套分层的数据流图
一本数据词典
一组小说明(也称加工逻辑说明)
补充材料
需求的分类
按需求内容分类
业务需求（整体全局）
用户需求（用户视角）
系统需求（计算机化）
功能需求
非功能需求（性能需求）
响应，并发，存储容量，速度
设计约束
从客户角度分类
基本需求（明示，常规需求）
需求明确规定的功能
期望需求（隐含）
除了基本需求外，客户认为理所应当包含在内的其他功能
兴奋需求（多余）
客户未要求的其他功能需求，会浪费项目开发时间和成本
软件需求分类
功能需求
软件必须完成的基本动作
性能需求
说明软件或人与软件交互的静态或动态数值需求，如系统响应速度、处理速度等
设计约束
受其他标准硬件限制等方面的影响
属性
可用性、安全性、可维护性、可转移/转移性
外部接口需求
用户接口、硬件接口、软件接口、通信接口
需求分析的工具
数据流图(DFD)

基本概念
数据流
加工
数据存储(文件)
外部实体
人/物
外部系统
组织结构
描述数据在系统中如何被传送或变换， 以及如何对数据流进行变换的功能或子功能，用于对功能建模
数据流图是可以分层的，从顶层（即上下文无关数据流）到0层、1层等， 顶层数据流图只含有一个加工处理表示整个管理信息系统， 描述了系统的输入和输出，以及和外部实体的数据交互。数据流图示例如下

基本设计原则
数据守恒原则
对任何一个加工来说，其所有输出数据流中的数据必须能从该加工的输入数据流中直接获得，或者说是通过该加工能产生的数据
守恒加工原则
对同一个加工来说，输入与输出的名字必须不相同，即使它们的组成成分相同
对于每个加工，必须既有输入数据流，又有输出数据流
外部实体与外部实体之间不存在数据流
外部实体与数据存储之间不存在数据流
数据存储与数据存储之间不存在数据流
父图与子图的平衡原则
子图的输入输出数据流同父图相应加工的输入输出数据流必须一致， 此即父图与子图的平衡。父图与子图之间的平衡原则不存在于单张图
数据流与加工有关，且必须经过加工
数据字典(DD)

4类条目
数据流
数据项
数据存储
基本加工
（源点和终点不在系统之内，不在字典中说明）
结构化语言
结构化语言是一种介于自然语言和形式化语言之间的半形式化语言，是自然语言的一个受限子集
外层
用来描述控制结构，采用顺序、选择和重复3种基本结构
①顺序结构，一组祈使语句、选择语句、重复语句的顺序排列。
②选择结构，一般用IF-THEN-ELSE-ENDIF、CASE-OF-ENDCASE等关键词。
③垂复结构，一般用DO-WHILE-ENDDO、REPEAT-UNTIL等关键词。
内层
一般采用祈使语句的自然语言短语，使用数据字典中的名词和游戏的自定义词， 其动词含义要具体，尽量不用形容词和副词来修饰， 还可使用些简单的算法运算和逻辑运算符号
判定表
某些情况下，数据流图中某个加工的一组动作依赖于多个逻辑条件的取值，此时用判定表能够清楚地表示复杂的条件组合与应做的动作之间的关系。
判定表由4个部分组成，用双线分割成如下的4个区域

判定树
判定树是判定表的变形，一般情况下比判定表更直观，且易于理解和使用
系统设计
系统设计
系统设计基本原理
抽象（重点说明本质方面，忽略非本质方面）
模块化（可组合、分解和更换的单元）
自顶而下、逐步求精
信息隐蔽（将每个程序的成分隐蔽或封装在一个单一的设计模块中）
模块独立
每个模块完成一个相对独立的特定子功能，且与其他模块之间的联系简单
模块的设计要求独立性高， 就必须高内聚，低耦合
内聚是指一个模块内部功能之间的相关性

耦合是指多个模块之间的联系

系统设计的主要目的
是为系统制定蓝图，在各种技术和实施方法中权衡利弊， 精心设计，合理地使用各种资源，得出新系统的详细设计方案
划分
概要设计
划分子系统，分配任务
基本任务
设计软件系统总体结构
数据结构及数据库设计
编写概要设计文档
评审
详细设计
模块内部的设计
基本任务
模块内详细算法设计
模块内数据结构设计
数据库的物理设计
其他设计（代码、输入/输出格式、用户界面）
编写详细设计说明书
评审
其他
体系结构设计
定义软件系统各主要部件之间的关系
数据设计
基于E-R图确定软件涉及的文件系统的结构及数据库的表结构
接口设计（人机界面设计）
软件内部，软件和操作系统间以及软件和人之间如何通信
过程设计
系统结构部件转换成软件的过程描述。 确定软件各个组成部分内的算法及内部数据结构， 并选定某种过程的表达形式来描述各种算法
应用的工具
IPO图
PDL
PAD
程序流程图
N/S盒图
模块设计
基本原则
保持模块的大小适中
尽可能减少调用的深度
多扇入，少扇出，数量适中
单入口，单出口
模块的作用域应该在模块控制域之内
功能应该是可预测的
原则
高内聚，低耦合
内聚性

功能内聚
完成一个单一功能，各个部分协同工作，缺一不可
顺序内聚
处理元素相关，而且必须顺序执行
通信内聚
所有处理元素集中在一个数据结构的区域上
过程内聚
处理元素相关，而且必须按特定的次序执行
瞬时内聚（时间内聚）
所包含的任务必须在同一时间间隔内执行
逻辑内聚
完成逻辑上相关的一组任务
偶然内聚（巧合内聚）
完成一组没有关系或松散关系的任务
耦合性

非直接耦合
两个模块之间没有直接关系，它们之间的联系完全是通过主模块的控制和调用来实现的
数据耦合
组模块借助参数表传递简单数据
标记耦合
一组模块通过参数表传递记录信息（数据结构）
控制耦合
模块之间传逆的信息中包含用于控制模块内部逻粗的信息
外部耦合
一组模块都访问同一全局简单变量，而且不是通过参数表传递该全局变量的信息
公共耦合
多个摸块都访问同一个公共数据环境
人机界面设计

置于用户控制之下
减少用户的记忆负担
保持界面的一致性
架构设计
软件架构风格
架构设计的一个核心问题是能否达到架构级的软件复用
架构风格反映了领域中众多系统所共有的结构和语义特性，并指导如何将各个构件有效地组织成一个完整的系统
架构风格定义了用于描述系统的术语表和一组指导构建系统的规则
分类
数据流风格
早期编译器就是采用的这种架构。要一步一步处理的，均可考虑采用此架构风格
分类
批处理序列
构件为一系列固定顺序的计算单元，构件之间只通过数据传递交互。 每个处理步骤是一个独立的程序，每一步必须在其前一步结束后才能开始， 数据必须是完整的，以整体的方式传递
管道过滤器
每个构件都有一组输入和输出，构件读输入的数据流，经过内部处理，然后产生输出数据流。 这个过程通常是通过对输入数据流的变换或计算来完成的，包括通过计算和增加信息以丰富数据、通过浓缩和删除以精简数据、通过改变记录方式以转化数据和递增地转化数据等。 这里的构件称为过滤器，连接件就是数据流传输的管道，将一个过滤器的输出传到另一个过滤器的输入
可以并行
调用返回风格
分类
主程序/子程序
单线程控制，把问题划分为若干个处理步骤，构件即为主程序和子程序，子程序通常可合成为模块。过程调用作为交互机制，即充当连接件的角色。调用关系具有层次性，其语义逻辑表现为主程序的正确性取决于它调用的子程序的正确性
面向对象
构件是对象，对象是抽象数据类型的实例。在抽象数据类型中，数据的表示和它们的相应操作被封装起来，对象的行为体现在其接受和请求的动作。连接件即是对象间交互的方式，对象是通过函数和过程的调用来交互的
层次结构(MVC、C/S、B/S)
构件组织成一个层次结构，连接件通过决定层间如何交互的协议来定义。每层为上一层提供服务，使用下一层的服务，只能见到与自己邻接的层。通过层次结构，可以将大的问题分解为若干个渐进的小问题逐步解决，可以隐藏问题的复杂度。修改某一层，最多影响其相邻的两层（通常只能影响上层）
MVC架构风格

C/S

优点
1、这种风格支持基于可增加抽象层的设计，允许将一个复杂问题分解成一个增量步骤序列的实现。
2、不同的层次处于不同的抽象级别：
越靠近底层，抽象级别越高；
越靠近顶层，抽象级别越低。
3、由于每一层最多只影响两层，同时只要给相邻层提供相同的接口，允许每层用不同的方法实现，同样为软件复用提供了强大的支持
缺点
1、并不是每个系统都可以很容易地划分为分层的模式。
2、很难找到一个合适的、正确的层次抽象方法。
独立构件风格
进程通信
构件是独立的过程，连接件是消息传递。构件通常是命名过程，消息传递的方式可以是点对点、异步或同步方式，以及远程过程（方法）调用等
事件驱动系统（隐式调用）
构件不直接调用一个过程，而是触发或广播一个或多个事件。主要优点是为软件复用提供了强大的支持，为构件的维护和演化带来了方便；其缺点是构件放弃了对系统计算的控制
虚拟机风格
解释器
解释器通常包括一个完成解释工作的解释引擎、一个包含将被解释的代码的存储区、一个记录解释引擎当前工作状态的数据结构，以及一个记录源代码被解释执行的进度的数据结构。具有解释器风格的软件中含有一个虚拟机，可以仿真硬件的执行过程和一些关键应用，其缺点是执行效率比较低
基于规则的系统
基于规则的系统包括规则集、规则解释器、规则/数据选择器和工作内存，一般用在人工智能领域和DSS中
仓库风格
现代集成编译环境一般采用这种架构风格
分类
数据库系统
构件主要有两大类，一类是中央共享数据源，保存当前系统的数据状态； 另一类是多个独立处理单元，处理单元对数据元素进行操作
黑板系统
包括知识源、黑板和控制三部分。知识源包括若干独立计算的不同单元，提供解决问题的知识。知识源响应黑板的变化，也只修改黑板；黑板是一个全局数据库，包含问题域解空间的全部状态，是知识源相互作用的唯一媒介；知识源响应是通过黑板状态的变化来控制的。黑板系统通常应用在对于解决问题没有确定性算法的软件中（信号处理、问题规划和编译器优化等）
超文本系统
测试基础知识
系统测试是为了发现错误而执行程序的过程， 成功的测试是发现了至今尚未发现的错误的测试
测试的基本概念及分类
测试原则
应尽早并不断的进行测试
程序员避免测试自己设计的程序
既要选择有效、合理的数据，也要选择无效、不合理的数据
修改后应进行回归测试
尚未发现的错误数量与该程序已发现错误数成正比
在设计测试方案时，不仅要确定输入数据，而且要根据系统功能确定预期的输出结果
检验程序是否做了该做的事，且是否做了不该做的事
严格按照测试计划进行
妥善保存测试计划和测试用例
测试用例可以重复使用或追加测试
分类
动态测试（机器运行）
黑盒测试法
等价类划分
确定无效与有效等价类
设计用例尽可能多的覆盖有效类
设计用例只覆盖一个无效类
边界值分析
处理边界情况时最容易出错
选取的测试数据应该恰好等于、稍小于或稍大于边界值
错误推测
因果图
白盒测试法
基本路径测试
循环覆盖测试
语句覆盖
被测试程序中的每条语句至少执行一次。
对执行逻辑覆盖很低，一般认为是很弱的逻辑覆盖
判定覆盖（分支覆盖）
被测程序每个判定表达式至少获得一次“真”值和“假”值 （或者程序中每一个判定取“真”分支和取“假”分支至少通过一次。)
判定覆盖比语句覆盖更强一些。判定可以是1个条件，也可以是多个条件的组合
条件覆盖
每一个判定语句中每个逻辑条件的各种可能的值至少满足一次
条件覆盖和判断覆盖没有包含关系
判断/条件覆盖
判定中每个条件的所有可能取值（真/假）至少出现一次， 并使每个判定本身的判定结果（真/假）也至少出现一次
同时满足判定覆盖和条件覆盖
路径覆盖
覆盖被测试程序中所有可能的路径
条件组合覆盖
每个判定中的各种可能值的组合都至少出现一次
同时满足判定覆盖、条件覆盖、判定/条件覆盖
基本路径测试
每一条独立路径都执行过（即程序中可执行语句至少执行一次)
测试用例个数与环路复杂度一致。判定为关键控制结点，必须出现在基本路径中
循环覆盖
循环中每个条件都得到验证
注意数组参数可循环验证
逻辑覆盖测试
灰盒测试法
静态测试（纯人工）
桌前检查
代码审查
代码走查
测试阶段
单元测试
测试依据是软件详细说明书。 在单元测试中，驱动模块（上层）用来调用被测模块， 自顶向下的单元测试中不需要另外编写驱动模块。 桩模块（底层）用来模拟被测模块所调用的子模块
集成测试
将模块组合起来进行测试， 分为一次性组装（简单，节约时间，发现错误少，只适合于小项目) 和增量式组装（能够发现更多错误，耗时长， 又可分为：自顶向下、自底向上、混合式)
系统测试
对软件进行性能测试，主要测试三个方面， 即负载测试（在极限情况下，系统各项性能指标)、 强度测试（系统资源特别低的情况下）、 容量测试（并发测试，系统可以处理的同时在线的最大用户数量)。 其他还有可靠性等性能测试，系统测试采用的是黑盒测试方法
确认测试
对已完成的软件进行功能上的测试， 分为内部确认测试（无用户情况）、 Alpha测试（用户在开发环境下进行测试）、 Beta测试（用户在实际使用时进行的测试)、 验收测试（用户根据SS对项目进行验收）
回归测试
软件修改错误或变更后，进行回归测试以验证之前正确的代码是否引入了错误
测试策略
自底向上
从最底层模块开始测试，需要编写驱动程序， 而后开始逐一合并模块，最终完成整个系统的测试。 优点是较早的验证了底层模块
自顶向下
先测试整个系统，需要编写桩程序，而后逐步向下直至最后测试最底层模块。 优点是较早的验证了系统的主要控制和判断点
三明治
既有自底向上也有自顶向下的测试方法，二者都包括。 兼有二者的优点，缺点是测试工作量大
McCabe复杂度计算

计算有向图G的环路复杂度公式为：V(G)=m-n+2。
说明：其中V(G)是有向图G中的环路个数，是G中的有向弧数，n是G中的节点数
软件维护
可维护性因素决定
可理解性
可测试性
可修改性
类型
改正性维护
发现了bug而进行的修改
预防性维护
对未来可能发生的bug进行预防性的修改
适应性维护
由于外部环境发生了改变，被动进行的对软件的修改和升级
完善性维护
基于用户主动对软件提出更多的需求，修改软件，增加更多的功能， 使其比之前的软件功能、性能更高，更加完善
软件工具与软件开发环境
软件工具
软件开发工具
对应于软件开发过程的各种活动
包括 需求分析工具、设计工具、编码与排错工具、测试工具
软件维护工具
辅助软件维护过程中活动的软件，辅助维护人员对软件代码及其文档进行各种维护活动
包括 版本控制工具、文档分析工具、开发信息库工具、逆向工程工具、再工程工具
软件管理和软件支持工具
辅助管理人员和软件支持人员的管理活动和支持活动，以确保软件高质量的完成
包括 项目管理工具、配置管理工具、软件评价工具
软件开发环境

指支持软件产品开发的软件系统
构成
工具集
用于支持软件开发的相关过程、活动和任务
环境集成机制
为工具集成和软件开发、维护和管理提供统一的支持
开发支持环境
环境信息库
过程控制和消息服务
用户界面规范
软件文档
按阅读对象划分
用户
开发过程的每个阶段的进度和进度变更的记录
软件变更情况的记录
相对于开发的判定记录
职责定义
管理员
培训手册
参考手册和用户指南
软件支持手册
产品手册和信息广告
开发人员
开发文档
可行性研究和项目任务书
需求规格说明
功能规格说明
设计规格说明（包括程序和数据规格说明
开发计划
软件集成和测试计划
质量保证计划、标准、进度
安全和测试信息
软件质量保证
ISO/IEC9126软件质量模型
质量特性和子特性

功能性

适合性
准确性
互用性
依从性
安全性
易使用性

易理解性
易学性
易操作性
可靠性

成熟性
容错性
易恢复性
效率

时间特性
资源特性
可维护性

易分析性
易改变性
稳定性
易测试性
可移植性

适应性
易安装性
一致性
易替换性
软件容错技术
容错就是软件遇到错误的处理能力
实现容错的手段主要是冗余
结构冗余
分为静态（通过表决和比较，少数服从多数）
动态（多重模块待机备份故障时切换备份机）
混合冗余（二者综合）
信息冗余
为检错和纠错在数据中加上一段额外的信息，例如校验码原理
时间冗余
遇到错误时重复执行，例如回滚，重复执行还有错，则转入错误处理逻辑
冗余附加技术
冗余附加技术是指为实现结构、信息和时间冗余技术所需的资源和技术， 包括程序、指令、数据、存放和调动它们的空间和通道等
在屏蔽硬件错误的容错技术中， 冗余附加技术包括
关键程序和数据的冗余及调用
检测、表决、切换、重构和复算的实现
在屏蔽软件错误的容错技术中， 冗余附加技术包括
冗余备份程序的存储及调用
实现错误检测和错误恢复的程序
项目管理
软件项目管理
进度管理
Gatt图

又称为横道图，横轴表示时间，纵轴表示活动，以时间顺序表示活动，能反应活动间的并行关系
无法反应活动之间的依赖关系，因此也难以清晰的确定关键任务和关键路径
PERT图

类似于前趋图，是有向图，反应活动之间的依赖关系，有向边上标注活动运行的时间
无法反应活动之间的并行关系
图中箭头表示任务，它可以标上完成该任务的时间，图中的节点表示流入节点的任务的结束，并开始流出结点任务，这里把结点称为事件。只有当流入该结点的所有任务都结束时，结点所表示的事件才出现
特点：不仅给出了每个任务的开始时间、结束时间、完成该任务所需的时间， 还给出了任务之间的关系
图的关键路径
关键路径重要概念
关键路径（项目总工期）
项目中耗时最长的一条线路
最早开始时间ES
取所有前驱活动最早完成时间EF的最大值
最早完成时间EF
最早开始时间ES+活动本身时间DU
最晚完成LF
取后续活动最晚开始时间的最小值
最晚开始时间LS
最晚完成LF-活动本身时间DU
松弛时间
某活动的最晚开始时间-最早开始时间 （或最晚完成时间-最早完成时间)，也即该活动最多可以晚开始多少天
例题
 
箭线图（双代号网络图，ADM）

前导图法（但代号网络图，PDM）

总时差为0的是关键活动
软件配置管理
基线
软件开发过程中特定的点，是项目生存期各开发阶段末尾的特定点， 又称为里程碑，反应阶段性成果
软件配置项
环境类（系统开发环境）
定义类（需求分析与系统定义阶段）
设计类（设计阶段)
编码类（编码及单元测试阶段）
测试类（系统测试完成后的工作）
维护类（维护阶段）
产品组成部分的工作成果+项目管理和机构支撑过程域产生的文档
主要内容
版本管理
版本控制

即软件配置项的版本控制
三个状态
草稿
正式
修改
版本命名规则

配置支持
变更支持
变更控制

过程支持
团队支持
变化报告
审计支持
软件风险管理
软件风险两个特性
不确定性（可能发生也可能不发生）
损失（发生会产生恶性后果)
风险曝光度(Risk Exposure)
计算方法是风险出现的概率乘以风险可能造成的损失
分类
项目风险
威胁到项目计划， 如果项目风险发生，有可能拖延项目的进度和增加项目的成本。 指预算、进度、人员、资源、利益相关者、需求等方面的潜在问题以及它们对软件项目的影响。项目复杂度、规模及结构不确定性也属于项目风险因素
技术风险
威胁到要开发软件的质量和交付时间， 如果技术风险发生，开发工作就变得很困难或者不可能， 指设计、实现、接口、验证和维护等方面的潜在问题。此外，规格说明的歧义性、技术的不确定性、技术陈旧以及“前沿”技术也是技术风险因素
商业风险
威胁到要开发软件的生存能力
包括
市场风险。开发了一个没有人真正需要的优良产品或系统。
策略风险。开发的产品不再符合公司的整体商业策略。
销售风险。开发了一个销售部门不知道如何去销售的产品。
管理风险。由于重点的转移或人员的变动而失去了高级管理层的支持。
预算风险。没有得到预算或人员的保证。
风险管理过程
风险识别
识别出项目中已知和可预测的风险， 确定风险的来源、产生的条件、描述风险的特征以及哪些项目可以产生风险， 形成一个风险列表
风险预测
又称为风险估计， 从两个方面预测风险，即风险可能发生的概率和风险发生产生的后果， 因此有风险曝光度=风险发生的可能性*风险发生会带来的损失
风险评估
定义风险参照水准，将识别出来的风险评估分类
风险控制
辅助项目组建立处理风险的策略
风险避免
风险监控
RMMM计划（风险缓解、监控和管理计划）
沟通管理
沟通路径
无主程序员

n*（n-）/2
有主程序员

n-1
成本管理
软件规模估算方法
COCOMO模型
常用的代码行分析方法作为其中一种度量估计单位， 以代码行数估算出每个程序员工作量，累加得软件成本
分为三级
基本COCOMO模型
基本COCOMO模型是是一个静态单变量模型， 它用一个以已估算出来的原代码行数(LOC)为自变量的经验函数计算软件开发工作量
中间COCOMO模型
在基本COCOMO模型的基础上， 再用涉及产品、硬件、人员、项目等方面的影响因素调整工作量的估算
详细COCOMO模型
包括中间COCOMO模型的所有特性， 但更进一步考虑了软件工程中每一步骤（如分析、设计)的影响
COCOMOⅡ模型

COCOMO的升级，也是以软件规模作为成本的主要因素，考虑多个成本驱动因子
三个阶段性模型
应用组装模型
软件工程前期阶段使用
对象点
早期设计阶段模型
需求已经稳定并且基本的软件体系结构已经建立时使用
功能点、代码行
体系结构阶段模型
软件的构造过程中使用
代码行
Putnam估算模型
一种动态多变量模型，假设在软件开发的整个生存周期中工作量有特定的分布
面向对象技术
面向对象基础
面向对象基本概念
对象与类相关概念
对象
基本的运行实体，为类的实例，封装了数据和行为的整体
对象具有清晰的边界、良好定义的行为和可扩展性
消息
对象之间进行通信的一种构造称为消息
包括
ID
唯一
属性
行为
类
是对象的抽象，定义了一组大体相似的对象结构，定义了数据和行为
类型
实体类
用于对必须存储的信息和相关行为建模的类，是需要长久保存且一直存在的类
边界类
系统内部与系统外部的业务主角之间进行交互建模的类
控制类
用于对一个或几个用例所特有的控制行为进行建模， 在用例执行过程中被动出现的特定行为的类
包括
类名
数据成员
成员函数
函数重载
与覆盖要区分开，函数重载与子类父类无关，且函数是同名不同参数
封装
一种信息隐蔽技术，其目的是使对象的使用者和生产者分离，也就是使其他开发人员无需了解所要使用的软件组件内部的工作机制，只需知道如何使用组件
继承与泛化相关概念
继承
父类和子类之间共享数据和方法的机制。是类之间的一种关系
覆盖/覆盖
子类在原有父类接口的基础上，用适合于自己要求的实现去置换父类中的相应实现。 即在子类中重定义一个与父类同名同参的方法
多态与动态绑定相关概念
多态
不同的对象收到同一个消息时产生完全不同的反应
类型
参数多态
不同类型参数多种结构类型
包含多态
父子类型关系
过载多态
同一个名字在不同的上下文产生不同含义
强制多态
强制类型转换
多态由继承机制支持
动态绑定
静态类型是指一个对象的类型在编译时就确定
静态绑定（静态分配）是基于静态类型的，在程序执行前（编译）方法已经被绑定
动态类型指对象类型在运行时才能确定
动态绑定是基于动态类型的，运行时根据变量实际引用的对象类型决定调用哪个方法，动态绑定支持多态
面向对象分析
为了确定问题域，理解问题
五个活动
认定对象
按自然存在的实体确定对象
组织对象
分析对象关系，抽象成类
对象间的相互作用
描述各对象在应用系统中的关系
确定对象的操作
操作，如创建增加删除等
定义对象的内部信息
面向对象设计
是设计分析模型和实现相应源代码，在目标代码环境中这种源代码可被执行。 设计问题域的解决方案
包括
识别类及对象
定义属性
定义服务
识别关系
识别包
7大原则
单一职责原则
设计目的单一的类
开放-封闭原则
对扩展开放，对修改封闭
李氏(Lisko)替换原则
子类可以替换父类
依赖倒置原则
要依赖于抽象，而不是具体实现；针对接口编程，不要针对实现编程
接口隔离原则
使用多个专门的接口比使用单一的总接口要好
组合重用原则
要尽量使用组合，而不是继承关系达到重用目的
迪米特(Demeter)原则（最少知识法则）
一个对象应当对其他对象有尽可能少的了解
其他原则
重用发布等价原则：重用的粒度就是发布的粒度
共同封闭原则：包中的所有类对于同一性质的变化应该是共同封闭的。一个变化若对一个包产生影响，则将对该包里的所有类产生影响，而对于其他的包不造成任何影响
共同重用原则：一个包里的所有类应该是共同重用的。如果重用了包里的一个类，那么就要重用包中的所有类
无环依赖原则：在包的依赖关系图中不允许存在环，即包之间的结构必须是一个直接的无环图形
稳定依赖原则：朝着稳定的方向进行依赖
稳定抽象原则：包的抽象程度应该和其稳定程度一致
方法
Booch
OOSE
OMT
面向对象程序设计
用面向对象程序设计语言实现设计方案
包括
程序设计范型
选择一种OOPL
面向对象测试
与普通测试步骤并无不同
四个层次
算法层
测试类中定义的每个方法，类似单元测试
类层
测试同一个类中所有方法与属性的相互作用，特有的模块测试
模板层
测试一组协同工作的类之间的相互作用，类似集成测试
系统层
类似系统测试
UML
UML是统一建模语言，和程序设计语言并无关系
三个要素
UML的基本构造块
事物
对模型中最具有代表性的成分的抽象
四种事物
结构事物
模型的静态部分 如类、接口、用例、构件等

行为事物
模型的动态部分 如交互、活动、状态机

分组事物
模型的组织部分 如包

注释事物
模型的解释部分 依附于一个元素或一组元素之上对其进行约束或解释的简单符号

关系

把事务结合在一起
依赖

一个事物的语义依赖于另一个事物的语义的变化而变化
泛化

一般/特殊的关系，子类和父类之间的关系
关联

是一种结构关系，描述了一组链，链是对象之间的连接
部分和整体的关系
聚合
整体与部分生命周期不同
组合
整体与部分生命周期相同
关系更强
实现

一个类元指定了另一个类元保证执行的契约
图
聚集了相关的事物
支配这些构造块如何放置在一起的规则
运用与整个语言的一些公共机制
UML中的图
结构图（静态）
类图

一组对象、接口、协作和它们之间的关系
对象图

展现某一时刻一组对象以及它们之间的关系，为类图的某一快照。
在没有类图的前提下，对象图就是静态设计视图
构件图（组件图）

一组构件之间的组织和依赖，专注于系统的静态实现视图
部署图

运行处理结点以及构件的配置，给出体系结构的静态实施视图，软硬件之间映射
它与构件图相关，通常一个结点包含一个或多个构件
其依赖关系类似于包依赖，因此部署组件之间的依赖是单向的类似于包含关系
包图
描述类或其他UML如何组织成包，以及包之间的依赖关系
对象图（动态）
用例图

系统与外部参与者的交互，展现了一组用例、参与者以及它们之间的关系。
用例是参与者完成的一系列操作
用例之间的关系

包含关系
其中这个提取出来的公共用例称为抽象用例，而把原始用例称为基本用例或基础用例系：当可以从两个或两个以上的用例中提取公共行为时，应该使用包含关系来表示它们
include
必选
扩展关系
如果一个用例明显地混合了两种或两种以上的不同场景，即根据情况可能发生多种分支，则可以将这个用例分为一个基本用例和一个或多个扩展用例，这样使描述可能更加清晰
extend
可选
泛化关系
当多个用例共同拥有一种类似的结构和行为的时候，可以将它们的共性抽象成为父用例，其他的用例作为泛化关系中的子用例。在用例的泛化关系中，子用例是父用例的一种特殊形式，子用例继承了父用例所有的结构、行为和关系
必选
交互图
顺序图（序列图）

是场景的图形化表示，描述了以时间顺序组织的对象之间的交互活动
类型
同步消息
进行阻塞调用，调用者中止执行，等待控制权返回需要等待返回消息 用实心三角箭头表示
异步消息
发出消息后继续执行，不引起调用者阻塞，也不等待返回消息 由空心箭头表示
返回消息
由从右到左的虚线箭头表示
通信图

即协作图，强调收发消息的对象之间的组织结构
状态图

展现了一个状态机，由状态、转换、事件和活动组成
动态图，展现了一个状态机，描述单个对象在多个用例中的行为， 包括简单状态和组合状态
转换可以通过事件触发器触发，事件触发后相应的监护条件会进行检查
转换和状态是两个独立的概念
图中方框代表状态，箭头上的代表触发事件，实心圆点为起点和终点
活动图

动态图，是一种特殊的状态图
专注于系统的动态视图，一个活动到另一个活动的流程，类似程序流程图，并行行为
活动的分岔和汇合线是一条水平粗线
并发分岔、并发汇合、监护表达式、分支、流等名词及含义。
每个分岔的分支数代表了可同时运行的线程数
活动图中能够并行执行的是在一个分岔粗线下的分支上的活动
设计模式
每一个设计模式描述了一个在我们周围不断重复发生的问题，以及该问题的解决方案的核心
设计模式的核心在于提供了相关问题的解决方案，使得人们可以更加简单方便的复用成功的设计和体系结构
四个基本要素
模式名称
问题
应该在何时使用模式
解决方案
设计的内容
效果
模式应用的效果
分类
创建型模式 主要是处理创建对象

Abstract Factory 抽象工厂模式

生产成系列相关或相互依赖的对象
抽象接口
Builder 构建器模式

复杂对象构造
类和构造分离
Factory Method 工厂方法模式

动态生产对象
子类决定实例化
Prototype 原型模式

克隆对象
原型实例，拷贝
Singleton 单例模式

唯一实例
结构型模式 主要是处理类和对象的组合

Adapter 适配器模式

转换，兼容接口
Bridge 桥接模式

抽象和实现分离，独立变化
继承树拆分
Composite 组合模式

整体部分，树形结构
Decorator 装饰模式

添加额外的职责
Facade 外观模式

对外统一接口
Flyweight 享元模式

细粒度，共享
文章共享文字对象
Proxy 代理模式

代理控制
快捷方式
行为型模式 主要是描述类或者对象的交互行为

Observer 观察者模式

一对多的联动
通知、自动更新·
Visitor 访问者模式

数据与操作分离
新操作
Chain of Responsibility 职责链模式

传递请求、职责、链接
State 状态模式

状态变成类
状态改变时改变行为
Command 命令模式

参数化
日志记录，可撤销
Interpreter 解释器模式

文法、解释
虚拟机的机制
Iterator 迭代器模式

顺序访问
数据库数据集
Mediator 中介者模式

不直接引用
一个中介对象封装一系列对象的交互
Memento 备忘录模式

可恢复
Strategy 策略模式

多方案切换
算法封装，相互替换，独立变化
Template Method 模板方法模式

文档模板填空
数据结构与算法基础
数据结构
线性结构
线性表
结构特点

存储结构
顺序存储结构

链式存储结构

基本操作

对比
 
队列和栈
队列
先进先出
循环队列

栈
先进后出
串
概念
字符串是一种特殊的线性表，其数据元素都为字符
空串
长度为0的字符串，没有任何字符
空格串
由一个或多个空格组成的串，空格是空白字符，占一个字符长度
子串
串中任意长度的连续字符构成的序列称为子串。 含有子串的串称为主串，空串是任意串的子串
子序列
是将这个串中的一些字符提取出来得到一个新串，并且不改变它们的相对位置关系
串比较
两个串比较大小时以字符的ASC川码值（或其他字符编码集合）作为依据。实质上，比较操作从两个的第一个字符开始进行，字符的码值大者所在的串为大；若其中一个串先结束，则以串长较大者为大
串相等
指两个串长度相等且对应序号的字符也相同
串的基本操作
(I)赋值操作StrAssign(s,t):将串s的值赋给串t。
(2)连接操作Concat(s,t):将串t接续在串s的尾部，形成一个新的串。
(3)求串长StrLength(s):返回串s的长度。
(4)串比较StrCompare(s,t):比较两个串的大小。返回值-l、0和1分别表示s<t、S=t和s>t三种情况。
(5)求子串SubString(s,start,len):返回串S中从start开始的、长度为len的字符序列
串的存储
(1)顺序存储
(2)链式存储
串的模式匹配算法
基本的模式匹配算法 （布鲁特一福斯算法）
其基本思想是从主串的第1个字符起与模式串的第1个字符比较，若相等，则继续逐个字符进行后续的比较；否则从主串中的第2个字符起与模式串的第1个字符重新比较，直至模式串中每个字符依次和主串中的一个连续的字符序列相等时为止，此时称为匹配成功，否则称为匹配失败
KMP算法
对基本模式匹配算法的改进，其改进之处在于：每当匹配过程中出现相比较的字符不相等时，不需要回溯主串的字符位置指针，而是利用已经得到的部分匹配”结果将模式串向右“滑动”尽可能远的距离，再继续进行比较
在KMP算法中，依据模式串的next函数值实现子串的滑动。若令next[]=k,则next[j]表示当模式串中的p与主串中相应字符不相等时，令模式串的PnextI与主串的相应字符进行比较。(j=next[j])

数组与矩阵
数组
存储地址计算

计算

矩阵
特殊矩阵

稀疏矩阵
存储位置计算

代入法
在一个矩阵中，若非零元素的个数远远少于零元素个数，且非零元素的分布没有规律。
存储方式
三元组结构，即存储每个非零元素的（行，列，值)
广义表

树与二叉树
树
树的结构

树结构是一种非线性结构，树中的每一个数据元素可以有两个或两个以上的直接后继元素，用来描述层次结构关系 树是n个结点的有限集合（n>=0),当n=0时称为空树， 在任一颗非空树中，有且仅有一个根节点； 其余结点可分为m(m>=0)个互不相交的有限子集T1,T2,Tm,其中每个Ti又都是一棵树，并且成为根结点的子树
基本概念
双亲、孩子和兄弟
结点的子树的根称为该结点的孩子： 相应地，该结点称为其子结点的双亲。 具有相同双亲的结点互为兄弟
结点的度
一个结点的子树的个数记为该结点的度
叶子结点
叶子结点也称为终端结点，指度为0的结点
内部结点
度不为0的结点，也称为分支结点或非终端结点。 除根结点以外，分支结点也称为内部结点
结点的层次
根为第一层，根的孩子为第二层，依此类推， 若某结点在第层，则其孩子结点在第+1层
树的高度
一棵树的最大层数记为树的高度（或深度）
有序（无序）树
若将树中结点的各子树看成是从左到右具有次序的， 即不能交换，则称该树为有序树，否则称为无序树
二叉树
是n个节点的有限集合，它或者是空树，或者是由一个根节点及两颗互不相交且分别称为左、右子树的二叉树所组成；与树的区别在于每个根节点最多只有两个孩子结点
特性
二叉树第i层(i>1)上最多有2^(i-1)个结点
高度为k的二叉树最多有2^k-1个结点(k≥1)
对于任何一棵二叉树，若其终端结点数为n0,度为2的结点数为n2，则n0=n2+1
具有n个结点的完全二叉树的深度为[log₂n]+1向下取整
对一棵有个结点的完全二叉树的所有结点 按层次自上而下、自左至右进行编号， 则对于任一结点 i (1≤i≤n)有
若i=1，则结点i是二叉树的根，无双亲：若i>1，则其双亲为[i/2]向下取整
若2i>n，则结点i没有左孩子，否则其左孩子为2i
若2i+1>n，则结点没有右孩子，否则其右孩子为2i+1
满二叉树

每层都是满结点的
完全二叉树
第k-1层是满结点的，第k层结点从左到右是满的
存储结构
顺序存储结构
用一组连续的存储单元存储二叉树中的节点， 按照从上到下，从左到右的顺序依次存储每个节点
对于深度为k的完全二叉树，除第k层外，其余每层中节点数都是上一层的两倍，由此，从一个节点的编号可推知其双亲、左孩子、右孩子结点的编号。假设有编号为的节点，则有
(1)若i=1，该结点为根结点，无双亲。
(2)若i>1，该结点的双亲为(i+1)/2（取整数）。
(3)若2i≤n,则该结点的左孩子编号为2i,否则无左孩子。
(4)若2i+1≤n,则该结点的右孩子编号为2i+1，否则无右孩子
(5)若i为奇数且不为1，则该结点左兄弟的编号为i-1，否则无左兄弟。
(6)若i为偶数且小于n,则该结点右兄弟的编号为计i+1，否则无右兄弟。
链式存储结构
一般用二叉链表来存储二叉树节点，二叉链表中除了该节点本身的数据外，还存储有左孩子结点的指针、右孩子结点的指针，即一个数据+两个指针
每个二叉链表节点存储一个二叉树节点，头指针则指向根节点
形态

遍历
一颗非空的二叉树由根节点、左子树、右子树三部分组成，遍历这三部分，也就遍历了整颗二叉树。这三部分遍历的基本顺序是先左子树后右子树，但根节点顺序可变，以根节点访问的顺序为准有下列三种遍历方式
先序（前序）遍历：根左右。
中序遍历：左根右。
后序遍历：左右根
层次遍历方法
层次遍历：按层次，从上到下，从左到右
示例

前序：12457836 中序：42785136 后序：48752631
查找二叉树

每个节点都存储一个值
每个节点的所有左孩子结点值都小于父节点值
所有右孩子结点值都大于父节点值
一个有规律排列的二叉树，这种数据结构可以方便查找、插入等数据操作
平衡二叉树
在查找二叉树特点的基础上，要求每个节点的平衡度只能为0或1或-1
节点的左右子树深度就是其左右子树各自的层数， 将左子树深度减去右子树深度，就得到该节点的平衡度。 因此，平衡二叉树就是任意左右子树层次相差不超过1
二叉排序树的查找效率取决于二叉排序树的深度，对于结点个数相同的二叉排序树，平衡二叉树的深度最小，而单枝树的深度是最大的，故效率最差
最优二叉树
最优二叉树又称为哈夫曼树，是一类带权路径长度最短的树
概念
路径
树中一个结点到另一个结点之间的通路
结点的路径长度
路径上的分支数目
树的路径长度
根节点到达每一个叶子节点之间的路径长度之和
权
节点代表的值
结点的带权路径长度
该结点到根结点之间的路径长度乘以该节点的权值
树的带权路径长度（树的代价）
树的所有叶子节点的带权路径长度之和
求法
哈夫曼树的求法：给出一组权值，将其中两个最小的权值作为叶子节点，其和作为父节点，组成二叉树，而后删除这两个叶子节点权值，并将父节点的值添加到该组权值中。重复进行上述步骤，直至所有权值都被使用完
构造出的哈夫曼树中，所有初始给出的权值都作为了叶子节点，此时，求出每个叶子节点的带权路径长度，而后相加，就是树的带权路径长度，这个长度是最小的
构造过程

线索二叉树
若n个节点的二叉树使用二叉链表存储，则必然有+1个空指针域，利用这些空指针域来存放节点的前驱和后继节点信息，为此，需要增加两个标志，以区分指针域存放的到底是孩子结点还是遍历节点

若二叉树的二叉链表采用上述结构，则称为线索链表，其中指向前驱后继节点的指针称为线索，加上线索的二叉树称为线索二叉树
树和二叉树的转换
规则
树的最左边节点作为二叉树的左子树，树的其他兄弟节点作为二叉树的右子树节点
示例

连线法
将最左边节点和其兄弟节点都连接起来，而原来的父节点和兄弟节点的连线则断开
图
非线性结构，图中任意两个节点间都可能有直接关系
定义
无向图
图的结点之间连接线是没有箭头的，不分方向
有向图
图的结点之间连接线是箭头，区分A到B,和B到A是两条线
完全图
无向完全图
节点两两之间都有连线，n个结点的连线数为(n-1)+(n-2)+.+1=n*(n-1)/2
有向完全图
节点两两之间都有互通的两个箭头，n个节点的连线数为n*(n-1)
度、出度和入度
度
关联与该顶点的边的数目
在有向图中，顶点的度为出度和入度之和
出度
以该顶点为起点的有向边的数目
入度
以该顶点为终点的有向边的数目
路径
存在一条通路，可以从一个顶点到达另一个顶点
有向图的路径也是有方向的
网
边带权值的图称为网
连通图和连通分量
针对无向图
若从顶点v到顶点u之间是有路径的，则说明v和u之间是连通的
若无向图中任意两个顶点之间都是连通的，则称为连通图
无向图G的极大连通子图称为其连通分量
强连通图和强连通分量
针对有向图
若有向图任意两个项点间都互相在在路径，存在v到u,也存在u到v的路径，则称为强连通图
有向图中的极大连通子图称为其强连通分量
图的存储
邻接矩阵

假设一个图中有n个节点，则使用n阶矩阵来存储这个图中各节点的关系，规则是若节点i到节点j有连线，则矩阵Ri,j=1，否则为0
如果是一个无向图，肯定是沿对角线对称的，只需要存储上三角或者下三角就可以了，而有向图则不一定对称，有向完全图是对称的
邻接链表

用到了两个数据结构，先用一个一维数组将图中所有顶点存储起来， 而后，对此一维数组的每个顶点元素，使用链表挂上和其有连线关系的结点的编号和权值
图的遍历

从图的任意节点出发，沿着某条搜索路径对图中所有节点进行访问且只访问一次
深度优先遍历
从任一顶点出发，遍历到底，直至返回，再选取任一其他节点出发，重复这个过程直至遍历完整个图
广度优先遍历
先访问完一个顶点的所有邻接顶点，而后再依次访问其邻接顶点的所有邻接顶点，类似于层次遍历
图的拓扑序列
AOV网（以顶点表示活动的网）
在有向图中，以顶点表示活动，用有向边表示活动之间的优先关系
用来表示大的工程项目执行计划，因此不能出现有向环
若存在环，则意味着某项活动必须以自身任务的完成为先决条件
若要检测一个工程是否可行，首先应检查对应的AOV网是否存在回路。检测的方法是对有向图构造其顶点的拓扑有序序列
构造方法

将有向图的有向边作为活动开始的顺序，若图中一个节点入度为0，则应该最先执行此活动，而后删除掉此节点和其关联的有向边，再去找图中其他没有入度的结点，执行活动，依次进行
图的最小生成树
假设有n个节点，那么这个图的最小生成树有n-1条边（不会形成环路，是树非图），这n-1条边会将所有顶点都连接成一个树，并且这些边的权值之和最小，称为最小生成树
方法
 
普里姆算法
从任意顶点出发，找出与其邻接的边权值最小的，此时此边的另外一个顶点自动加入树集合中，而后再从这这个树集合的所有顶点中找出与其邻接的边权值最小的，同样此边的另外一个顶点加入树集合中，依次递归，直至图中所有顶点都加入树集合中，此时此树就是该图的最小生成树
克鲁斯卡尔算法（推荐）
这个算法是从边出发的，因为本质是选取权值最小的n-1条边，因此，就将边按权值大小排序，依次选取权值最小的边，直至囊括所有节点，要注意，每次选边后要检查不能形成环路
最短路径

算法分析设计
算法基础
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作
概念
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作
特性
有穷性
一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成
确定性
算法中的每一条指令必须有确切的含义，理解时不会产生二义性。并且在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出
可行性（有效性）
一个算法是可行的，即算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现
输入
一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合
输出
一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量
算法的复杂度
时间复杂度
指程序运行从开始到结束所需要的时间
时间复杂度是一个大概的规模表示，一般以循环次数表示，O（n）说明执行时间是的正比，另外，log对数的时间复杂度一般在查找二叉树的算法中出现。渐进符号O表示一个渐进变化程度，实际变化必须小于等于O括号内的渐进变化程度
空间复杂度
指对一个算法在运行过程中临时占用存储空间大小的度量
一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小
主定理

常用算法

分治法
特征
把一个问题拆分成多个小规模的相同子问题，一般可用递归解决
递归技术
经典问题
斐波那契数列、归并排序、快速排序、矩阵乘法、二分搜索、大整数乘法、汉诺塔
贪心法
特征
局部最优，但整体不见得最优。每步有明确的，既定的策略，一般用于求满意解
经典问题
背包问题(如装箱)、多机调度、找零钱问题
贪心法解决部分背包问题可得最优解
动态规划法
特征
划分子问题，并把子问题结果使用数组存储，利用查询子问题结果构造最终问题结果。（一般自顶向下时间复杂度为O(2^n),自底向上时间复杂度为O(n^a)效率更高)
“最优子结构”和递归式
经典问题
斐波那契数列、矩阵乘法、背包问题、LCS最长公共子序列
回溯法
特征
系统的搜索一个问题的所有解或任一解
经典问题
N皇后问题、迷宫、背包问题
查找
顺序查找
将待查找的关键字为ky的元素从头到尾与表中元素进行比较，如果中间存在关键字为key的元素，则返回成功；否则，则查找失败
平均查找长度(n+1)/2
时间复杂度为
折半（二分）查找
设查找表的元素存储在一维数组r[1.....n]中， 在表中元素已经按照关键字递增方式排序的情况下
首先将待查元素的关键字(key)值与表r中间位置上（下标为mid)记录的关键字进行比较，若相等，则查找成功
若key>r[mid].key,则说明待查记录只可能在后半个子表r[mid+1.....n]中，下一步应在后半个子表中查找
若key<r[mid].key,说明待查记录只可能在前半个子表r[1.....mid-1]中，下一步应在的前半个子表中查找
重复上述步骤，逐步缩小范围，直到查找成功或子表为空失败时为止
前提：顺序存储并有序
时间复杂度为
比较次数最多为
散列表（哈希表）
哈希表则通过一个以记录的关键字为自变量的函数（称为哈希函数）得到该记录的存储地址，所以在哈希表中进行查找操作时，需要用同一哈希函数计算得到待查记录的存储地址，然后到相应的存储单元去获得有关信息再判定查找是否成功。
根据设定的哈希函数H(key)和处理冲突的方法，将一组关键字映射到一个有限的连续的地址集上，并以关键字在地址集中的“像”作为记录在表中的存储位置
散列表查找的基本思想是：已知关键字集合U,最大关键字为，设计一个函数Hash,它以关键字为自变量，关键字的存储地址为因变量，将关键字映射到一个有限的、地址连续的区间T[0....n-1](n<<m)中，这个区间就称为散列表，散列查找中使用的转换函数称为散列函数
解决冲突
线性探测法
按物理地址顺序取下一个空闲的存储空间
伪随机数法
将冲突的数据随机存入任意空闲的地址中
再散列法
原有的散列函数冲突后，继续用此数据计算另外一个哈希函数，用以解决冲突
排序
分类
稳定与不稳定排序
依据是两个相同的值在一个待排序序列中的顺序和排序后的顺序应该是相对不变的，即开始时21在21前，那排序结束后，若该21还在21前，则为稳定排序，不改变相同值的相对顺序
内排序和外排序
依据排序是在内存中进行的还是在外部进行的
算法

插入类排序
直接插入排序
在插入第i个记录时，R1、R2.......Ri-1已经排好序，这时将Ri的关键字ki依次与关键字ki-1、ki-2等进行比较，从而找到应该插入的位置并将R插入，插入位置及其后的记录依次向后移动
前提条件是前i-1个元素是有序的，第i个元素依次从第i-1个元素往前比较，直到找到一个比第i个元素值小的元素，而后插入，插入位置及其后的元素依次向后移动，本质是插入排序
稳定
时间复杂度
空间复杂度
基本有序的情况下
时间复杂度
希尔排序

希尔排序是对直接插入排序算法的改进， 适合于大数据的排序，采用分组的方法，可以提高效率
不稳定
时间复杂度
空间复杂度
选择类排序
直接选择排序

本质就是每次选择出最小的元素进行交换，主要是选择过程，交换过程只有一次。
堆排序

堆排序的方法

1、依据给出的待排序关键字建立初始堆
 
2、输入堆顶元素，并调整堆。重复上述步骤
数据量较大的时候
不稳定
时间复杂度
空间复杂度
交换类排序
冒泡排序

快速排序

分治法
时间量级上，平均性能最好
不稳定
时间复杂度
需要记录所有基准元素时
空间复杂度
需要辅助空间存储左侧数组和右侧数组时
空间复杂度
最差情况
基本有序
时间复杂度
归并排序

分治法
稳定
时间复杂度
空间复杂度
基数排序

稳定
例题

背包算法

2

程序设计语言基础
程序设计语言概述
分类
低级语言
机器语言（计算机硬件只能识别0和1的指令序列），汇编语言
高级语言
功能更强，抽象级别更高，与人们使用的自然语言比较接近
解释和编译

相同
都是将高级语言翻译成计算机硬件认可的机器语言加以执行
不同
编译程序生成独立的可执行文件，直接运行，运行时无法控制源程序，效率高
解释程序不生成可执行文件，可以逐条解释执行，用子调试模式，可以控制源程序， 因为还需要控制程序，因此执行速度慢，效率低
各种语言的特点

Fortran
科学计算，执行效率高
Pascal
为教学而开发的，表达能力强，Delphi
C
指针操作能力强，高效
Lisp
函数式程序语言，符号处理，人工智能
C++
面向对象，高效
Java
面向对象，中间代码，跨平台
C#
面向对象，中间代码，.Net
Prolog
逻辑推理，简洁性，表达能力，数据库和专家系统
Python语言
解释型，面向对象，胶水语言
程序设计语言组成
语法（一组规则）
语义（语法成分的含义）
语用（构成语言的各个记号和使用者的关系)
基本成分
数据成分
指一种程序设计语言的数据和数据类型
数据
常量
程序运行时不可改变
变量
程序运行时可以改变
全局量
存储空间在静态数据区分配
局部量
存储空间在堆栈区分配
数据类型
整型、字符型、双精度、单精度浮点型、布尔型等
运算成分
指明允许使用的运算符号及运算规则
算术运算、逻辑运算、关系运算、位运算等
控制成分
指明语言允许表述的控制结构
顺序结构、选择结构、循环结构（初始化+循环体+循环条件)
传输成分
指明语言允许的数据传输方式
赋值处理、数据的输入输出等
函数

是程序模块的主要成分，是一段具有独立功能的程序
main函数
程序运行的起点
函数声明
函数定义
函数调用
传值调用
将实参的值传递给形参，形参的改变不会导致调用点所传的实参的值改变
实参可以是合法的变量、常量和表达式
传址调用
即引用调用，将实参的地址传递给形参，即相当于实参存储单元的地址引用，因此其值改变的同时就改变了实参的值
实参不能为常量，只能是合法的变量和表达式
语言处理程序基础
编译程序基本原理
编译程序的功能
把某高级语言书写的源程序翻译成与之等价的目标程序（汇编语言或机器语言)
编译程序工作过程

词法分析
是编译过程的第一个阶段
任务是从左到右一个字符一个字符地读入源程序， 即对构成源程序的字符流进行扫描然后根据构词规则识别单词（也称单词符号或符号)
输出记号流
语法分析
是编译过程的一个逻辑阶段
任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，表达式”等等.
语法分析程序判断源程序在结构上是否正确
语法分析方法
自上而下语法分析
最左推导，从左至右。给定文法G和源程序串r。从G的开始符号S出发，通过反复使用产生式对句型中的非终结符进行替换（推导），逐步推导出
自下而上语法分析
最右推导，从右至左。从给定的输入串开始，不断寻找子串与文法G中某个产生式P的候选式进行匹配，并用P的左部代替（归约）之，逐步归约到开始符号S
递归下降思想
原理是利用函数之间的递归调用模拟语法树自上而下的构造过程， 是一种自上而下的语法分析方法
移进-规约思想
设置一个栈，将输入符号逐个移进栈中，栈顶形成某产生式的右部时，就用左部去代替，称为归约。 很明显，这个思想是通过右部来推导出左部，因此是自下而上语法分析的核心思想
输出语法树/分析树
语义分析
是编译过程的一个逻辑阶段
任务是对结构上正确的源程序进行上下文有关性质的审查，进行类型审查。如类型匹配、除法除数不为0等
静态语义错误（在编译阶段能够查找出来） 动态语义错误（只能在运行时发现)

中间代码和目标代码生成
中间代码是根据语义分析产生的，需要经过优化链接，最终生成可执行的目标代码
引入中间代码的目的
进行与机器无关的代码优化处理
常用的中间代码
后缀式（逆波兰式）

主要掌握上述三种表达式即可， 其实就是树的三种遍历，一般正常的表达式是中序遍历即中缀表达式， 根据其构造出树，再按题目要求求出前缀或后缀式
简单求法
后缀表达式是从左到右开始，先把表达式加上括号， 再依次把运算符加到本层次的括号后面
三元式（三地址码）
四元式
树
需要考虑三个问题
如何生成较短的目标代码
如何充分利用计算机中的寄存器，减少目标代码访问存储单元的次数
如何充分利用计算机指令系统的特点，以提高目标代码的质量
文法定义
定义

非终结符
能够推导出其他元素
终结符
最终结果，不能推导出其他元素
产生式
即非终结符推导出终结符的公式
闭包
概念如下图，一般考察闭包可以为0个的情况代入运算

文法类型

常见的程序设计语言
上下文无关文法
语法推导式
正规式

有限自动机
定义

确定的有限自动机和不确定的有限自动机
输入一个字符，看是否能得出唯一的后继， 若能，则是确定的，否则若得出多个后继，则是不确定的
解析

主要有五个符号集，由上图示例，可知用状态来表示十分清晰，由S输入一个0，可得出B,依次类推，一般考试，给出一个状态图，问能否构造出001这样的字符串，解决方法就是从起始S到终点f之间是否有一条路，权值为001。本质就是有向图从起点到终点的遍历
表达式

法律法规与标准化
知识产权基础
保护范围和保护对象
著作权法（版权）
对象和范围
著作权
文学、绘画、摄影等作品
注意事项
1、不需要申请，作品完成即开始保护
2、绘画或摄影作品原件出售（赠予）著作权还归原作者， 原件拥有者有：所有权、展览权
软件著作权法 计算机软件保护条例
对象和范围
软件著作权
软件作品
注意事项
1、不需要申请，作品完成即开始保护
2、登记制度便于举证
专利法
对象和范围
专利权
注意事项
需要申请，专利权有效期是从申请日开始计算
商标法
对象和范围
商标权
注意事项
需要申请，核准之日起商标受保护
反不正当竞争法
对象和范围
商业秘密权
注意事项
1、商业秘密包括技术与经营两个方面
2、必须有保密措施才能认定商业秘密
保护期限

知识产权人的确定
单位和个人的著作权归属情况如下

委托创作中，著作权默认归属于创作方个人，具体如下

单位和委托的区别在于，当合同中未规定著作权的归属时，著作权默认归于单位
侵权判定

不授予专利权
科学发展
智力活动的规则和方法
疾病的诊断和治疗方法
动物和植物品种
用原子核变换方法获得的物质
对平面印刷品的图案、色彩或者二者的结合作出的主要起标识作用的设计
中国公民、法人或者其他组织的作品，不论是否发表，都享有著作权
开发软件所用的思想、处理过程、操作方法或者数学概念不受保护
著作权法不适用于下列情形
法律、法规、国家机关的决议、决定、命令和其他具有立法、行政、司法性质的文件，及其官方正式译文
时事新闻
历法、通用数表、通用表格和公式
知识产权具有严格的地域性， 即各国主管机关依照本国法律授予的知识产权，只能在其本国领域内受法律保护
其他法律细则

标准化基础
分类

编号

多媒体
基本概念
分类
感觉媒体
直接作用于人的感觉器官，使人产生直接感觉的媒体。如：视觉、听觉、触觉等
表示媒体
指传输感觉媒体的中介媒体，即用于数据交换的编码。如：文字、图形、动画、音频和视频等
表现媒体
进行信息输入和信息输出的媒体。如：键盘、鼠标和麦克风；显示器、打印机和音响等
存储媒体
存储表示媒体的物理介质。如磁盘、光盘和内存等
传输媒体
传输表示媒体的物理介质。如电缆、光纤、双绞线等
声音
以声音的带宽来衡量声音的大小，单位是HZ
声音是一种模拟信号，要对其进行处理，就必须将其转化为数字信号
转换过程：采样、量化、编码
人耳能听到的音频信号的频率范围是20Hz~20KHz
声音的采样频率一般为最高频率的两倍，才能保证不失真
未经压缩的数字音频数据的传输率计算公式
数据传输率(bps)=采样频率(Hz)×量化位数(bit)×声道数
声音波形经过数字化后所需占用的存储空间计算公式
声音信号数据量(Byte)=数据传输率(bps)X持续时间(s)/8
数字音乐合成方法
数字调频合成法FM
使高频振荡波的频率按调制信号规律变化的一种调制方式。采用不同调制波频率和调制指数，就可以方便的合成具有不同频谱分布的波形，再现某些乐器的音色。可以采用这种方法得到真有襁特效果的"电子模拟声“，创造出丰富多彩的声音，是真实乐器所不具备的音色
波表合成法Wavetable
将各种真实乐器所能发出的所有声音（包括各个音域、声调）录制下来，存贮为一个波表文件。播放时，根据MD文件纪录的乐曲信息向波表发出指令，从“表格"中逐一找出对应的声音信息，经过合成、加工后回放出来。合成的音质更好
声音特性
音量：即响度，表示声音的强弱程度，主要取决于声波振幅的大小
音高：表示各种声音的高低，主要取决于声波的振动频率，振动频率越高则音越高
音调：表示声音的调子的高低，由声音本身的频率决定
音色：又称为音品，由声音波形的谐波频谱和包络决定
声音文件格式
wav、snd、au、.aif、voc、.mp3、,ra、,mid等
图形和图像
颜色三要素
亮度：彩色明暗深浅程度。
色调（红、绿）：颜色的类别。
饱和度：某一颜色的深浅程度。
彩色空间

图像的属性
分辨率（每英寸像素点数di)
像素深度（存储每个像素所使用的二进制位数）
图像文件格式
bmp、gif、jpg、png、tif、wmf等
图像深度
图像文件中记录一个像素点所需要的位数
显示深度
表示显示缓存中记录屏幕上一个点的位数（bit），也即显示器可以显示的颜色数
水平分辨率
显示器在横向上具有的像素点数目
垂直分辨率
显示器在纵向上具有的像素点数目
矢量图的基本组成单位是图元， 位图的基本组成单位是像素， 视频和动画的基本组成单元是帧
计算
公式

数据压缩
基础

有损压缩与无损压缩

无损压缩编码法
也称冗余压缩法或熵编码法
有损压缩编码法
也称为熵压缩法
下午考试
数据流图
系统开发与运行
考试形式
第一小题补充外部实体
补充外部实体
外部实体就是与系统进行交互的其他实体，可以是大型系统、公司部门、相关人员等，外部实体会与系统进行交互，反应在数据流图中就是一个个事件流， 依据事件的名称结合题目描述可以轻易得出答案
第二小题补充数据存储
补充数据存储
数据存储出现在0层数据流图中，反应系统内部数据的存储，可以直接根据数据流图中数据存储的输入数据流和输出数据流判断该数据存储的信息得出答案，但注意要使用题目说明的数据存储名词作为答案
第三小题补充缺失数据流
补充缺失数据流
首先判断父图和子图是否数据平衡，依据父图和子图间的数据平衡原则核对父图中的每个输入、输出数据流是否都能在子图中找到，直接看外部实体的输入、输出数据流，可以轻易得出答案
而后判断子图内部是否数据平衡，依据子图内数据平衡原则，详细阅读题目描述，对每句话核对是否反映子图中，以及每个加工是否都有输入、输出等原则判断。一般父图中的缺失数据流在是由子图中多条数据流组成的，要注意分析
第四小题考察简单概念
以题目描述和数据流图为主，答案都在题目描述里，更像是阅读理解题
数据库设计
数据库技术基础
考试形式
第一小题补充E-R图
根据题目描述确认哪些实体之间有联系，联系类型是哪一种，而后进行连线即可
第二小题补充关系模式
实际考察的是将E-图转换为关系模式，补充缺失的属性
分成两步
首先需要审题，题目会给出每个关系模式的属性信息， 先将题目中的属性信息和问题对应，将缺少的属性全部补充
而后再按照规则转换，即前面所说的规则，按联系的三种对应方式决定要添加哪些字段
第三小题是简单的情景问答题
一般都是给出一段新的描述，要求新增一种实体-联系类型和关系模式， 本质也是考察联系类型和E-R图转换为关系模式
UML建模
面向对象技术
用例图
类图
序列图
通信图
活动图
状态图
解题技巧
考察UML建模就是考察多种图形，对这些图形的考察一般都是缺失一些关键点，而后要求考生补图
要求认真审题，根据题干说明补齐类名或者对象名或者消息名等等，记住类图和对象图中的多重度（互相独立的分析，掌握表示方法）、类之间的联系标识（多边形端为整体，直线端为个体)。
认真审题，审图，根据说明查缺补漏，一般来说有以下几种题型
1、补充用例图：主要考察补充用例名称、参与者、用例之间的关系，只要认真审题，根据题中描述核对，都可以轻易得出答案
2、补充类图：主要考察补充类名称，需要根据类之间的关系以及多重度来判断，需要牢记类之间关系的图形符号，尤其是组合、聚合和继承的符号，并且观察符号上的多重度数字，与题目描述对应
3、补充状态图：主要补充状态名称，根据题目描述可以轻易得出答案
4、识别设计模式，掌握经典设计模式特点，并结合英文等联想
算法设计
程序设计语言基础
算法设计是下午软件设计中最难的题型，主要难在C代码填空上，因此文老师的建议是先不解决代码填空题（因为最难），先解决其他外围问题（如时间复杂度、算法技巧、取特殊值计算结果)，最后解决代码填空，有助于理解整个题目
解题技巧
1、代码填空：第一小题，最后解决，并不影响解决其他题目，要理解题目算法原理，才能得出答案。另外近几年的算法设计真题有很大的技巧，即便不理解算法原理也可以推导出答案，要结合算法描述中的公式，以及算法代码中类似的分支，能够发现填空的答案在代码中其中地方已经给出，因为算法原理的相似可以通用，尤其是分治法算法。详见文老师真题详解，详述技巧。
要注意的是，当遇到有最小值或最大值参与比较时，若比较出来比最小值更小，接下来肯定要更新这个最小值以及其下标元素值。当遇到一些条件判断的填空时，要注意对应上下文查看哪些变量是作为控制的。
2、算法、时间复杂度：第二小题，先做，考察何种算法很好分辨，涉及到分组就是分治法，局部最优就是贪心法，整体规划最优就是动态规划法，迷宫类的问题是回溯法，记住关键字很好区分；时间复杂度就是看C代码中的fo循环层数和每一层的循环次数，涉及到二分必然有O(logn)。
3、特殊值计算：第三小题，一般应该先做，不需要根据C代码，直接根据题目给出的算法原理一步步推导即可得出答案，耐心推导并不难。但要注意，如果遇到算法原理十分复杂的，建议放弃，掌握问题1和2的技巧即可。