软考背诵笔记

计算机硬件组成

运算器，控制器，存储器，输入设备，输出设备

中央处理单元（CPU）

控制器组成

指令寄存器（IR）:暂存cpu执行指令

程序计数器（PC）:存放下一条执行地址

地址寄存器（AR）:保存当前CPU所访问的内存地址

指令译码器（ID）:分析指令操作码

运算器的组成

算术逻辑运算单元ALU：实现对数据的逻辑和算术运算

累加寄存器AC：源头运算结果和源操作数的存放区

数据缓冲寄存器DR：暂时存放内容的指令和数据

状态条件寄存器PSW：保存指令运算结果的条码内容，如内存溢出

寻址方式

快到慢：立即寻址--寄存器寻址--直接寻址==寄存器间接寻址--间接寻址

码制

假设二进制机器字长是n+1,且为整数

原码表示范围：-（2^n-1）≤ x ≤ 2^-1

反码表示范围：-（2^n-1）≤ x ≤ 2^-1

补码表示范围：-2^n ≤ x ≤ 2^n-1

移码表示范围：-2^n ≤ x ≤ 2^n-1

原码小数表示范围：-（1-2^-n） ~ 1-2^-n

补码小数表示范围：-1 ~ 1-2^-n

校验码

奇偶校验码：只能检一位错，且不能纠错

循环冗余校验码CRC：只能检错不能纠错，摸2运算

海明码：利用奇偶性来检错纠错

公式：2^k-1 ≥ n+k

地址映射

全相联映射：主存的任意一块可以映射到Cache中的任意一块

直接相联映射：主存中的一块，只能直接映射到Cache中特定块中

组相联映射：组跟组之间直接相联，组内全相联

逻辑运算

与（and）：全1为1 ， 有0为0     全真为真，有假为假

或（or）：全0为0，有1为1       有真为真，全假为假

非（not）：0变1，1变0         真变假，假变真

异或（xor）：相同为0，不同为1       同假异真

同或（xnor）：相同为1，不同为0         同真异假

与非（nand）：先与后非，全1为0，有0为1    全真为假，有假为真

或非（nor）：先或后非，全0为1，有1为0     全假为真，有真为假

指令RISC和CISC

RISC 和CISC（精简指令集计算机和复杂指令集计算机）

区别	RISC	CISC
指令种类	少，简单	多，丰富
指令复杂度	低，简单	高，复杂
指令长度	固定	变化
寻址方式	少	复杂多样
实现（译码）方式	硬布线控制逻辑（组合逻辑控制器）	微程序控制器
通用寄存器数量	多，大量	一般
流水线技术	支持	不支持

Flynn分类法

除了单单，其余主存模块都是多个

指令流---控制部分匹配，同多同少

数据流----处理器匹配，同多同少

体系结构类型	结构	关键特性	代表
单指令流单数据流SISD	控制部分：1个 处理器：1个 主存模块：1个		单处理器系统
单指令流多数据流SIMD	控制部分：一个 处理器：多个 主存模块：多个	各个处理器以异步的 形式执行同一条指令	并行处理机 阵列处理机 超级向量处理机
多指令流单数据流MISD	控制部分：多个 处理器：一个 主存模块：多个	被证明不可能，至少 是不实际的	目前没有，有文献称流水线计算机为此类
多指令流多数据流MIMD	控制部分：多个 处理器：多个 主存模块：多个	能够实现作业、任务、 指令等各级全面并行	多处理及系统 多计算机

流水线

周期

执行时间

吞吐率：总指令条数/流水线执行时间

加速比

I/O

I/O软件层次结构（越往上越与硬件无关）

输入输出技术

程序控制（查询）方式：CPU主动查询，效率低

程序中断方式：外部请求中断，等待CPU处理，效率相对高

DMA方式（直接主存存取）：CPU只需初始化，全程DMA控制器完成，在主存和外设建立通路，效率高

中断响应时间：发出中断请求，到开始进入中断处理程序

中断处理时间：中断处理程序开始到中断处理程序结束

中断向量：提供中断处理程序的入口地址，多级中断嵌套，适用堆栈来保护断点和现场

比特转换

1MB=1024KB=2^10KB=2^20B

1B(Byte/字节)=8bit（b/比特）

