自己整理的笔记，一些常考的、要熟悉记忆的知识点。
上午基础知识
1、海明码校验：
数据位数为n，校验码为k位
2^k-1≥n+k
例子：数据位n = 8
2^3-1=7，7>=8+3不成立
2^4-1=15，15>8+4成立，故8位数据需要4位校验码。
2、后缀表达式规则（逆波兰式）：
从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。（减和除都是下方的数字放在前）
3、面向对象开发方法有Booch方法、Coad方法和OMT方法。Jackson方法是一种面向数据结构的开发方法。
4、词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成。
中间代码生成和代码优化不是必须的。
各个阶段处理的错误：
词法分析阶段处理的错误：非法字符、单词拼写错误等
语法分析阶段处理的错误：标点符号错误、表达式中缺少操作数、括号不匹配等有关语言结构上的错误
静态语义分析阶段（即语义分析阶段）处理的错误：运算符与运算对象类型不合法等错误。
目标代码生成（执行阶段）处理的错误：动态语义错误，包括陷入死循环、变量取零时做除数、引用数组元素下标越界等错误等。
5、原码反码补码（正数都一样，正数0负数1，负数反码收尾1后面取反，负数补码是反码+1）
6、DMA直接存储器存储。 IO模块直接到主存，无须中央处理器的中转。
7、寄存器：
程序计数器PC：存放下一条指令所在单元的地址的地方。
指令寄存器IR：用来保存当前正在执行的一条指令。
数据寄存器：用来保存操作数和运算结果等信息。
地址寄存器：保存当前CPU所访问的内存单元的地址。
8、操作系统的三态模型：运行->等待->就绪
9、软件开发模型：
瀑布模型
结构化方法的模型，先计划再分阶段执行、执行完成后再评审。
问题：需求阶段难以把控，往往不明确，容易导致项目的失败
适用于：需求明确，二次开发
原型模型、演化模型、增量模型（迭代思想）
原型模型：在开发初期构造简易系统，调整并开发
适用于：需求不明确
螺旋模型：融合了原型、瀑布模型、演化模型的特征，引入了风险分析
V模型：接近瀑布模型，强调测试地位，提早写测试计划，测试贯穿于开发的始终
喷泉模型：面向对象模型，迭代，无间隙
RAD：快速开发模型，用可视化工具开发，瀑布+构件组装
构件组装模型（CBSD）：构建，组装，提高了软件开发的复用性
统一过程（UP、RUP）：大型项目，初始-细化-构建-交付
特点：用例驱动，以架构为中心，迭代和增量
敏捷开发：自适应开发、水晶方法、特征驱动开发、SCRUM、极限编程
基本原则：快速反馈、简单性假设、逐步修改、提倡更改、优质工作
12个最佳实践：计划游戏、小型发布、隐喻、简单设计、测试先行、重构、结对编程、集体代码所有制、持续集成、每周工作40小时、现场客户、编码标准
适合小型项目
10、多媒体标准：
MPEG-1：MP3，VCD
MPEG-2：DVD
MPEG-4、MPEG-7、MPEG-21
11、网络层次和主要设备的对应：
物理层传输层设备：中继器和集线器
数据链路层设备：网桥和交换机
网络层设备：路由器
应用层互联设备：网关
12、常用端口：
TCP端口：
FTP协议占用两个标准的端口号20和21，其中20为数据口，21为控制口。
Telnet服务的23端口；
SMTP服务的25端口；
HTTP服务的80端口；
HTTPS服务的443端口。
UDP端口：
DNS服务的53端口；
SNMP（简单网络管理协议）服务的161端口。
109端口是为POP2（Post Office Protocol Version 2，邮局协议2）服务开放的，
110端口是为POP3（邮件协议3）服务开放的，
POP2、POP3都是主要用于接收邮件的，目前POP3使用的比较多。
13、顺序存储、链式存储
线性表按顺序存储 插入新元素需要移动元素N/2 ,删除元素需要移动元素(N-1)/2
线性表按链式存储 删除不需要移动元素
14、分布式数据库的透明：
分片透明是指用户或应用程序不需要知道逻辑上访问的表具体是怎么分块存储的。
复制透明是指采用复制技术的分布方法，用户不需要知道数据是复制到哪些节点，如何复制的。
位置透明是指用户无须知道数据存放的物理位置。
逻辑透明，即局部数据模型透明，是指用户或应用程序无须知道局部场地使用的是哪种数据模型 。
15、沟通路径
若任意小组成员之间均可能有沟通路径，则可用完全连通图来对开发小组的沟通路径建模，最多的沟通路径为完全连通图的边数，即n个成员的开发小组的沟通路径是n（n-1）/2。
16、流水线技术所需时间为：
一条指令的完整时间+(指令执行次数-1)最长分段时间
取指5t、分析2t、执行3t，执行完500次需要(5+2+3)+(500-1)5=2505
17、数字签名、数字证书、数字信封
数字信封：发送方将原文用对称密钥加密传输，而将对称密钥用接收方公钥加密发送给对方。接收方收到电子信封，用自己的私钥解密信封。取出对称密钥解密得原文。
数字证书由CA签发给用户，CA保证它的安全和可靠性，使用CA的私钥对证书进行签名，使用CA的公钥验证签名的合法有效性。
数字签名技术是将摘要信息用发送者的私钥加密，与原文一起传送给接收者。接收者只有用发送者的公钥才能解密被加密的摘要信息，然后用HASH函数对收到的原文产生一个摘要信息，与解密的摘要信息对比。如果相同，则说明收到的信息是完整的，在传输过程中没有被修改，否则说明信息被修改过，因此数字签名能够验证信息的完整性。数字签名是个加密的过程，数字签名验证是个解密的过程。保证信息传输的完整性、发送者的身份认证、防止交易中的抵赖发生。
例题：要求邮件以加密方式传输，邮件最大附件内容可达500mb。发送者不可抵赖，若邮件被第三方截获第三方无法篡改。
发送者不可抵赖：数字签名
第三方无法篡改：信息摘要技术
邮件正文适合使用对称加密（随机密钥K）。用接收方的公钥加密随机密钥K，接收方收到后用接收方的私钥解密后获得随机密钥K。（数字信封技术）；对正文形成摘要，使用发送方的私钥对摘要数字签名得到摘要的密文，接收方使用发送方的公钥对密文进行解密得到解密后正文的摘要。把对称解密得到的邮件正文形成的摘要和解密后的摘要进行对比，确保一致后达到第三方无法篡改。
18、能力成熟度模型(CMMI)
CLO（未完成的）：过程域未执行或未得到CL1中定义的所有目标。
CL1（已执行的）：其共性目标是过程将可标识的输入工作产品转换成可标识的输出工作产品，以实现支持过程域的特定目标。
CL2（已管理的）：其共性目标是集中于已管理的过程的制度化。根据组织级政策规定过程的运作将使用哪个过程，项目遵循已文档化的计划和过程描述，所有正在工作的人都有权使用足够的资源，所有工作任务和工作产品都被监控、控制、和评审。
CL3（已定义级的）：其共性目标集中于已定义的过程的制度化。过程是按照组织的裁剪指南从组织的标准过程中裁剪得到的，还必须收集过程资产和过程的度量，并用于将来对过程的改进。
CL4（定量管理的）：其共性目标集中于可定量管理的过程的制度化。使用测量和质量保证来控制和改进过程域，建立和使用关于质量和过程执行的质量目标作为管理准则。
CL5（优化的）：使用量化（统计学）手段改变和优化过程域，以满足客户的改变和持续改进计划中的过程域的功效。
19、软件的维护：
（1）改正性维护。为了识别和纠正软件错误，改正软件性能上的缺陷、排除实施中的错误使用，应当进行的诊断和改正错误的过程就称为改正性维护。
（2）适应性维护。在使用过程中，外部环境（新的硬、软件配置）、数据环境（数据库、数据格式、数据输入／输出方式、数据存储介质）可能发生变化。为使软件适应这种变化，而去修改软件的过程就称为适应性维护。
（3）完善性维护。在软件的使用过程中，用户往往会对软件提出新的功能与性能要求。为了满足这些要求，需要修改或再开发软件，以扩充软件功能、增强软件性能、改进加工效率、提高软件的可维护性。这种情况下进行的维护活动称为完善性维护。
（4）预防性维护。这是指预先提高软件的可维护性、可靠性等，为以后进一步改进软件打下良好基础。
20、数据库体系结构的三层模式：
视图-外模式，
存储文件-内模式，
基本表-模式。
21、软件维护工具辅助维护人员对软件代码及其文档进行各种维护活动。
主要包括：
版本控制工具
文档分析工具
开发信息库工具
逆向工程工具
再工程工具
配置管理支持工具
22、软件调试的常用方法：试探法、回溯法、归纳法、演绎法
（1）试探法。根据错误的特点，猜测问题的所在位置，利用在程序中设置输出语句，分析寄存器、存储器的内容等手段来获得错误的线索，一步步地试探和分析出错误所在。
（2）回溯法。从发现错误症状的位置开始，人工沿着程序的控制流程往回跟踪代码，直到找出错误根源为止。
（3）对分查找法。在该方法中，如果已经知道程序中的变量在若干位置的正确取值，可以在这些位置上给这些变量以正确值，观察程序运行输出结果，如果没有发现问题，则说明从赋予变量一个正确值到输出结果之间的程序没有错误，问题可能在除此之外的程序中。否则，错误就在所考察的这部分程序中，对含有错误的程序段再使用这种方法，直到把故障范围缩小到比较容易诊断为止。
（4）归纳法。从测试所暴露的问题出发，收集所有正确或不正确的数据，分析它们之间的关系，提出假想的错误原因，用这些数据来证明或反驳，从而查出错误所在。
（5）演绎法。根据测试结果，列出所有可能的错误原因。分析已有的数据，排除不可能和彼此矛盾的原因。对其余的原因，选择可能性最大的，利用已有的数据完善该假设，使假设更具体。用假设来解释所有的原始测试结果，如果能解释这一切，则假设得以证实，也就找出错误；否则，要么是假设不完备或不成立，要么有多个错误同时存在，需要重新分析，提出新的假设，直到发现错误为止。
23、质量特性、质量子特性：
功能性：
适合性
准确性
互用性
依从性
安全性
可靠性：
成熟性
容错性
易恢复性
易使用性：
易理解性
易学性
易操作性
效率：
时间特性
资源特性
可维护性：
易分析行
易改变性
稳定性
易测试性
可移植性：
适应性
易安装性
一致性
易替换性
24、设计原则
开-闭原则是指一个软件实体应当对扩展开放，对修改关闭，即在设计 一个模块的时候，应当使这个模块可以在不被修改的前提下被扩展。满足开-闭原则的系统具备更好的可复用性与可维护性。
里氏代换原则是指任何基类对象可以出现的地方，子类对象一定可以代替基类对象。
依赖倒转原则就是要依赖于抽象，而不依赖于实现，或者说要针对接口编程，不要针对实现编程。
25、存储和传递信息的实体，如手册、磁盘、光盘、磁带以及相关的播放设备等；二是指承载信息的载体，即信息的表现形式（或者说传播形式），如文字、声音、图像、动画和视频等，即CCITT定义的存储媒体和表示媒体。
媒体分为感觉媒体、传输媒体、表示媒体、表现媒体、存储媒体。
感觉媒体指直接作用于人的感觉器官，使人严生内接感觉的媒体， 如引起听觉反应的声音、引起视觉反应的图像等；
传输媒体指传输表示媒体的物理介质，如电缆、光缆。电磁波等；
表示媒体指传输感觉媒体的中介媒体，即用于数据交换的编码，如图像编码、文本编码和声音编码等；
表现媒体是指进行信息输入和输出的媒体，如键盘、鼠标、话筒，以及显示器、打印机、喇叭等；
存储媒体指用于存储表示媒体的物理介质，如硬盘、光盘等。
26、多态：
参数多态：应用广泛、最纯的多态。
包含多态：同样的操作可用于一个类型及其子类型。包含多态一般需要进行运行时的类型检查。
强制多态：编译程序通过语义操作，把操作对象的类型强行加以变换，以符合函数或操作符的要求。
过载多态：同一个名（操作符、函数名）在不同的上下文中有不同的类型。
27、模块之间的耦合有7种类型，根据耦合性从低到高为非直接耦合、数据耦合、标记耦合、控制耦合、外部耦合、公共耦合和内容耦合。
如果一个模块访问另一个模块时，彼此之间是通过数据参数（不是控制参数、公共数据结构或外部变量）来交换输入、输出信息的，则称这种耦合为数据耦合；
如果一组模块通过数据结构本身传递，则称这种耦合为标记耦合；
若一组模块都访问同一个公共数据环境，则它们之间的耦合就称为公共耦合；
若一个模块直接访问另一个模块的内部数据、一个模块不通过正常入口转到另一个模块内部、两个模块有一部分程序代码重叠或者一个模块有多个入口，上述几个情形之一发生则说明两个模块之间就发生了内容耦合。
28、内聚：
①偶然(巧合)内聚：指一个模块内的各个处理元素之间没有任何联系。
②逻辑内聚：指模块内执行几个逻辑上相似的功能，通过参数确定该模块完成哪一个功能。
③时间内聚：把需要同时执行的动作组合在一起形成的模块。
④通信内聚：指模块内所有处理元素都在同一个数据结构上操作，或者指各处理使用相同的输入数据或者产生相同的输出数据。
⑤顺序内聚：指一个模块中各个处理元素都密切相关于同一功能且必须顺序执行， 前一个功能元素的输出就是下一个功能元素的输入。
⑥功能内聚：是最强的内聚，指模块内所有元素共同完成一个功能，缺一不可。
29、软件许可一般由独占许可、独家许可、普通需求三种形式。
独占许可：软件著作权人不得将软件使用权授予第三方，自己不能使用该软件。
独家许可：软件著作权人不得将软件使用权授予第三方，自己可以使用该软件。
普通需求：软件著作权人可以将软件使用权授予第三方，自己可以使用该软件。
30、分治法
把一个问题拆分成多个小规模的相同子问题，一般可用递归解决。
步骤：划分-求解子问题-合并
常见求解问题：
排序：归并排序，快速排序
组合：棋牌覆盖，循环赛日程安排问题
几何：最近点对
31、动态规划法
划分子问题(最优子结构)，并把子问题结果使用数组存储，利用查询子问题结果构造最终问题结果。
特征：能够分解为互相重叠的若干子问题，满足最优性原理（最优子结构性质）该问题的最优解中也包含着其子问题的最优解。
步骤：分段-分析-求解
常见求解问题：
图问题：TSP，多短图最短路径
组合问题：0/1背包，最长公共子序列
查找问题：最优二叉查找树
32、贪心法
局部最优，但整体不见得最优。每步有明确的，既定的策略。
常见求解问题：
图问题：TSP，图着色，最小生成树
组合问题：背包，多机调度，活动安排
33、回溯法：系统的搜索一个问题的所有解或任一解。有试探和回退的过程。
常见求解问题：
图问题：图着色，哈密顿回路
组合问题：八皇后，批处理作业调度
33、设计模式：（有下划线表示可以是类模式也可以是对象模式，无下划线的表示只是对象模式）
创建型（用于创建对象）：工厂方法模式，抽象工厂模式，单例模式，原型模式，构建器模式
结构型（处理类和对象的组合问题）：适配器模式，桥接模式，组合模式，装饰模式，外观模式，享元模式，代理模式
行为型（描述类和对象交互、指责分配的问题）：职责链模式，命令模式，解释器模式，迭代器模式，中介者模式，备忘录模式，观察者模式，状态模式，策略模式，模板方法模式，访问者模式
34、从已知的一些函数依赖，可以推导出另外一些函数依赖，这就需要一系列推理规则。函数依赖的推理规则最早出现在1974年W.W.Armstrong的论文里，这些规则常被称作“Armstrong 公理”。
设U是关系模式R的属性集，F是R上成立的只涉及U中属性的函数依赖集。函数依赖的推理规则有以下三条：
自反律：若属性集Y包含于属性集X，属性集X包含于U，则X→Y在R上成立。（此处X→Y是平凡函数依赖）
增广律：若X→Y在R上成立，且属性集Z包含于属性集U，则XZ→YZ在R上成立。
传递律：若X→Y和Y→Z在R上成立，则X→Z在R上成立。
根据上面三条推理规则，又可推出下面三条推理规则：
合并规则：若X→Y，X→Z，则X→YZ为F所蕴含；
伪传递规则：若X→Y，WY→Z，则XW→Z为F所蕴含：
分解规则：若X→Y，Z=Y，则X→Z为F所蕴含。
35、PV操作：
互斥信号量的初值一般为1。
P通过。
①S减1；
②若S减1后仍大于或等于0，则进程继续执行；
③若S减1后小于0，则该进程被阻塞后放入等待该信号量的等待队列中，然后转进程调度。
V释放。
V操作的主要动作是：
①S加1；
②若相加后结果大于0，则进程继续执行；
③若相加后结果小于或等于0，则从该信号的等待队列中释放一个等待进程，然后再返回原进程继续执行或转进程调度。
36、排序方法及复杂度
37、关系代数：并、交、差、笛卡尔积、投影、选择、自然连接
笛卡尔积：结果列数为二者属性列数之和，行数为二者元素数乘积。
投影：对属性列的选择列出。
选择：对元组行的选择列出。
自然连接：列数为二者属性列数之和去掉重复列，行数为二者同名属性列其值相同的结果元组。
下午应用技术
1、找缺失数据流：
1、父图和子图的平衡
2、数据加工要既有输入流、又要有输出流
3、根据描述在对应文段中查找
ps：技巧-看题目分值估计缺失数据流数量
2、E-R图转关系模型
①1对1：1的主键加到1这边
厂长（姓名、年龄）、工厂（公厂号、厂名、姓名）
②1对：把1的主键加到这边
仓库（仓库号、仓库名）、商品（商品号、商品名、仓库号）
③对：把两边的主键加到联系中
学生（学号、姓名）、课程（课程号、课程名）、选修（学分、学号、课程号）
弱实体（病人-病人家属）：病人家属中加病人的主键（病人编号）
3、结构化语言 描述加工逻辑
条件语句
IF 条件 THEN
分支内容
ELSE IF 条件 THEN
分支内容
ELSE
分支内容
ENDIF
循环语句
WHILE 条件
DO
{
执行语句
}
ENDDO
4、包含<<include>>
指向被包含，必定存在
例如删除订单，必须要先查询订单
5、扩展<<extend>>
指向扩展项，可以不存在是扩充
例如去上课，可能迟到，迟到就是扩展
6、泛化<<generalization>>
一般和具体的关系，指向一般
7、类图：一般是三层，第一层是类名，第二层是属性，第三层是方法。
'+'：Public，公有的，能访问该类的类都能访问该属性
'-'：Private，私有的，只有该类能访问该属性
'#'：Protected，受保护的，该类及其继承类都能访问该属性
'~'：Package，包的，在同一个包中的类都能访问该属性
8、关联-多重度
A----------B ，数值写在线上且B附近
1：A和1个B关联
0..：A和0个或多个B关联
1..*：A和1个或多个B关联
0..1：A和0个或1个B关联
9、聚合
部分不依赖于整体，整体消失了部分仍然能存在。用空心菱形表示。（记忆：聚集的鸟群）
部分----------◇整体
10、组合
部分是依赖于整体，整体消失了部分就无法存活。用实心菱形表示。（人体组成部分）
部分----------◆整体
11、依赖
对应类A和类B来说，如果类A发生了变化会引起类B的变化，则称类B依赖于类A。用虚线和箭头表示。
A<-----------B 依赖----------->被依赖
12、泛化
一般和特殊的关系。用实现和空心三角形表示，指向一般。
子-----------▷父
13、Java简单语法
extends 继承
abstract抽象
抽象类不一定有抽象方法；有抽象方法的一定是抽象类
抽象类不能被实例化；抽象方法没有方法体
interface接口
implement实现
接口里的方法其实都是抽象方法，也就是没有方法体的，但是她不用写abstract关键字
实现一个接口就要实现接口里的所有方法
