软考笔记

计算机组成原理与体系结构

数据的表示

进制转换
符号数（原码反码补码移码）
原码

正数的原码等于自身的二进制数，负数的原码第一位为1(符号位，表示负数)，后面为自身的二进制数

反码

正数的反码等于自身的二进制数，负数的反码符号位不动，其余各位按位取反

补码

正数的补码等于自身的二进制数，负数的补码是在反码的基础上+1

移码(增码)

无论正负数，只要将其补码的符号位取反即可

符号数的应用
在计算机中，最适合数字加减运算的数字编码是补码，最适合表示浮点数阶码的数字编码是移码。
浮点数运算

对阶 ——尾数计算 —— 结果格式化

cpu

CPU结构（运算器与控制器的组成)
运算器、控制器、寄存器和内部总线，其中控制器不仅要保证程序的正确执行，而且要能够处理异常事件。
Flynn分类法简介
CISC(早期复杂)和RISC（简单）指令
流水线的基本概念

流水线是指在程序执行时多条指令重叠进行操作的一种准并行处理实现技
术。各种部件同时处理是针对不同指令而言的，它们可同时为多条指令的
不同部分进行工作，以提高各部件的利用率和指令的平均执行速度

流水线周期及流水线执行时间计算

流水线周期及流水线执行时间计算.

考试时优先为理论时间
k为多少部分例题中为k=3

流水线吞吐量的计算

流水线吞吐量的计算

流水线吞效率的计算

流水线吞吐量的计算

计算机组成与体系结构

层次化存储结构
CPU[寄存器] —Cache[按内容存取]—内存（主存）—外存（辅存）[硬盘，光盘，U盘]
Cache概念
局部性原理
时间局部性
时间局部性
工作集理论：工作集是进程运行时被频繁访问的的页面集合
存储器分类

RAM：随机存取存储器，可以随时读写（刷新时除外），而且速度很快，一旦断电所存储的数据将随之丢失。
ROM：只读存储器是一种只能读出事先所存数据的固态半导体存储器。不会因为电源关闭而消失。
存储器编址

-磁盘结构与参数

例题&讲解截图：

每个物理块旋转时间为 33/11=3ms
最差情况：第一个物理块存储时间等于旋转加处理时间等于 6ms，剩下的由于磁头过了对应的区块（一直转不能停）所以剩下的物理块每块存储时间为 33+3=36，总时间为36*10+6=336==366
优化分布后：每块都是刚刚好一处理完就刚刚好转到下一块：即 6 *11=66
计算机总线
内部总线（芯片与处理器），外部总线，控制总线（插件板与cpu接口）
控制总线（假设为32bit）分为：
数据总线（一个周期32bit数据）
地址总线（地址空间2的32次方即4g）
控制总线（发送控制信号）
串联与并联可靠性分析
串联： R=R1+R2+R3+…
并联：R=1-（1-R1）（1-R2）（1-R3）
失效率=1-R
串并联：先整体后局部

校验码

增大码子距离实现

循环校验码 CRC
通过异或计算（相同为0 不同为1 ）

校验码位数为除数位数-1

2^R = R+x+1 (R=校验位数 x信息位数)
第七位为信息位则 7 =2²⁺²1+2^0 则第七位分别与 r0,r1,r2,当计算有关位校验数时第七位的信息位参与其或以计算，校验所以有关信息位或以计算结果就是校验位的值。
重新计算信息位与效验码或异值为1 就是出现错误的位数

操作系统基本原理

###进程管理

进程状态

就绪状态是仅仅缺cpu 不缺其他资源
挂起到静止就绪是人为主动挂起
前趋图
用前趋图的形式表达一系列活动的先后约束关系
同步与互斥
互斥：同一时刻仅仅允许一个资源使用（共享）
同步：多个资源同时使用，速度有差异时，有速度匹配要求，差太多快的要等慢的（异步）
PV操作

pv操作解决并发进程之间某个约束问题（不就是进程锁嘛）

v（）开始阻塞 ++操作 s（）开始线程–操作

前趋图起点是 v（）箭头指向是p（v）

死锁：最小资源数=k（进程数）*（n-1）+1 【k：进程数 n 每个进程资源数】

-银行家算法
系统安全即不会发生死锁
银行家算法一个一个进程或者选项地推，走不通就是错误的；

存储管理

分区管理组织
首次适应法: 从上到下
最佳适应法：从小空间到大空间分配（缺点运行久后碎片多且小）
最差适应法：从大空间到小空间分配
循环首次适应法：首次适应法连成环一个一个依次分配
页式存储组织
掌握逻辑地址与物理地址的转换

练习题：