软件工程

关键路径：起点至终点最长的路径，关键路径上的活动均为关键活动

松弛时间：最早开始时间到最迟开始时间之差，或者最早结束时间到最吃结束时间之差

 文件索引

储存器

区别	SRAM（静态随机存取存储器）	DRAM（动态随机存取存储器）
刷新机制	不需要刷新就可保存数据，只需保持通电数据就可恒久保持	因为适用电容作为储存单元，电容器的电荷会逐渐泄露，所以需要定期刷新，以维持数据稳定
速度	不刷新所以读写快	要刷新所以读写慢，且电容充电需要时间
功耗	功耗大，因为要维持触发器的稳定状态	功耗低，因为只有再读写的时候才消耗能量
成本	由于结构相对复杂集成度低，因此成本较高	由于每个存储单元的面积相对较小，有更高的存储密度，因此成本低
应用场景	对速度要求高的场合，如CPU的L1缓存，L2缓存	广泛用于计算机的主存储器，图形显卡，移动设备，服务器和数据中心等，用于存储正在运行的程序和临时数据

文件管理

绝对路径：/开始，从根目录开始，包括盘符

相对路径：当前工作目录下的路径名

全文件名：绝对路径+文件名

队列和栈

队列：先进先出

栈：先进后出

软件工程

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

软件生存周期

可行性分析与项目开发计划：确定软件开发目标，可行性，产出可行性分析报告和项目开发计划，确定系统逻辑模型

需求分析：确定软件功能、性能、数据、系欸按等，产出软件需求说明书

概要设计：设计软件结构，产生概要设计说明书

详细设计：对每个模块共嗯那个进行详细描述,把功能描述转化为精确，结构化的过程描述，产生详细设计文档

编码：控制结构转计算机代码，产出源程序清单

测试：保证软件质量，设计测试用例检查软件，产出软件测试计划、测试用例、软件测试报告

能力成熟度CMMI

初始级：过程不可预测且缺乏控制

已管理：过程为项目服务

已定义：过程为组织服务

定量管理：过程为以度量和控制

优化：集中于过程改进

模型

统一过程模型UP

“用例和风险驱动，以架构为中心，迭代并增量”的开发过程

每一次迭代都是一次完整的开发过程，包括整个开发生命周期

开发阶段：确认需求，风险评估

精华阶段：需求分析，架构设计

构建阶段：系统构建，产生实现模型

移交阶段：产生软件增量，β测试，交付系统

瀑布模型

结构化方法模型，适用于需求明确，二次开发

V模型

瀑布模型的变种，增加多轮测试，测试贯穿始终

原型

快速原型开发，与瀑布模型相反，适用于需求不明确

螺旋模型

多模型混合，像原型，增加风险分析，适用于需求不明确

增量模型

最先优先级高的开发，开发部分交付部分，依次增加，每次产品可独立操作

喷泉模型

用户需求为动力，对象为驱动，适用于面向对象，具有迭代性和无间隙性

基于构建的开发模型

包装构件，构建构件库，组成系统，增强复用性，节省时间和成本

敏捷开发

尽可能早，持续的对有价值的软件的交付

自适应开发ASD

强调开发的适应性

水晶方法Crystal

每一个不同的项目，都需要不同的策略，约定和方法论

特性驱动开发

针对中小型软件开发项目，强调简化，使用，易被开发团队接受

适用于需求经常变动的项目

并列争求法Scrum

迭代的增量化过程，每30天一次的迭代为一个冲刺，按需求优先级实现产品

极限编程XP

轻量级、高效、低风险、柔性、可预测性、科学

四大价值观：沟通、简单性、反馈、勇气

五大原则：快速反馈，简单性假设，逐步修改，提倡更改，优质工作

12个最佳实践：计划游戏，小型发布，隐喻，简单设计，测试先行，重构，结队编程，集体代码所有制，持续集成，某周工作40小时，现场客户，编码标准

软件工具

开发工具：分析，设计，编辑，排错，测试工具

维护工具：版本控制，逆向工程，再工程，文档分析，开发信息库工具

管理和支持工具：项目管理，配置管理，软件评价工具

软件项目

4P：人员，产品。过程。项目

