软考复习
计算机组成原理：
数据表示
最高位为符号位 0为正 -1为负
源码 直接二进制
反码 正数一样 负数：除符号位其他取反
补码 反码基础上+1
移码 首位进行取反
表示范围
源码 -(2^n-1 - 1) ~ 2^n-1 - 1
反码 -(2^n-1 - 1) ~ 2^n-1 -1
补码 -2^n-1 ~ x^n-1 -1
浮点数运算
对阶低阶-->高阶
尾数计算
结果格式化 确保小数点左边只有一位
CPU结构
主机+外设
运算器
1、算数逻辑单元 ALU
2、累加寄存器 AC
3、数据缓冲寄存器 DR
4、状态条件寄存器 PSW
控制器 指令相关
1、程序计数器PC
2、指令寄存器IR
3、指令译码器
4、时序部件
Flynn分类法
依据：指令流(单)多、数据流(单)多
单指令流+单数据流 一个控制 一个处理器 单处理器系统
单指令流+多数据流 一个控制 多个处理器 阵列处理机 异步处理同一个指令
多指令流+单数据流 多个控制 一个处理器 不可能情况
多指令流+多数据流 多个控制 多个处理器 多处理机系统、多计算机 作业、指令的全面并行
CISC & RISC
CISC前期产品、奢侈品级别
名称：复杂指令系统
指令：数量多，使用频率差别大、可变长格式
寻址：支持多种
实现：微程序控制技术(微码)
特点：研制周期长
RISC
名称：精简指令系统
指令：数量少、使用频率接近、定长格式、大部分为单周期指令，操作寄存器
寻址：支持少量
实现：增加了通用寄存器、硬布线逻辑控制为主、适合采用流水线
特点：优化编译、支持高级语言
流水线(计算方法)
取指 -->分析 --> 执行
流水线计算问题：
流水线周期为执行时间最长的那一段的时间
例：取值3 分析2 执行2==>周期=3
计算公式：
一条指令执行时间(取指+分析+执行)+(指令数-1)*流水线周期
流水线吞吐率计算： 吞吐率为规定时间内处理指令的条数
tp=流水线指令条数/流水线执行时间
流水线的加速比：
s=不使用流水线的时间/使用流水线的时间
流水线效率：
n个任务所占的时空区/总的时空区
计算机层次化存储结构
CPU寄存器
Cache按内容存取：不同内容不同区域，也叫相邻存储器
内存(主存)
外存(辅存)硬盘、光盘、U盘
CacheCPU和主存之间
计算平均周期时间： cache里有的就cache里，没有的就辅存里找
t1是Cache的周期时间 t2主存的周期
h命中率：能够获取到数据的概率
t3=t1*h + (1-h)*t2
局部性原理
时间局部性：
刚刚访问完的指令 再去访问
空间局部性：
立即访问临近空间
工作集理论：
被频繁访问的页面打包成一个集合
主存： 主存计算题
主存分类：
RAM：随机存储
ROM：只读
磁盘结构：
单缓存区：缓存区有处理时间
计算机总线(三种类型)
内部总线：芯片级别
系统总线：插件之间
数据：
32位：总线宽度32bit位 数据的宽度
地址：
32位==4G 只能管理4G的内存空间
控制：
发送控制信号的总线
外部总线
可靠性分析：
串联系统：
可靠虑：R=R1*R2*R3 ····· Rn
失效率：累加
并联系统：
可靠率：1-(1-R1)*(1-R2)* ···· (1-Rn)
考题：串并联合在一起 求可靠度
差错控制：
CRC：
根据生成多项式确定除数编码
在被除数编码后面添上(除数编码个数-1)个0
进行对2模运算 得到的余数替换刚刚换上去的0
·····
·····传输操作
最后对结果进习性对2模运算 如果余数为0 则说明没有错误
海明码：
2^n (n为整)都应该填入校验位 不能填入信息位
信息位有x位 校验位有r位
需要满足：
2^r>=x+r+1
校验位的数值 根据信息位数值所组成的多项式来决定
通过信息位多项式的数值做异或运算得到
操作系统：
进程管理
时间片轮转方法进行CPU资源的分配
进程状态：
运行
就绪：所有资源都配足 只缺CPU
等待：除了CPU还有其他资源没到位
转换关系：
前驱图：
进程的同步和互斥：
互斥：同一时刻，只能一个进程服务一个资源
同步：速度有查宜，速度快的等速度慢的
生产者消费者问题：
PV操作：
临界资源：进程间需要互斥方法对其进行共享的资源
临界区：访问临界资源的代码段
信号量：特殊的变量 如P(s) V(s)
PV操作
P操作相当于阻塞当前进程
V操作相当于激活进程
PV操作中有一个进程队列
PV操作例题
PV操作和前驱图结合：
每个圈圈都是一个进程
做题过程：
箭头上面标上相应的信号量，从左到右，从上到下
箭头源是V操作 箭头目的是P操作
进程的死锁问题：
死锁：如果系统在某一时刻发现 所有的资源都已分配 进程也无法完成并释放资源
题型一：至少多少个资源不会发生死锁：
给每个进程分配 (所需资源-1) 资源，然后最后再加一个 就是可以盘活资源的最少资源数
题型二：死锁的预防和避免
死锁的必要条件：(4)
1、资源互斥
2、保持和等待
3、不剥夺
4、环路等待
死锁的预防：
打破条件之一即可：
例：资源互斥：进行资源共享
死锁的避免：
1、有序的资源分配
2、银行家算法 ⭐⭐⭐⭐
找到可行的顺序
存储管理
分区存储组织：
首次适应算法：
从上到下 找到第一个合适的 切割使用
最佳适应：
把空间大小从小到大连起来 然后从小到大进行分配
最差适应：
把空间大小从小到大连起来 然后从大到小进行分配
将空闲块首尾相连
页面式存储组织：
特点：页的大小统统一致
优点：利用率高，碎片小，分配管理简单
缺点：系统开销大
题目：
1、先分辨出页号和页地址
2、通过页号得到物理块号(页帧号)
3、如果有需要淘汰的页 则需要找访问位为0的 即没有被近期访问的
页面淘汰算法图示
没有使用快表 说明需要先访问页号 再找到内存 因此有两次内存的访问 一共分配了六个页面 因此需要12次内存的访问
指令默认是一次性放入内存 因此只需要一次缺页中断 但是数据每一个占用了两个内存块 因此数据部分需要4次 总共就需要 (4+1)=5 次
段式存储：
特点：段的大小可以不均等
段页式存储；
页面置换算法：
最优算法：
随机算法；
先进先出：
最近最少使用：根据使用情况 刚刚被访问的页面 不会被淘汰
缺页：当前所调用的不在内存中就算缺页
文件管理
索引文件结构：
每间接一次 都翻了(物理盘块大小)/(地址字节数9)
一般都是13个节点
0~9 直接索引 地址直接对应物理盘块
10 一级间接索引
11 二级间接索引
13 三级间接索引
寻址试题;
树形目录结构：注意一下就好
绝对路径
相对路径：号码短 拨起来方便
空闲存储空间管理：
空闲区表法
空心啊链表法
位试图法 ⭐⭐⭐
成组链接法
作业管理⭐考的少
设备管理⭐考的少
数据传输方式：
程序控制方案
程序查询方式：CPU发出查询指令 进行状态的查看0=
-
程序中断
类似于程序控制：完成后会发一个中断
DMA：
DMA控制器监管 CPU只在开始结尾进行介入
虚设备和spooling技术：
spooling技术
解决原理：在磁盘上开了一个缓冲区
微内核操作系统：
可靠性、稳定性、安全性都不错
用户态
核心态
数据库系统:
三级模式，两级映射：
数据库设计：
需求分析 ==> 概念结构设设计 ==> 逻辑结构设计 ==> 物理设计
E-R模型
方框----试题
椭圆----属性
菱形----联系
E-R图的冲突：
属性冲突
命名冲突
结构冲突
关系代数：
并:将两个集合的内容并在一起 每个内容只显示一次
交 ：公共部分找出来 形成新的表
差 ：我有的 你没有
⭐注意：笛卡尔集中 有相同的也要写上 不可合并和省略
笛卡尔积 ：将所有数据列都列出来 每两条记录都做组合 拼接成为新的记录
投影 ：结果就是选出需要的列 Π
选择 ：就是根据条件 选出行
连接：相当于做等值连接 自然连接 相同的字段做等值操作
规范化理论：
部分依赖：主键中的一部分可以确定属性
主键：多个部分的组合键
价值和用途：
候选键：可以有多个候选键 即有多个可以唯一表示
超键：能够唯一表示元组的键 超键消除多余属性==候选键
主键：选一个候选键 就是主键
外键：别的表的主键
范式经典试题：
求解候选键：
图示法求候选键：
1、将关系模式化成图示 属性为节点 依赖关系作为箭头
2、找到入度为0的节点 尝试遍历图
⭐如果没有入度为0的 找既有出度又有入度的
3、若可以遍历所有节点 则为主键
范式：
1NF：属性值为不可分的原子值
2NF：消除非主属性 对 候选键 部分依赖
即每个非主属性完全依赖主键，不存在部分依赖
3NF：消除非主属性 对 候选键 传递依赖
BCNF：消除主属性 对 候选键 传递依赖
模式分解：
保持函数依赖：
拆分过后 该有的还有 冗余的除外
无损分解：
有损：不能还原
无损：可以还原
并发控制：
事务：
原子性：要么全做 要么全不做
一致性：操作前后状态一致
隔离性
持续性：影响是持续的
存在问题：
丢失更新
不可重复读
读"脏"数据 脏数据指不是真正需要的数据
封锁协议：
一级封锁协议：加入R锁 修改前必须加锁 可以防止丢失修改
二级封锁协议：加入S锁和R锁 防止丢失修改&脏数据
三级封锁协议：三种问题都可以修改
两段锁协议：可以串行
死锁问题：
1、避免
2、预防
完整性约束：⭐实质上就是保证数据的可靠性
实体完整性约束
约束的是主键 主键不可以为空 不可以重复
参照完整性约束
外键完整性约束 即填入的数据一定要和外表主键对应
用户字定义完整性:
用户自定义的约束
数据库安全：
用户标识和鉴定：身份认证问题最外层保护机制
存取控制
密码存取和传输
试图的保护
审计 日志对操作进行记录 随后进行分析
数据库备份和恢复：
冷备份(静态备份) 数据库关闭 停止运行的时候进行备份
热备份(动态备份) 正常运行的情况下进行备份操作
完全备份：全部备份
⭐差量备份：针对完全备份的数据的变化进行备份
⭐增量备份：针对上一次备份的数据变化进行备份
静态海量转储
静态增量转储
动态海量转储
动态增量转储
日志文件：
针对数据库改变所做的记录，可以记录针对数据库的任何操作，并且独立保存
故障与恢复：
本身故障 rollback语句
算术溢出、违反存储规则 撤销修改，回到最初状态
系统故障 检查点方式
外存破坏 日志重做业务
数据仓库和护具挖掘：
数据仓库：
面向主题
集成的
相对稳定的
反映历史变化
抽取数据 --> 数据仓库(数据集市) --> OLAP服务器(查询 发掘 分析 ····)
反规范化： 提高查询速度 以牺牲空间为代价
技术手段： 增加冗余
增加派生性冗余列
增加冗余列
重新组表
分割表
大数据概念：
即对海量数据进行处理的技术
计算机网络：
局域网只活动在统一网络层下 是接在同一路由器下的
OSI/RM 七层模型
物理层：二进制传输
中继器 ~= 烽火台
集线器：多端口中继器
数据链路层：帧传输
网桥、网卡、交换机
网络层：分组传输 & 路由选择
三层交换机、路由器
传输层：端到端连接
TCP协议
UDP协议
表示层：数据的格式与表达、加密、压缩
应用层：实现具体的应用功能
网络层次：
TCP/IP 协议族，重量级
网络层：
icmp
arp
rarp
传输层：
tcp
udp :
dhcp动态分配ip地址
dns 域名 <==> ip地址
采用递归查询 刨根问底，一直问道为止
迭代查询 不知道的服务器提供线索，让你问道知道的人
IPX/SPX协议：NOVELL，路由，大型企业网
NETBEUL协议：IBM，非路由，快速
无分类地址
计算机网络分类：
分布范围分：
局域网：活动在 OSI/RM 的下两层
城域网：城市之间
广域网：范围比较大了 就
英特网：全球吧
拓扑结构分：
总线型：
星形：办公室的网络拓扑结构 中心节点 往往是交换机
环型：
网络规划与设计：
三大原则：
实用性
开放性
先进性
分层设计：
核心层：数据交换
汇聚层：网络访问策略控制、数据包处理、过滤、寻址
接入层：向本地网段提供用户接入
IP地址与子网划分：
全零为网络地址
全一为广播地址
A类网络：
前 8 个为网络地址
后面为主机号 拥有2^24-2个主机位
B类网络：
前 16 位为网络地址
右面两端为主机号 拥有2^18-2个主机位
C类网络：
前 24 位为网络地址
最后一段位主机号 拥有2^6-2个主机位
子网划分：
172.18.129.0/24 前24位为网络号
子网掩码：区分 网络号 和 主机号
无分类编址：
见图片笔记
特殊含义的IP地址：
127网段：回播地址 如127.0.0.1连接到本机
网络号全0：当前子网中的主机
全1地址：本地子网的广播
主机号全1地址：特定子网的广播
内部地址 三个
169.254.0.0 DHCP失效使用(win) 操作系统分配的 实际并没有办法上网
0.0.0.0 DHCP失效使用(Linux)
无线网：
无线局域网 wlan wifi
无线城域网 wman WiMax
无线广域网 WWAN 3G/4G
无线个人网 wpan Bluetooth
IPV6：
特点特色：
长度为128位 地址空间扩大了2^96倍
考虑到了安全问题
三年中地址：
单播地址
任播地址 相当于就是广播地址
组播地址
信息系统安全属性：
保密性：最小授权原则、防暴露、信息加密、物理保密
完整性：安全协议、校验码、密码校验、数字签名、公证
可用性：综合保障
不可抵赖性：数字签名
对称加密和非堆成加密技术：
对称：加密速度快 速度高 但是加密强度不高 适合大数据量的
用什么加密就用什么解密 如war、word文件的加密解密
常见加密算法：
DES 56位密钥 64位
3DES 两个56位密钥 多搞几次就是三重DES
AES
RC-5
IDEA
非对成：
每个人会有自己的公钥(可以公开)，同时也会有自己的私钥(只能自己留着)
只有A的私钥才能解A的公钥
公钥加密 私钥解密
0
⭐摘要和数字签名一般结合来使用
信息摘要：相当于一段信息的特征值
算法：单项(摘要不能反向得到明文)hash函数 固定长度散列值
常用的信息摘要算法为MD5 SHA等
MD5 128位
SHA 160位
数字签名技术：不存在保密的职能 一般都是对摘要就行签名 不可抵赖的情况下用
用A的私钥加密 相当于就是A对该信息进行了一次签名
用A的公钥解密 相当于对数字签名进行了一次验证过程
数字信封与PGP
数字信封技术：
实际的内容使用对称传输的方式，再用非对称方式传输加密密钥
PGP：电子邮件 & 文件存储
数字证书：
个人的密钥和等等信息绑定起来 相当于一个身份证 必须要有持有者的公钥信息
可以通过验证签名的方法对数字证书进行判断 是否伪造
网络威胁和攻击：
重放攻击(ARP)：ARP欺骗攻击 所截获的某次合法的通信数据拷贝，处于非法的目的而被重新发送
拒绝服务攻击(DOS)：合法用户无法合理访问
窃听：用各种合法手段进行信息的窃听
业务流分析：长期监听含有对数据 分析的成分
信息泄露：被透露了
破坏完整性：对数据有了非法的增删改
假冒：通过欺骗通信系统达到非法用户冒充成合法用户
旁路控制：利用漏洞获取系统的特权
授权侵犯：内鬼作祟 也叫内部攻击
特洛伊木马：软件中藏有一个无害的程序段 当其被执行的时候就会破坏用户的安全
陷阱门：设置了某个机关，使得当提供特定的输入数据时允许违反安全策略
抵赖：否认自己所发布的消息，伪造来信
防火墙技术： 防外不防内
网络级：工作层次低 效率高
只是初步排查
包过滤
状态检测
应用级：工作层次搞 效率低
需要讲信息拆出来检查
双穴主机
频闭主机
屏蔽子网 ⭐这个才可能考
DMZ 中间区域 一般放对外服务器
数据结构：
广义表：递归形式定义的一种表
(a,(b,c),(d,e))
长度：即为：第一层的元素的个数
深度：包含括号的层数 或者说是嵌套的次数
两种操作：
head(取表头)
tail()取表尾 除了表头都是表尾
树与二叉树：
满二叉树：整棵树没有什么缺失的节点
完全二叉树：除了最下面 没有缺失 且需要从左往右排列排满
特性：
第i层最多有2^(i-1)个节点
深度为K的二叉树最多2^K-1个节点
叶子节点数为n0的化 n0=n2+1
如果对一颗有n个节点的完全二叉树的节点按层序编号(从上到下、从左到右)
1、如果i=1 则节点i没有父节点，是二叉树的根；若i>1，则父节点是i/2向下取整
2、若2i>n，则i为叶子节点，没有左子节点；否则，左子节点为2i
3、若2i+1>n，则i无右子节点；否则其右子节点为2i+1
反向构造二叉树 必须知道中序序列
树 转 二叉树
查找二叉树：不能出现值一样的
1、先和根节点比较 小的放左边 大的放右边
最优二叉树：
哈夫曼树：无损压缩的方式 不会有信息的损失
让一颗树的带权路径长度最短
线索二叉树：
平衡二叉树：查一下怎么平衡的
图的基本概念：
无向图
有向图
图的存储：
邻接矩阵
邻接表：记录距离和
图的遍历：
深度优先遍历
广度优先遍历
拓扑排序：
表达事件的先后执行
叫做AOV网络
图的最小生成树：边值加起来最小
普利姆算法：
从一个节点出发，一个个地进行纳入，纳入后成为一个整体，再找最小的，重复过程
克鲁斯卡尔：
找最短的边，拼成树
算法的特性：
有穷性：执行有穷步后结束
确定性：算法中每一条指令都有明确含义
I/O
有效性：例如ａ＝０ｂ／ａ就是无效的
查找：
顺序查找（ｎ＋１）／２
二分查找平均O（ｌｏｇ２ｎ）
最多（ｌｏｇ２ｎ）＋１向下取整
散列：
根据一定的规则在一张表里进行存储
使用ｋｅｙ关键码ｐ求余
有冲突的话，会有多种处理机制：
１、线性探测法：往后依次放进去
２、伪随机法：
堆排序：
大顶堆：
孩子节点比父节点大
小顶堆：
和大顶堆相对
归并排序：
将各个位的排序结果分别进行排序然后分别进行排序
各种排序时间空间复杂度
程序设计语言：（相当于编译原理）
编译过程：
词法分析－－＞语法分析－－＞
语义分析－－＞中间代码生成－－＞
代码优化－－＞目标代码生成－－＞目标程序
有限自动机：形象表示状态间的转换
双圈一般是结束
实质上就是看能不能找到一个从起点到终点的串
文法推导与正规式：
见图片笔记例题
计算机组成原理：
数据表示
最高位为符号位 0为正 -1为负
源码 直接二进制
反码 正数一样 负数：除符号位其他取反
补码 反码基础上+1
移码 首位进行取反
表示范围
源码 -(2^n-1 - 1) ~ 2^n-1 - 1
反码 -(2^n-1 - 1) ~ 2^n-1 -1
补码 -2^n-1 ~ x^n-1 -1
浮点数运算
对阶低阶-->高阶
尾数计算
结果格式化 确保小数点左边只有一位
CPU结构
主机+外设
运算器
1、算数逻辑单元 ALU
2、累加寄存器 AC
3、数据缓冲寄存器 DR
4、状态条件寄存器 PSW
控制器 指令相关
1、程序计数器PC
2、指令寄存器IR
3、指令译码器
4、时序部件
Flynn分类法
依据：指令流(单)多、数据流(单)多
单指令流+单数据流 一个控制 一个处理器 单处理器系统
单指令流+多数据流 一个控制 多个处理器 阵列处理机 异步处理同一个指令
多指令流+单数据流 多个控制 一个处理器 不可能情况
多指令流+多数据流 多个控制 多个处理器 多处理机系统、多计算机 作业、指令的全面并行
CISC & RISC
CISC前期产品、奢侈品级别
名称：复杂指令系统
指令：数量多，使用频率差别大、可变长格式
寻址：支持多种
实现：微程序控制技术(微码)
特点：研制周期长
RISC
名称：精简指令系统
指令：数量少、使用频率接近、定长格式、大部分为单周期指令，操作寄存器
寻址：支持少量
实现：增加了通用寄存器、硬布线逻辑控制为主、适合采用流水线
特点：优化编译、支持高级语言
流水线(计算方法)
取指 -->分析 --> 执行
流水线计算问题：
流水线周期为执行时间最长的那一段的时间
例：取值3 分析2 执行2==>周期=3
计算公式：
一条指令执行时间(取指+分析+执行)+(指令数-1)*流水线周期
流水线吞吐率计算： 吞吐率为规定时间内处理指令的条数
tp=流水线指令条数/流水线执行时间
流水线的加速比：
s=不使用流水线的时间/使用流水线的时间
流水线效率：
n个任务所占的时空区/总的时空区
计算机层次化存储结构
CPU寄存器
Cache按内容存取：不同内容不同区域，也叫相邻存储器
内存(主存)
外存(辅存)硬盘、光盘、U盘
CacheCPU和主存之间
计算平均周期时间： cache里有的就cache里，没有的就辅存里找
t1是Cache的周期时间 t2主存的周期
h命中率：能够获取到数据的概率
t3=t1*h + (1-h)*t2
局部性原理
时间局部性：
刚刚访问完的指令 再去访问
空间局部性：
立即访问临近空间
工作集理论：
被频繁访问的页面打包成一个集合
主存： 主存计算题
主存分类：
RAM：随机存储
ROM：只读
磁盘结构：
单缓存区：缓存区有处理时间
注意考试的题目(印象笔记)
计算机总线(三种类型)
内部总线：芯片级别
系统总线：插件之间
数据：
32位：总线宽度32bit位 数据的宽度
地址：
32位==4G 只能管理4G的内存空间
控制：
发送控制信号的总线
外部总线
可靠性分析：
串联系统：
可靠虑：R=R1*R2*R3 ····· Rn
失效率：累加
并联系统：
可靠率：1-(1-R1)*(1-R2)* ···· (1-Rn)
考题：串并联合在一起 求可靠度
差错控制：
CRC：
根据生成多项式确定除数编码
在被除数编码后面添上(除数编码个数-1)个0
进行对2模运算 得到的余数替换刚刚换上去的0
·····
·····传输操作
最后对结果进习性对2模运算 如果余数为0 则说明没有错误
海明码：
2^n (n为整)都应该填入校验位 不能填入信息位
信息位有x位 校验位有r位
需要满足：
2^r>=x+r+1
校验位的数值 根据信息位数值所组成的多项式来决定
通过信息位多项式的数值做异或运算得到
操作系统：
进程管理
时间片轮转方法进行CPU资源的分配
进程状态：
运行
就绪：所有资源都配足 只缺CPU
等待：除了CPU还有其他资源没到位
转换关系：(图片笔记)
前驱图：
进程的同步和互斥：
互斥：同一时刻，只能一个进程服务一个资源
同步：速度有查宜，速度快的等速度慢的
生产者消费者问题：
图片笔记
PV操作：
临界资源：进程间需要互斥方法对其进行共享的资源
临界区：访问临界资源的代码段
信号量：特殊的变量 如P(s) V(s)
PV操作 见图片笔记
P操作相当于阻塞当前进程
V操作相当于激活进程
PV操作中有一个进程队列
PV操作和前驱图结合：
每个圈圈都是一个进程
做题过程：
箭头上面标上相应的信号量，从左到右，从上到下
箭头源是V操作 箭头目的是P操作
(见图片笔记)
进程的死锁问题：
死锁：如果系统在某一时刻发现 所有的资源都已分配 进程也无法完成并释放资源
题型一：至少多少个资源不会发生死锁：
给每个进程分配 (所需资源-1) 资源，然后最后再加一个 就是可以盘活资源的最少资源数
题型二：死锁的预防和避免
死锁的必要条件：(4)
1、资源互斥
2、保持和等待
3、不剥夺
4、环路等待：(图片笔记：环路等待)
死锁的预防：
打破条件之一即可：
例：资源互斥：进行资源共享
死锁的避免：
1、有序的资源分配
2、银行家算法 ⭐⭐⭐⭐
找到可行的顺序
存储管理
分区存储组织：
首次适应算法：
从上到下 找到第一个合适的 切割使用
最佳适应：
把空间大小从小到大连起来 然后从小到大进行分配
最差适应：
把空间大小从小到大连起来 然后从大到小进行分配
将空闲块首尾相连
页面式存储组织：
特点：页的大小统统一致
优点：利用率高，碎片小，分配管理简单
缺点：系统开销大
题目：
1、先分辨出页号和页地址
2、通过页号得到物理块号(页帧号)
3、如果有需要淘汰的页 则需要找访问位为0的 即没有被近期访问的
段式存储：
特点：段的大小可以不均等
段页式存储；
页面置换算法：
最优算法：
随机算法；
先进先出：
最近最少使用：根据使用情况 刚刚被访问的页面 不会被淘汰
缺页：当前所调用的不在内存中就算缺页
文件管理
索引文件结构：
每间接一次 都翻了(物理盘块大小)/(地址字节数9)
一般都是13个节点
0~9 直接索引 地址直接对应物理盘块
10 一级间接索引
11 二级间接索引
13 三级间接索引
树形目录结构：注意一下就好
绝对路径
相对路径：号码短 拨起来方便
空闲存储空间管理：
空闲区表法
空心啊链表法
位试图法 ⭐⭐⭐
成组链接法
作业管理⭐考的少
设备管理⭐考的少
数据传输方式：
程序控制方案
程序查询方式：CPU发出查询指令 进行状态的查看
程序中断
类似于程序控制：完成后会发一个中断
DMA：
DMA控制器监管 CPU只在开始结尾进行介入
虚设备和spooling技术：
spooling技术 见图示
解决原理：在磁盘上开了一个缓冲区
微内核操作系统：
可靠性、稳定性、安全性都不错
用户态：
核心态：
数据库系统:
三级模式，两级映射：
见图片笔记
数据库设计：
需求分析 ==> 概念结构设设计 ==> 逻辑结构设计 ==> 物理设计
具体见图片笔记
E-R模型
方框----试题
椭圆----属性
菱形----联系
E-R图的冲突：
属性冲突
命名冲突
结构冲突
关系代数：
并:将两个集合的内容并在一起 每个内容只显示一次
交 ：公共部分找出来 形成新的表
差 ：我有的 你没有
⭐注意：笛卡尔集中 有相同的也要写上 不可合并和省略
笛卡尔积 ：将所有数据列都列出来 每两条记录都做组合 拼接成为新的记录
投影 ：结果就是选出需要的列 Π
选择 ：就是根据条件 选出行
连接：相当于做等值连接 自然连接 相同的字段做等值操作
规范化理论：
部分依赖：主键中的一部分可以确定属性
主键：多个部分的组合键
价值和用途：
候选键：可以有多个候选键 即有多个可以唯一表示
超键：能够唯一表示元组的键 超键消除多余属性==候选键
主键：选一个候选键 就是主键
外键：别的表的主键
求解候选键：
图示法求候选键：
1、将关系模式化成图示 属性为节点 依赖关系作为箭头
2、找到入度为0的节点 尝试遍历图
⭐如果没有入度为0的 找既有出度又有入度的
3、若可以遍历所有节点 则为主键
范式：
1NF：属性值为不可分的原子值
2NF：消除非主属性 对 候选键 部分依赖
即每个非主属性完全依赖主键，不存在部分依赖
3NF：消除非主属性 对 候选键 传递依赖
BCNF：消除主属性 对 候选键 传递依赖
模式分解：
保持函数依赖：
拆分过后 该有的还有 冗余的除外
无损分解：
有损：不能还原
无损：可以还原
并发控制：
事务：
原子性：要么全做 要么全不做
一致性：操作前后状态一致
隔离性
持续性：影响是持续的
存在问题：
丢失更新
不可重复读
读"脏"数据 脏数据指不是真正需要的数据
封锁协议：
一级封锁协议：加入R锁 修改前必须加锁 可以防止丢失修改
二级封锁协议：加入S锁和R锁 防止丢失修改&脏数据
三级封锁协议：三种问题都可以修改
两段锁协议：可以串行
死锁问题：
1、避免
2、预防
完整性约束：⭐实质上就是保证数据的可靠性
实体完整性约束
约束的是主键 主键不可以为空 不可以重复
参照完整性约束
外键完整性约束 即填入的数据一定要和外表主键对应
用户字定义完整性:
用户自定义的约束
数据库安全：
用户标识和鉴定：身份认证问题最外层保护机制
存取控制
密码存取和传输
试图的保护
审计 日志对操作进行记录 随后进行分析
数据库备份和恢复：
冷备份(静态备份) 数据库关闭 停止运行的时候进行备份
热备份(动态备份) 正常运行的情况下进行备份操作
完全备份：全部备份
⭐差量备份：针对完全备份的数据的变化进行备份
⭐增量备份：针对上一次备份的数据变化进行备份
静态海量转储
静态增量转储
动态海量转储
动态增量转储
日志文件：
针对数据库改变所做的记录，可以记录针对数据库的任何操作，并且独立保存
故障与恢复：
本身故障 rollback语句
算术溢出、违反存储规则 撤销修改，回到最初状态
系统故障 检查点方式
外存破坏 日志重做业务
数据仓库和护具挖掘：
数据仓库：
面向主题
集成的
相对稳定的
反映历史变化
抽取数据 --> 数据仓库(数据集市) --> OLAP服务器(查询 发掘 分析 ····)
反规范化： 提高查询速度 以牺牲空间为代价
技术手段： 增加冗余
增加派生性冗余列
增加冗余列
重新组表
分割表
大数据概念：
即对海量数据进行处理的技术
计算机网络：
局域网只活动在统一网络层下 是接在同一路由器下的
OSI/RM 七层模型
物理层：二进制传输
中继器 ~= 烽火台
集线器：多端口中继器
数据链路层：帧传输
网桥、网卡、交换机
网络层：分组传输 & 路由选择
三层交换机、路由器
传输层：端到端连接
TCP协议
UDP协议
表示层：数据的格式与表达、加密、压缩
应用层：实现具体的应用功能
TCP/IP 协议族，重量级
网络层：
icmp
arp
rarp
传输层：
tcp
udp :
dhcp动态分配ip地址
dns 域名 <==> ip地址
采用递归查询 刨根问底，一直问道为止
迭代查询 不知道的服务器提供线索，让你问道知道的人
IPX/SPX协议：NOVELL，路由，大型企业网
NETBEUL协议：IBM，非路由，快速
计算机网络分类：
分布范围分：
局域网：活动在 OSI/RM 的下两层
城域网：城市之间
广域网：范围比较大了 就
英特网：全球吧
拓扑结构分：
总线型：
星形：办公室的网络拓扑结构 中心节点 往往是交换机
环型：
网络规划与设计：
三大原则：
实用性
开放性
先进性
分层设计：
核心层：数据交换
汇聚层：网络访问策略控制、数据包处理、过滤、寻址
接入层：向本地网段提供用户接入
IP地址与子网划分：
全零为网络地址
全一为广播地址
A类网络：
前 8 个为网络地址
后面为主机号 拥有2^24-2个主机位
B类网络：
前 16 位为网络地址
右面两端为主机号 拥有2^18-2个主机位
C类网络：
前 24 位为网络地址
最后一段位主机号 拥有2^6-2个主机位
子网划分：
172.18.129.0/24 前24位为网络号
子网掩码：区分 网络号 和 主机号
无分类编址：
见图片笔记
特殊含义的IP地址：
127网段：回播地址 如127.0.0.1连接到本机
网络号全0：当前子网中的主机
全1地址：本地子网的广播
主机号全1地址：特定子网的广播
内部地址 三个
169.254.0.0 DHCP失效使用(win) 操作系统分配的 实际并没有办法上网
0.0.0.0 DHCP失效使用(Linux)
无线网：
无线局域网 wlan wifi
无线城域网 wman WiMax
无线广域网 WWAN 3G/4G
无线个人网 wpan Bluetooth
IPV6：
特点特色：
长度为128位 地址空间扩大了2^96倍
考虑到了安全问题
三年中地址：
单播地址
任播地址 相当于就是广播地址
组播地址
信息系统安全属性：
保密性：最小授权原则、防暴露、信息加密、物理保密
完整性：安全协议、校验码、密码校验、数字签名、公证
可用性：综合保障
不可抵赖性：数字签名
对称加密和非堆成加密技术：
对称：加密速度快 速度高 但是加密强度不高 适合大数据量的
用什么加密就用什么解密 如war、word文件的加密解密
常见加密算法：
DES 56位密钥 64位
3DES 两个56位密钥 多搞几次就是三重DES
AES
RC-5
IDEA
非对成：
每个人会有自己的公钥(可以公开)，同时也会有自己的私钥(只能自己留着)
只有A的私钥才能解A的公钥
公钥加密 私钥解密
0
⭐摘要和数字签名一般结合来使用
信息摘要：相当于一段信息的特征值
算法：单项(摘要不能反向得到明文)hash函数 固定长度散列值
常用的信息摘要算法为MD5 SHA等
MD5 128位
SHA 160位
数字签名技术：不存在保密的职能 一般都是对摘要就行签名 不可抵赖的情况下用
用A的私钥加密 相当于就是A对该信息进行了一次签名
用A的公钥解密 相当于对数字签名进行了一次验证过程
数字信封与PGP
数字信封技术：
实际的内容使用对称传输的方式，再用非对称方式传输加密密钥
PGP：电子邮件 & 文件存储
数字证书：
个人的密钥和等等信息绑定起来 相当于一个身份证 必须要有持有者的公钥信息
可以通过验证签名的方法对数字证书进行判断 是否伪造
网络威胁和攻击：
重放攻击(ARP)：ARP欺骗攻击 所截获的某次合法的通信数据拷贝，处于非法的目的而被重新发送
拒绝服务攻击(DOS)：合法用户无法合理访问
窃听：用各种合法手段进行信息的窃听
业务流分析：长期监听含有对数据 分析的成分
信息泄露：被透露了
破坏完整性：对数据有了非法的增删改
假冒：通过欺骗通信系统达到非法用户冒充成合法用户
旁路控制：利用漏洞获取系统的特权
授权侵犯：内鬼作祟 也叫内部攻击
特洛伊木马：软件中藏有一个无害的程序段 当其被执行的时候就会破坏用户的安全
陷阱门：设置了某个机关，使得当提供特定的输入数据时允许违反安全策略
抵赖：否认自己所发布的消息，伪造来信
防火墙技术： 防外不防内
网络级：工作层次低 效率高
只是初步排查
包过滤
状态检测
应用级：工作层次高 效率低
需要讲信息拆出来检查
双穴主机
频闭主机
屏蔽子网 ⭐这个才可能考
DMZ 中间区域 一般放对外服务器
数据结构：
广义表：递归形式定义的一种表
(a,(b,c),(d,e))
长度：即为：第一层的元素的个数
深度：包含括号的层数 或者说是嵌套的次数
两种操作：
head(取表头)
tail()取表尾 除了表头都是表尾
树与二叉树：
满二叉树：整棵树没有什么缺失的节点
完全二叉树：除了最下面 没有缺失 且需要从左往右排列排满
特性：
第i层最多有2^(i-1)个节点
深度为K的二叉树最多2^K-1个节点
叶子节点数为n0的化 n0=n2+1
如果对一颗有n个节点的完全二叉树的节点按层序编号(从上到下、从左到右)
1、如果i=1 则节点i没有父节点，是二叉树的根；若i>1，则父节点是i/2向下取整
2、若2i>n，则i为叶子节点，没有左子节点；否则，左子节点为2i
3、若2i+1>n，则i无右子节点；否则其右子节点为2i+1
反向构造二叉树 必须知道中序序列
树 转 二叉树
查找二叉树：不能出现值一样的
1、先和根节点比较 小的放左边 大的放右边
最优二叉树：
哈夫曼树：无损压缩的方式 不会有信息的损失
让一颗树的带权路径长度最短
线索二叉树：
平衡二叉树：查一下怎么平衡的
图的基本概念：
无向图
有向图
图的存储：
邻接矩阵
邻接表：记录距离和
图的遍历：
深度优先遍历
广度优先遍历
拓扑排序：
表达事件的先后执行
叫做AOV网络
图的最小生成树：边值加起来最小
普利姆算法：
从一个节点出发，一个个地进行纳入，纳入后成为一个整体，再找最小的，重复过程
克鲁斯卡尔：
找最短的边，拼成树
算法的特性：
有穷性：执行有穷步后结束
确定性：算法中每一条指令都有明确含义
I/O
有效性：例如ａ＝０ｂ／ａ就是无效的
查找：
顺序查找（ｎ＋１）／２
二分查找平均O（ｌｏｇ２ｎ）
最多（ｌｏｇ２ｎ）＋１向下取整
散列：
根据一定的规则在一张表里进行存储
使用ｋｅｙ关键码ｐ求余
有冲突的话，会有多种处理机制：
１、线性探测法：往后依次放进去
２、伪随机法：
堆排序：
大顶堆：
孩子节点比父节点大
小顶堆：
和大顶堆相对
归并排序：
将各个位的排序结果分别进行排序然后分别进行排序
程序设计语言：（相当于编译原理）
编译过程：
词法分析－－＞语法分析－－＞
语义分析－－＞中间代码生成－－＞
代码优化－－＞目标代码生成－－＞目标程序
有限自动机：形象表示状态间的转换
双圈一般是结束
实质上就是看能不能找到一个从起点到终点的串
文法推导与正规式： （1）：C （2）：C
有限自动机例题：AC
表达式：括号体现在执行这些操作的优先级问题上
前缀表达式
中缀表达式：正常顺序的表达式
后缀表达式
函数调用：
值传递
址传递：传的是指针类型的变量
各种语言的特点：
Fortran语言 科学计算
Pascal语言 为教学
Lisp 人工智能
Prolog 逻辑推理 数据库
法律法规：
⭐侵权判断 考的最多
保护期限：
署名权、修改权：没有限制，永久保护
发表权、使用权、获取报酬权：终身 || 死后50年，过了后就是全人类共有
注册商标：有效期 可以续注
发明专利权：
实用新型专利 & 外观设计专利：
知识产权人确定：看看一个作品完成后 是规个人所有还是公司所有
作品：除了署名权之外 其他都是单位所有
委托开发：所有放为开发者
合作开发：共同拥有著作权
商标：先申请 先有
专利：先申请 先拥有
侵权判定： ⭐考察频度比较高
中国公民、法人的作品无论发表(公之于众)与否 都有著作权
开发软件所用的思想、处理过程、操作方法及数学概念等 不受保护(著作权法不保护)
标准基础知识：
国际标准：ISO、IEC
国家标准：GB-中国 ANSI-没果 BS-英国 JIS-日本
行业标准：GJB-中国军用标准
多媒体基础：
音频相关概念：
声音带宽：次声波 20Hz ~ 20kHz 超声波
说话：300Hz ~ 3400Hz
乐器：20Hz ~ 20kHz
采样：
采样频率：越高效果越好 ⭐频率应为声音最高频率的2倍
采样精度：精度越高效果越好
图像相关概念：
亮度：画面明亮程度
色调
饱和度
彩色空间：
RGB
YUV(电视，兼容)
CMY(CMYK) 印刷领域
HSV(HSB) 从艺术欣赏的角度进行划分
媒体种类：
感觉媒体
表示媒体：文字、图形、图像、动画
显示媒体：输入设备，显示器等外设
存储媒体
传输媒体
多媒体计算问题：
图像容量计算：
计算题据例 注意：小写的"k"为1000 大写的"K"为1024 只有在存储的情况下才会用
常见多媒体标准：
JPEG 有损
JPEG-2000 有损&无损
MPEG-1 mp3 VCD
MPEG-2 aac Huffman DVD
MPEG-4 交互性、无线通信、网络应用/可视电话
MPEG-7 多媒体内容的描述接口
MPEG-21 融合不同的协议
数据压缩：
有损压缩：压缩之后还原不了 压缩比比较高 熵压缩法
无损压缩：压缩之后可以还原 压缩比比较小 熵编码法 Haffman
软件工程：
软件开发模型 适用于：需求明确、二次开发
快速原型：针对原型不明确的情况
螺旋模型：风险分析
V模型：测试的地位更加重要
喷泉模型：面向对象的
RAD：快速开发模型
CBSD：各个模块都变成标准的构建
敏捷开发方法：就是 简单 一般是小型项目
多扇入少扇出
McCabe复杂度：边的个数-节点个数+2
基本原则：有向边个数-节点数+2
维护类型：
改正性维护：已经出错了
适应性维护：还没有出错
完善性维护
预防性维护
软件过程改进--CMMI 能力成熟度模型
软件开发成熟度
0、混乱级 -->1、已管理级 -->2、项目管理级 -->3、已定义级 -->4、定量管理级(量化) -->5、持续优化
项目管理经典题目：
UML静态图和动态图 左静
两天根据自己需求总结了一小波 肯定不是广泛适用 但是感觉比没有强 hahahahaha
望大家好好复习 一发拿证！！