解题过程：页面大小：4k=2^12 即页内地址为12位，对应3个十六进制位。即题中的页内地址为题中的A29，页号为5
，通过查表5对应的物理地址即页帧号为6 所以完整物理地址为6A29H。不在内存无法淘汰，所以题中3，4无法淘汰，而且刚刚访问的无法淘汰，故，应该淘汰的页号为
0，2无法淘汰。答案为1.
段式存储组织

段式存储组织按照代码逻辑的方式划分内存（每段不一定大小一致），便于共享。
段页式存储组织
块表

快表：cache 慢表：内存
页面置换算法

抖动：分配更多资源却起反效果效率降低
计算题
索引文件结构

默认13个节点的结构
树形文件结构
空闲存储空间管理
空闲区表法：用一个表记录空闲区域
空闲链表：用链表记录空闲区域

坑点：位置是从0开始算

设备管理

数据传输控制方法
虚设备与SPOOLING技术

核心：开辟缓冲区，提高效率
微内核

数据库系统

数据库模式

三级模式两级映射
数据库设计过程
了解流程以及每个阶段的产出物
ER图

先局部后连整体
一对一联系最少2个
一对2联系最少2个
多对多最少3个（多对多的联系转成一个）
关系代数
并：合并并去重
交：公共部分
差：A-B 为去掉a里面a与b的公共部分

笛卡儿积：A*B A每一行与B每一行一一对应。
投影：某一列或行（有时是属性名有时是数字编码注意编号从1开始）
选择：带条件的筛选

连接：两个表某两个字段（默认是相同字段做等值）

规范化理论

函数依赖
规范化理论价值与用途
非规范化的关系模式，可能存在数据冗余，更新，插入，删除异常
键
超键与候选键的区别是：超键可能存在冗余属性
求候选键：

可以从这个没有其他节点指向的点（或组合点）遍历全部点
范式【必考】

1nf：没有每个键不可拆
2nf：每个非主属性完全依赖主键（把不依赖的独立出去）
3nf：非主键不依赖非主键
bc范式：依赖左边必须是候选键
范式越高数据拆分越细，影响性能效率
主属性：候选键的一部分
模式拆分

无损：可还原
是否无损的方法：
直接将可推的内容拉同一个表看是否与原表相同；
表格法：

集合法（只适合拆分成两份时适应）

并发控制

原子性：整个流程是整体不可分
一致性：内部守恒一致
隔离性：与外部隔离，事务直接互不影响
持续性：结果影响是持续性的

完整性约束

实体：例如非空
参照完整性：例如必须存在该部门或班级
对数据输入有一定约束，提高数据的可靠性

数据库安全

数据库备份与恢复

rollback语句命令实现回滚

数据仓库与数据挖掘

数据库：要效率速度
数据仓库：数据不改变，大规模查询分析

反规范号

规范化逆过程

大数据

计算机网络

七层模型

一二层为局域网，第三次开始拦截广播（广播只能在局域网）

###网络技术标准与协议

-DHCP

递归查询与迭代查询

网络类型与拓扑结构

网络规划与设计

分层设计

ip地址

html

无线网

接入技术

ipv6

信息安全

信息系统安全属性

对称加密与非对称加密

对称加密（加密解密用同一个密钥）

非对称加密（加密速度慢）

对称加密技术：

非对称加密技术（甲乙各有私钥公钥，且只能用对应私钥解密例如：甲公钥加密只能由甲私钥解密。给甲发数据就用甲公钥加密数据。）

信息摘要

数字签名

数字证书与PGP

练习题

各个网络层次的安全保障

网络威胁与攻击

防火墙

数据结构与算法

数组

稀疏矩阵

求公式时直接用代入法

线性表

队列与栈

广义表

二叉树

前中后续遍历
构造二叉树：先找根节点然后分左右然后左找根一步步递归下去
最优二叉树（哈夫曼树）
线段树
平衡二叉树

图

树与图的区别在于树没有环路

接邻矩阵
遍历
拓扑序列
最小生成树

普里奥算法：选一个点为红点集，剩下的为蓝点集，从蓝点集选一个最短的点连接最近的红点，并将该点纳入红点集，然后循环从蓝点集选一个距离红点集最短的点连接并纳入红点集如此反复循环，不许形成环路。

克鲁斯卡尔算法：直接选n-1条最短不成环的边相连
###算法

-查找问题

折半查找在查找成功时关键字的比较次数最多为[log2n」+1次
折半查找的时间复杂度为O(log2n）
排序
插入排序
希尔排序
直接插入排序
冒泡排序

-归并排序

-堆排序

建堆

排序
快速排序
基数排序