COCOMO：软件项目规模估算法，以代码行估算每个程序员二的工作量，累加成本

基本模型：静态变量模型，以代码行loc计算软件开发工作量

中间模型：在基础模型的基础上，涉及产品，人员，项目，硬件的因素调整工作量估算

详细模型：包括中间模型所有特性，加考虑每个步骤的影响

COCOMOII：COCOMO的升级，考虑多个成品驱动因子

应用组装模型

早期设计阶段模型

体系结构阶段模型

进度管理

基本原则：划分，相互依赖，时间分配，工作量确认。确认责任，明确输出结果，确定里程碑

Ganntt图：能反映活动并行关系，无法反映活动的依赖关系

PERT图：有向图，反应活动的依赖关系，无法反映并行关系

软件项目的组织

主程序员制小组：主程序员全权负责，必要时其他代替，适合大规模项目

民主制小组：成员地位平等，任何决策全员投票，适合于规模小，开发人员少，采用新技术，确定性小的项目

层次式小组：分2层次，组长领导高级程序员，高级程序员领导程序员

软件质量管理

可维护性（常考）

易分析性：与为诊断缺陷，失效原因，为判定待修改部分  有关的软件属性

易改变性：与进行修改，排错，适应环境变化所需努力有关的软件属性

易测试性：为确认经修改软件所需努力有关的软件属性

稳定性：与修改造成未预料效果风险的软件属性

质量特性	质量子特性
功能性	适用、准确、互用、依从、安全
可靠性	成熟、容错、易恢复
易使用性	易理解、易学、易操作
效率	时间特性、资源特性
可维护性	易分析、易改变、易测试、稳定
可移植性	适应、易安装、一致、易替换

软件容错技术

设计质量、程序质量

实现容错的主要手段---冗余

结构冗余：静态（通过表决和比较，少数服从多数)，动态（多重模块待机备份，故障时切换备份机），混合冗余（二者混合）

信息冗余：在数据上加额外的信息检错纠错，如校验码原理

时间冗余：遇到错误时重复执行，如回滚，重复执行还错转为错误处理逻辑

冗余附加技术：实现数据结构，信息和时间冗余技术所需要的技术和资源，包括程序、指令、数据、存放和调动他们空间和通道等

风险管理

特性：不确定性（可能发生可能不），损失（发生产生的恶性后果）

项目风险：威胁项目计划（指预算，进度，人员，资源利用相关者，需求等潜在问题，项目复杂度，规模，结构不确定性也属于项目风险）

技术风险：威胁开发软件的质量和角度时间（指设计，实现，接口。验证，维护等潜在问题。规格说明的歧义性、技术的不正确性、技术陈旧以及前沿技术也是技术风险因素）

商业风险：威胁到开发软件的生存能力

        市场风险:市场无需求的产品

        策略风险:产品不符合整体商业策略

        销售风险:不知道如何销售产品

        管理风险:用于重点转移或人员变动导致失去管理支持

        预算风险:没得到预算或人员保证

风险管理过程

风险识别：形成风险列表

风险预测：从风险可能发生的概率和风险产生的后果预测，风险曝光度=风险发生概率*损失

风险评估：定义风险参照水准，将识别出来的风险评估分类

风险控制：风险避免，风险监控，RMMM计划（风险环节，监控，管理计划）

软件度量

软件属性

外部属性：面向管理者用户，可直接测量，性能指标

内部属性：面向产品本省，只可间接测量，如可靠度

McCabe算法

环路复杂度，有向变m，节点数n，复杂度m-n+2

计算机网络

计算机网络概念

实现远程通信，远程信息处理，资源共享

功能：数据通信，资源共享，负载均衡，高可靠性

分类：局域网LAN，城域网MAN，广域网WAN

拓扑结构

总线型：利用率低，干扰大，价格低

星型：交换机形成的局域网，中央单元负荷大

环型：流动方向固定，效率低，扩展难

树型：总线型的扩充，分级结构

分布式：任意节点连接，管理难，成本高

OSI七层模型

从上到下：物理层，数据链路层，网络层，传输层，会话层，表示层，应用层

物理层：二进制数据传输

数据链路层：将数据封装成帧，传至局域网内主机

网络层：数据分组传输和路由选择，传至互联网的主机

