软考
数据结构
Mccabe
流图G的环形复杂度V(G)=E-N+2，其中，E是流图中边的条数，N是结点数。
二叉树的分类
满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。
完全二叉树：一棵二叉树至多只有最下面的一层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。
平衡二叉树：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
最优二叉树：哈夫曼树
搜索
折半查找
一大一小再一大
优先队列
优先队列一般采用二叉堆数据结构实现，由于是二叉堆，所以插入和删除 一个元素的时间复杂度均为 O(lgn)。
AOV网进行拓扑排序
在aov网中选一个入度为0 度顶点输出它
从网中删除该点和有关的边
重复上述两个步骤 ，直到不存在入度为0的顶点为止
UML
UML 用关系把事物结合在一起，主要有下列四种关系:
(1)依赖(dependency)。依赖是两个事物之间的语义关系，其中一个事物发生变化会影响另一个事物 的语义。
(2)关联(association)。关联描述一组对象之间连接的结构关系。
(3)泛化(generalization)。泛化是一般化和特殊化的关系，描述特殊元素的对象可替换一般元素的对象。
(4)实现(realization)。实现是类之间的语义关系，其中的一个类指定了由另一个类保证执行的契约。
(5)组合。是一种特殊类型的关联，也表示类之间整体与部分的关系，但是组合关系中部分和整体具有统一的生存期，一旦整体对象不存在了，部分对象也将不存在。部分对象与整体对象之间有同生共死的关系。例如：桌子和桌面
(6)聚合。是一种特殊类型的关联，它描述了整体和部分间的结构关系。在一个聚合关系中，子类可以独立于父类生存。例如：车子与铃铛，铃铛可以独立于车子生存
软件工程
自顶向下集成
优点:较早地验证了主要控制和判断点;按深度优先可以首先实现和验证一个完整的软件功能;功能较 早证实，带来信心;只需一个驱动，减少驱动器开发的费用;支持故障隔离。 缺点:柱的开发量大;底层验证被推迟;底层组件测试不充分。 适应于产品控制结构比较清晰和稳定;高层接口变化较小;底层接口未定义或经常可能被修改;产口控 制组件具有较大的技术风险，需要尽早被验证;希望尽早能看到产品的系统功能行为。
自底向上集成
优点:对底层组件行为较早验证;工作最初可以并行集成，比自顶向下效率高;减少了桩的工作量;支 持故障隔离。缺点:驱动的开发工作量大;对高层的验证被推迟，设计上的错误不能被及时发现。 适应于底层接口比较稳定;高层接口变化比较频繁;底层组件较早被完成。
几个模型
瀑布模型：需求完整，不适合超大系统
螺旋模型：风险分析
喷泉模型：面向对象，以用户需求为动力
软件开发方法
1.结构化方法：面向数据流 数据处理 系统不复杂
2.jackson 面向数据结构
3.原型化 适用于反复修改 需求不清‘
4.面向对象
软件工程基本要素
方法 工具 过程
设计模式
结构型模式
适配器模式
是一个类对象结构型模式
将一个类的接口转换成客户希望的另外一个接口
桥接模式
对象结构型模式
将抽象部分与它的实现部分分离，使他们都可以独立地变化
组合模式
对象结构型模式
将对象组合成树形结构以表示“整体”-”部分“
行为型模式
visitor
多态accept（）方法
中介者模式
对象行为型模式
用一个中介对象来封装一系列的对象交互
创建型模式
建造者模式
对象创建型模式
将一个复杂对象的构建与其表示分离
编译原理
编译 和解释
解释性语言不包含目标代码生成阶段
递归下降分析法
自下而上
题目范围
数据结构 2
编译原理 2
设计模式 2-3
数据库 4
计算机网络
DHCP :自动分配IP地址
FTP
传输协议：tcp
计算机组成原理
海明码
（ 2^k ）- 1 >= n + k n为数据位 k为校验位
总线
系统总线包括：（ISA EISA MCA PCI）
数据总线，
地址总线，
控制总线
虚拟存储器
由主存辅存两级存储器组成
内存
内存中每个地址的存处单元是8bit
Cache与主存的地址映像由硬件自动完成
主存与Cache也是由硬件完成
存储器划分
按寻址方式：随机存储器，顺序存储器，直接存储器
按内容访问：相联存储器
中断
cpu是在一个总线周期结束时响应DMA请求的
中断向量可提供中断服务程序的入口地址
DMA工作方式下 主存与外设之间建立了直接的数据通路
数据库
数据库等三级模式结构
1.概念模式 /模式。基本表（只描述数据的逻辑结构和特征） desc
2.外模式 用户模式或子模式。视图，用户能看到的部分
3.内模式 存储模式 物理机构和存储方式。文件。
两级映像
模式/内模式映像
分布式数据库
透明性是指每一个数据库分布节点对用户的应用来说都是透明的，看不出是本地还是远程。
分片透明：用户或者应用程序只对全局关系进行操作而不必考虑数据的分片
复制透明：数据存在多个地方，用户不必关心，系统会自动完成
未知透明：用户不必知道所操作的数据放在何处
逻辑透明：用户不必关心DBMS DML
范式
1nf：每一个分量都是不可再分的（存在冗余 不一致性 插入和异常删除）
2nf：消除非主属性对对主属性的部分函数依赖
3nf：在2nf的基础上消除类非主属性对码的传递函数依赖
bcnf：在3nf基础上消除类主属性对码的部分和传递依赖
有损分解
如果r1交r2是r1或r2的超码， 则r上的分解是无损分解。
Armstrong公理系统
设关系模式R<U,F>，其中U为属性集，F是U上的一组函数依赖，那么有如下推理规则：
① A1自反律：若Y⊆X⊆U，则X→Y为F所蕴含；
② A2增广律：若X→Y为F所蕴含，且Z⊆U，则XZ→YZ为F所蕴含；
③ A3传递律：若X→Y，Y→Z为F所蕴含，则X→Z为F所蕴含。
根据上面三条推理规则，又可推出下面三条推理规则：
④ 合并规则：若X→Y，X→Z，则X→YZ为F所蕴含；
⑤ 伪传递规则：若X→Y，WY→Z，则XW→Z为F所蕴含；
⑥ 分解规则：若X→Y，Z⊆Y，则X→Z为F所蕴含。
网络安全
主动攻击
拒绝服务攻击 dos 分布式拒绝服务攻击ddos 信息篡改 资源使用 欺骗 伪装 重放
DMZ
DMZ是英文“demilitarized zone”的缩写，中文名称为“隔离区”，也称“非军事化区”。它是为了解决安装防火墙后外部网络的访问用户不能访问内部网络服务器的问题，而设立的一个非安全系统与安全系统之间的缓冲区。
应用于企业Web服务器、FTP服务器和论坛等
包过滤技术
基于网络层 传输层 简单易用 成本低。无法识别基于应用层的入侵
代理服务技术
基于应用层，安全性较高。 但是慢！
公开密钥理论
用CA的私钥对证书签名 公钥对证书验证
公开密钥加密算法 ecc dsa rsa
对称密钥加密算法 des
加密算法
idea算法和rc4算法都是对称加密算法 只能进行数据加密
md5算法事消息摘要算法，只能用来生产消息摘要 无法进行数字签名
rsa是非对称加密算法，有数字签名和验证的功能。
知识产权保护
署名权 修改权 保护作品完整权的保护期不受限制
软件工程
cocomo ii
层次结构 包括对象点 功能点和代码行
内聚
1） 偶然内聚：一个模块内的各处理元素之间没有任何联系，只是偶然地被凑到一起。这种模块也称为巧合内聚，内聚程度最低。
（2） 逻辑内聚：这种模块把几种相关的功能组合在一起， 每次被调用时，由传送给模块参数来确定该模块应完成哪一种功能 。
（3） 时间内聚：把需要同时执行的动作组合在一起形成的模块称为时间内聚模块。
（4） 过程内聚：构件或者操作的组合方式是，允许在调用前面的构件或操作之后，马上调用后面的构件或操作，即使两者之间没有数据进行传递。简单的说就是如果一个模块内的处理元素是相关的，而且必须以特定次序执行则称为过程内聚。
（5） 通信内聚：指模块内所有处理元素都在同一个数据结构上操作或所有处理功能都通过公用数据而发生关联（有时称之为信息内聚）。即指模块内各个组成部分都使用相同的数据数据或产生相同的数据结构。
（6） 顺序内聚：一个模块中各个处理元素和同一个功能密切相关，而且这些处理必须顺序执行，通常前一个处理元素的输出时后一个处理元素的输入。
例如某模块完成工业产值求值的功能，前一个功能元素求总产值，后一个功能元素求平均产值，显然该模块内两部分紧密关联。
顺序内聚的内聚度比较高，但缺点是不如功能内聚易于维护。
（7） 功能内聚：模块内所有元素的各个组成部分全部都为完成同一个功能而存在，共同完成一个单一的功能，模块已不可再分。即模块仅包括为完成某个功能所必须的所有成分，这些成分紧密联系、缺一不可。
功能内聚是最强的内聚，其优点是它的功能明确。判断一个模块是否功能内聚，一般从模块名称就能看出。如果模块名称只有一个动词和一个特定的目标（单数名词），一般来说就是功能内聚，如：“计算水费”、“计算产值”等模块。功能内聚一般出现在软件结构图的较低层次上。
功能内聚模块的一个重要特点是：他是一个“暗盒”，对于该模块的调用者来说，只需要知道这个模块能做什么，而不需要知道这个模块是如何做的。
计算机网络
静态路由子网掩码 255.255.255.0
默认路由子网掩码 0.0.0.0
主机路由子网掩码 255.255.255.255