传输层：端到端的连接，传至主机端口

会话层：管理主机间的对话，提供会话管理服务

表示层：提供解释所交换的数据的含义的服务，包括数据间的转换，压缩，加密等操作，对数据进行处理

应用层：实现具体应用功能，直接进程间的通信

网络互联硬件

物理层：中继器（扩大信息），集线器Hup（多路中断）---无法隔离冲突或广播域

数据链路层：网桥（分析帧地址），交换机（多路网桥，Mac地址表）---可以隔离冲突域不可隔离广播域

网络层：路由器（连接多个逻辑上分开的网络，路由选择）--可以歌库冲突与也可隔离广播域

应用层：网关（连接不同类型，且协议差别较大的网络，协议转换）

有线介质：双绞线，同轴电缆，光纤

无线介质：微波，红外线，卫星通信

局域网协议

IEEE802.3：标准以太网，10Mbps,传输介质同轴电缆

IEEE802.3u：快速以太网，100Mbps，传输介质双绞线

IEEE802.3z：千兆以太网，1000Mbps，传输介质双绞线或光纤

TCP/IP协议簇

特性：逻辑编制，路由选择，域名解析，错误检测，流量控制

网络层协议

IP：核心协议，无连接，不可靠

ICMP：因特网信息控制协议，检测网络通信顺畅

ARP/RARP：地址解析协议，反地址解析协议

ARP：IP地址-->物理地址

RARP：物理地址-->IP地址

传输层协议

TCP：可靠（三次握手）

UDP：不可靠，一般用于音频，视频传输

应用层协议

可靠的-------------------------------------------

FTP：文件传输协议，21控制端口，20传输端口

HTTP：80，超文本传输协议，加SSL变HTTS(端口443)

SMTP：发送，23，简单邮件传输协议，邮件报文用ASCLL格式表示

POP3：收取，110，邮件传输

Telent：23，远程连接协议

不可靠------------------------------------------------

TFTP：69,小文件传输协议

SNMP：161,简单网络管理协议

DHCP：67,动态分配IP地址协议，客户机、服务器模型，默认租期8天

DNS：53,域名解析协议，域名解析为IP

IP地址

全0全1不可分配

A类：8位

B类：16位

C类：24位

D类组播

E类保留

防护墙

网络级防火墙：层次低，效率高，使用包过滤、状态检测手段，伪装数据无法过滤，只检测网络包外在

应用级防火墙：层次高、效率低，网络包拆开检测，耗时久，安全强度高，包括双宿主主机，屏蔽主机网关被屏蔽子网等方法。

被屏蔽子网方法：在内部和外部之间，加一个屏蔽子网，称为DMZ（非军事区），这样内网和外网之间必须多经过一道防火墙，屏蔽子网中一般存放的是邮件服务器，WEB服务器这些内外网交互的服务器，可以屏蔽掉一些来自内网的攻击，但完全来自内网的服务器攻击还是无法屏蔽

计算机木马病毒

病毒：破坏计算机功能，破坏数据

病毒特点：传染，隐蔽，潜伏，破坏，针对，衍生，寄生，未知

木马：控制计算机的工具，监视操作，盗取数据

病毒木马种类

系统引导性病毒

文件外壳病毒

目录行病毒

蠕虫病毒：感染EXE可执行文件，熊猫烧香，罗密欧与朱丽叶，恶魔，尼姆达，冲击波

木马：QQ消息尾巴木马，特洛伊木马，冰河

宏病毒：感染word,excel等文件，美丽沙，台湾一号

CIH病毒：史上唯一破外硬件的病毒

红色代码：蠕虫+木马

网络安全

五大要素

保密性，完整性，可用性，可控性，不可抵赖性

网络攻击

拒绝重放ARP：截取某次合法数据拷贝，处于非法目的重新发送

拒绝服务DOS：对信息或资源的合法访问被无条件拒绝

旁路控制

授权侵犯

特洛伊木马

窃听

业务流分析

信息泄露

破坏信息完整性

加密技术

明文：实际数据

密文：加密数据

加密：明文转密文过程

解密：密文转明文过程

加密算法：公开；规则包括代换，置换

对称加密：安全性不高，密钥分发困难，但快，适合大数据；

        “3S5I”：DES(56位密钥)，3DES，AQS，RC-5，IDEA（128位密码）

非对称加密：保密性好，速度慢，不适合文件加密，适合少量数据加密

        “AACC”：RSA，DSA，ECC

公钥体系中：公钥加密认证，私钥解密签名

常见网络诊断命令

Ping:检查网络是否联通

Tracert:确定IP数据包访问目标所采取的路径，若网络不通，能定位到具体哪里不通

Ipconfig:显示网络配置值（ip地址，MAC地址，网关地址）

 ipconfig/release:DHCP客户端手工释放IP地址

 ipconfig/flushdns:清楚本地DNS缓存内容

 ipconfig/displaydns:显示本地DNS内容

 ipconfig/registerdns:DNS客户端手工向服务器进行注册

 ipconfig/renew:DHCP客服端手工向服务器刷新请求（重新申请IP地址）

Nslookup:查询dns记录

Netstat:显示网络连接，路由表，网络接口信息

操作系统

死锁

产生条件

资源互斥

占用并等待

不剥夺

形成环路

破坏死锁

预防

避免：一般采用银行家算法

检测

解除

死锁计算

n个进程，r个资源

产生死锁的最大资源数：n*(r-1)

不发生死锁的最小资源数：n*(r-1)+1

数据库

三级模式两级映射

内模式：储存文件

概念模式（模式）：基本表

外模式：视图

模式/内模式

内模式/外模式

数据库设计

需求分析：产出数据流图，数据字典，需求说明书

概念结构分析：设计ER图

逻辑结构分析：将ER转关系模式，即实际表和表属性

物理设计分析：生成物理数据库

关系代数运算

笛卡尔积X：S1 X S2,列S1+S1,数据行S1*S1

投影π:选择关系模式的某列

选择σ：选择关系模式的某条记录

自然连接：列：去重显示，记录：属性值相同的记录

函数依赖

部分函数依赖：A可确定C,AB也可确定C，AB中的一部分（即A）可以确定C，称为部分函数依赖

传递函数依赖：当A和B不等价时，A可以确定B，B可以确定C，则A可以确定C，是传递函数依赖

键与约束

实体完整性约束：主键约束

参照完整性约束：外键约束

用户自定义完整性约束：自定义，如age字段要求0-150

范式

第一范式：不存在复合属性

第二范式：不存在部分依赖

第三范式：不存在传递依赖

BC范式：每个属性都不部分依赖于候选键也不传递依赖于候选键

事务管理

原子性：操作，要么都做，要么都不做

一致性：数据，事务发生后数据一致

隔离性：执行，不同事务之间互不干涉

持续性：改变，结果持续性

并发控制

并发问题：丢失更新，不可重复读，读脏数据

控制技术：封锁（排他锁X，共享锁S）

三级封锁协议

一级封锁协议：事务在修改数据R之前，必须对其加排他锁，直到事务结束才释放。一级封锁协议可以解决丢失更新的问题

二级封锁协议：在一级封锁协议的基础上，加上事务T在读数据R之前必须先对其加上S锁，读完之后立即释放S锁。二级封锁协议可以解决读脏数据的问题

三级封锁协议：在一级封锁协议的基础上，加上事务T在读数据R前必须对其加上S锁，直到事务结束时释放S锁。三级封锁协议除了防止修改和不读脏数据外，还进一步防止了不可重复读

分布式数据库

分布式透明性

分片透明性：无需知道逻辑上储存的表如何让分块储存

位置透明性：无需知道数据储存位置的改变

逻辑透明性：无需知道局部使用的是那种数据结构

复制透明性：无需知道复制的数据从何而来

程序设计语言

低级语言：机器语言

高级语言：功能语言

各种程序语言特点

Fortrany语言：科学计算，执行效率高

Pscal语言：为教学而开发，表达能力强

C语言：指针操作能力强，高效

C++：面向对象，高效

C#：面向对象，中间代码，.NET

Lisp语言：函数式程序语言，符号处理，人工智能

JAVA语言：面向对象，中间代码，跨平台

Prolog：逻辑推理，简洁性，表达能力，数据库和专家系统

解释：将高级语言翻译成计算机认可的机器语言加以执行，生成不可执行文件，可以逐条解释执行，用于调试模式，可以控制源程序，慢，低效

编译：将高级语言翻译成计算机认可的机器语言加以执行，生成独立可执行文件，无法控制源程序，高效

程序编译基本原理

源程序

⬇

词法分析：单词排错

⬇

语法分析：语句排错

⬇

语义分析：语义排错，比如除数不为0，分析静态语义错误（编译阶段排查）和动态语义错误（运行阶段排查）

⬇

中间代码生成：进行与机器无关的代码优化，后缀式（逆波兰式），三元式（三地址码），四元式，图和树

⬇

代码优化

⬇

目标代码生成

⬇

目标代码

系统开发与运行

高内聚，低耦合

内聚 

内聚程度从低到高：偶然逻辑，时间过程，通信顺序，功能

内聚分类	定义	记忆关键字
偶然内聚	一个模块内各元素之间没有任何联系	无直接联系
逻辑内聚	模块内执行逻辑相似，参数决定执行哪一个	逻辑相似，参数决定
时间内聚	需要同时执行的组合动作	同时执行
过程内聚	一个模块完成多个任务，这些任务必须按照指定的过程顺序执行	指定过程顺序
通信内聚	模块内所有处理元素都在同一数据结构上操作，或者处理使用相同的输入或产生相同输出	相同数据结构，相同输入输出
顺序内聚	一个模块中各个处理元素都密切相关与同一功能，且必须顺序执行，前一功能的输出就是下一功能的输入	顺序执行，前输出为后输入
功能内聚	最强的内聚，模块中所有元素共同作用完成一个功能，缺一不可	共同作用，缺一不可

耦合

耦合程度从低到高：无直接数据，标记控制 ，外部公共，内容

耦合分类	定义	记忆关键字
无直接耦合	模块之间无直接关系，分别从属不同模块的控制和调用，不传递任何信息	无直接关系
数据耦合	模块间又调用，传递简单的数据值（值传递）	传递数据值调用
标记耦合	模块间传递数据结构	数据结构传递
控制耦合	一个模块调用另一个模块，传递的是控制变量，被调用的模块通过改变控制变量的值决定执行某一功能	控制变量，决定执行某一功能
外部耦合	模块间通过外环境联合（如I/O）	软件外部环境
公共耦合	通过公共数据环境相互作用的那些模块间的耦合	公共数据结构
内容耦合	当一个模块直接使用另一个模块的内部数据，或者通过非正式入口转入另一个模块内部	模块内部关联（直接或者非正式入口进入）

 系统设计

概要设计：设计系统总体结构，数据结构，数据库设计，编写概要设计文档，评审

详细设计：模块内详细算法设计，数据结构设计，数据库物理设计，其他设计（代码，界面，输入输出格式），编写详细设设计文档，评审

测试基础知识

成功的测试：是发现迄今为止未发现的错误

测试原则

尽早不断的测试

避免由开发人员和开发小组测试

设计测试方案时，不仅要确定输入数据，还要确定预期的输出结果

即要包含有效、合理的测试用例，也包含无效、不合理的测试用例

检验程序是否做了该做的事，且是否做了不该做的事

严格按照测试计划进行

妥善保存测试用例和测试计划

测试用例可重复使用或追加测试

测试阶段

单元测试：对单个模块进行测试（接口，信息，功能）。测试依据是软件详细说明书

集成测试：将模块组合起来测试（一次性组装：简单，省时，发现错少，适用小项目；增量组装：耗时，发现错误多，又可分为：自顶向下，自底向上，混合式）

确认测试：功能测试，分内部确认（无用户），Alpha测试（用户+开环环境测），Beat测试（用户+实际环境测），验收测试（用户根据SR对项目验收）

系统测试：性能测试，分负载测试（测极限），强度测试（资源特别低），容量测试（并发，最大用户数）

回归测试：软件改错或变更后，再测试 

动态测试：黑盒测试（功能测试，不了解软件代码结构），白盒测试（结构性测试，明确代码结构）

静态测试：

测试策略

自底向上：从底开始，需编写驱动程序，优点：较早验证底层模块

自顶向下：从顶开始，需编写桩程序，优点：较早验证主要控制和判断点

三明治：前两者混合，优缺点也混合，测试工作量大

测试用例设计

黑盒测试：等价划分，边界值划分

白盒测试

        语句覆盖：所有语句执行一遍

        判定覆盖：所有判断语句真假分支执行一遍

        条件覆盖：对代码中一个条件，可能式组合的，如a>0&b>0，判断覆盖只针对词组和的真假分支做两个测试用例，而条件覆盖是需要对每个独立的条件都做真假分支的测试用例，共可有4个测试用例，测试层级更高。主要区别：条件覆盖，针对每个条件都要真假覆盖，判定覆盖，只针对每个判断语句

        判定/条件覆盖：使判定中每个条件的所有可能取值（真/假）至少出现一次，并且每个判定本身的判定结果（真/假）也至少出现一次，即两种覆盖的综合。

        条件组合覆盖：

        路径覆盖：逻辑代码中所有可行路径都覆盖了，覆盖层级最高。

标准化知识产权

客体类型	权力类型	保护期限
公民作品	署名权，修改权，保护作品完整权	没有限制
	发表权，适用权和获得报酬权	作者终生及其死亡后50年（低50年的12月31日）
单位作品	发表权，适用权和获得报酬权	50年（首次发表后的第50 年的12月31日），若其间未发表，不保护
公民软件产品	署名权，修改权	没有时间限制
	发表权，复制权，发行权，出租权，信息网络传播权，翻译权，使用许可权，获得报酬权，转让权	作者终生及其死亡后50年（低50年的12月31日），合作开发以最后死亡作者为准
单位软件产品	发表权，复制权，发行权，出租权，信息网络传播权，翻译权，使用许可权，获得报酬权，转让权	50年（首次发表后的第50 年的12月31日），若其间未发表，不保护
注册商标		有效期10年（若注册人死亡或倒闭1年后，为转移则可注销，期满后6个月内必须虚注）
发明专利权		保护期为20年（从申请日开始）
实用新型和外观设计专利权		保护期为20年（从申请日开始）
商业秘密		不确定，公开后公众可用

面向对象分析，执行的活动：认定对象，组织对象，描述对象间的相互作用，确定对象的操作

面向对象设计，执行的活动：识别类及对象，定义属性，定义服务，识别关系，识别包

UML

关系

依赖：一个事务语义依赖于另一个事务变化

关联：分组合和聚合，组合式组成部分（关联性更强），聚合是聚在一起

泛化：一般/特殊   子类/父类的关系

实现：

设计模式

分类

口诀：工适模解（类）、适桥组装外享代（结构型）
	创建型5	结构型7	行为型11
类	工厂方法模式（facatory method）	适配器模式(adapter)	模板方法模式(template method)	解释器模式(interpreter)
对象	抽象工厂模式(abstract factory) 原型模式(prototype) 单例模式(singleton) 构建器模式(builder)	桥接模式(bridge) 组合模式(composite) 装饰模式(decorator) 外观模式(facade) 享元模式(flyweight) 代理模式(proxy)	职责链模式(chain of responsibility) 命令模式(command) 迭代器模式(iterator) 中介者模式(mediator)	备忘录模式(memento) 观察者模式(observer) 状态模式(state) 策略模式(strategy) 访问者模式(visitor)

创建型设计模式

设计模式名称	简要说明	记忆关键字
抽象工厂模式（abstract factory）	提供一个接口，可以创建一系列相关或相互依赖的对象，而无需定他们具体的类	生产成系列对象
构建器模式（builder）	将一个复杂类的表示与其构造相分离，使得相同的构建过程能够得出不同的表示	复杂对象构造
工厂方法模式（factory method）	定义一个创建对象的接口，但由其子类决定需要实例化哪一个类，工厂方法使得子类实例化的过程推迟	动态生产一个对象
原型模式（prototype）	用原型实例指定创建对象的类型，并且通过拷贝这个原型来创建新的对象	克隆对象
单例模式（singleton）	保证一个类只有一个实例，并且提供一个访问它的全局访问点	单实例

结构型设计模式

设计模式名称	简要说明	记忆关键字
适配器模式（adapter）	将一个类的接口转换成用户希望得到的另一种接口，它使原本不相容的接口得以相融后协同工作	转换接口
桥接模式（bridge）	将类的抽象部分和他的实现部分分离开来，使他们可以独立的变化，抽象部分通过实现部分的接口与实现部分联系起来 此时接口就像一座桥梁一样	继承树拆分
组合模式（composite）	将具有层级关系的多个对象组合成树形结构以表示“整体-部分”的层次结构，使得用户对单个对象和组合对象的使用具有一致性	树形目录结构
装饰模式（decorator）	动态的给一个对象添加一些额外的职责、功能。 就像添加了一些装饰，他提供了用子类扩展功能的一个灵活替代，比派生一个子类更加灵活	附加职责
外观模式（facade）	为子类系统中的一组接口提供一个接口，从而简化该子类的使用，在外界看来，系统就只有一个接口（外观）	对外统一接口
享元模式（flyweight）	支持大量细粒度对象共享元对象的有效方法	文章共享文字方法
代理模式（proxy）	为其他对象提供一个代理用于控制这个对象的访问	快捷方式

行为型设计模式

数据结构

矩阵

对稀疏矩阵的压缩方式：

1，三元组顺序表

2，行逻辑连接的顺序表

3，十字链表

矩阵顶点的出度

有向图的矩阵，是非对称矩阵，各顶点的出度是矩阵行中1的个数

有n个顶点e条边（弧）的无向图邻接矩阵中：邻接大小为n^2，非0元素的个数是2e，0元素的个数是n^2-2e

有n个顶点e条边（弧）的有向图邻接矩阵中：邻接大小为n^2，非0元素的个数是e，0元素的个数是n^2-e

邻接矩阵优点

• 方便检查任意一对顶点间是否存在边
• 方便找任一顶点的所有邻接点（有边直接相连的顶点）
• 方便计算任一顶点的度（从该点发出的边数为出度，指向该点的变数为入度）
  • 无向图：对应行（列）非0元素个数
  • 有向图：对应行非0元素的个数是出度，对应列非0元素的个数是入度

邻接矩阵缺点

• 不便于增加和删除顶点
• 邻接矩阵的空间复杂度为O(n^2),跟其有的边的条数无关，只与顶点数有关，无论边少还是边多，空间复杂度都为O(n^2),浪费空间----存稀疏图（点很多而边很少）有大量无效元素
• 浪费时间---统计稀疏图中一共有多少条边，因为必须遍历所有元素

树与二叉树

定义：

节点的度：某个节点的孩子节点的数，就是他的度（如图：红色数字就为每个节点的度）

树的度：正课书中度最大的节点的度，就为整个树的度（如图：树的度是2）

二叉树的重要特性：

1，在二叉树的第i层上，最多有2^(i-1)个节点（i>0）

2，深度为K的二叉树最多有2^k - 1个节点（k>0）

3，对任何一颗二叉树，如果其叶子节点数为x，度为2的节点数是y，则x=y+1

遍历

前序遍历：根左右 1 2 4 5 7 8 3 6

中序遍历：左根右 4 2 7 8 5 1 3 6

后续遍历：左右根 4 8 7 5 2 1 3 6

层次遍历：1 2 3 4 5 6 7 8

查找二叉树

所有左子树<根节点，右子树>根节点

最优二叉树（哈夫曼树）

树的路径长度；权；带权路径长度（路径长度*权）；树的带权路径长度:

如图比如：

2的带权路径长度=2*2=4    4的带权路径长度3*4=12

8的带权路径长度=3*8=24     1的带权路径长度1*1=1

所有加起来4+12+24+1=41就是整棵树的带权路径长度

哈夫曼树的带权路径长度最短

例题1：

例题2：

线索二叉树

平衡二叉树

平衡度：左-右   （有则为1 ，没有则为0，左有右没有，1-0=1，右有左没有0-1=-1）

节点深度：有多少层，比如下图左图的39节点，左子树深度就有3层，右边为0

大顶堆

        根节点（堆顶元素）是所有节点中的最大值（父节点都大于左右子节点）。大顶堆常用于实现优先队列，且可用于构建堆排序算法。

小顶堆

        小顶堆中的根节点是所有节点中的最小值（父节点都小于左右子节点）。小顶堆常用于问题如：查找流中的前 K 个最小元素。

二叉排序树

一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

左边子树值<根节点值<右子树值

例题：

构造结果：