导图社区 软件设计师中级考点
- 66
- 0
- 1
- 举报
软件设计师中级考点
软件设计师中级考点，包含部分的例题。基本概括了常见的考点。背完这些再做些例题基本问题不大。内容实用，感兴趣的小伙伴可以收藏一下~
编辑于2024-10-22 16:31:07- 软考中级
- 软考知识点
- 软考考点
- 软件设计师中级考点
- 软件设计师中级知识点
- 制作竖屏
想要轻松掌握竖屏操作中的边框设置技巧吗？这篇指南将带你从基础到进阶，快速上手！首先，了解如何选中外框、填充颜色，并通过更多选项调整透明度。接下来，探索配色网站coolorsco，为你的设计找到完美配色。你还可以通过关系线或浮动主题添加外框，拖入悬浮主题，设置子主题样式。无论是调整外框大小、添加子主题，还是通过子主题添加外框，这篇指南都能帮你一一实现。一篇学会，轻松搞定竖屏中的边框设置！
- 软件设计师中级考点
软件设计师中级考点，包含部分的例题。基本概括了常见的考点。背完这些再做些例题基本问题不大。内容实用，感兴趣的小伙伴可以收藏一下~
- 边框制作
流行的四个顶点边框制作方法，指示了从创建浮动主题到设置主题形状、拷贝粘贴、创建多个主题以及最终添加连接线的完整流程。
软件设计师中级考点
社区模板帮助中心，点此进入>>
- 制作竖屏
想要轻松掌握竖屏操作中的边框设置技巧吗？这篇指南将带你从基础到进阶，快速上手！首先，了解如何选中外框、填充颜色，并通过更多选项调整透明度。接下来，探索配色网站coolorsco，为你的设计找到完美配色。你还可以通过关系线或浮动主题添加外框，拖入悬浮主题，设置子主题样式。无论是调整外框大小、添加子主题，还是通过子主题添加外框，这篇指南都能帮你一一实现。一篇学会，轻松搞定竖屏中的边框设置！
- 软件设计师中级考点
软件设计师中级考点，包含部分的例题。基本概括了常见的考点。背完这些再做些例题基本问题不大。内容实用，感兴趣的小伙伴可以收藏一下~
- 边框制作
流行的四个顶点边框制作方法，指示了从创建浮动主题到设置主题形状、拷贝粘贴、创建多个主题以及最终添加连接线的完整流程。
- 相似推荐
- 大纲
软件设计师中级
第1章 计算机系统知识
计算机系统基础知识
计算机系统硬件基本组成
运算器 控制器 存储器 输入设备 输出设备
中央处理单元
CPU的组成

运算器
算数逻辑单元ALU 状态条件寄存器PSW 累加寄存器AC 数据缓存寄存器DR
控制器
程序计数器 PC 指令寄存器 IR 指令译码器 ID 时序部件
寄存器组
分为专用寄存器和通用寄存器。运算器和控制器中的寄存器是专用寄存器，其作用是固定的。通用寄存器用途广泛并可由程序员规定其用途,其数目因处理器不同有所差异。
内部总线
数据表示
原码/反码/补码/移码
原码：符号位+数值位绝对值；0-整；1-负 反码：正数的反码和原码相同，负数-符号位不变，其他位是原码取反 补码：正数的补码和原码相同，负数-符号位不变，未位加1（反码+1），可以将减法运算转成加法运算 移码：将补码的符号位取反（不区分正负） 编码 10810（sbyte） -10810（sbyte） 原码 01101100 11101100 反码 01101100 10010011 补码 01101100 10010100 移码 11101100 00010100 注意：原码不是数值的二进制
定点数和浮点数
定点数
小数点位数不变的数
浮点数
这个表示的是二进制不是十进制，二进制也有小数 二进制1011.10101可以写成2^4 * 0.101110101可以可以写成2^5 * 0.0101110101
表示
浮点数的表示分规格化和非规格化，以十进制的理解 规格化：1.XX的就是规格化1.2 * 10^2 非规格化：0.XXX的就是非规格化 而且尾数必定是小数 所以N=R^e*M，R为基数，e为阶码，M为尾数 尾数⽤补码表⽰，阶码⽤移码表⽰ 尾数的位数决定数的有效精度，位数越多精度越⾼ 阶码的位数决定数的表⽰范围，位数越多范围越⼤
运算
对阶，将阶码小的向大的转化，尾数右移 计算尾数 格式化结果 1.2*10^2 + 0.1*10^3 0.12*10^3+ 0.1*10^3
例题
解析： 先计算尾数：尾数用原码表示为0000000001，是小数转十进制是0*2^-1 + 0*2^-2 + ...1*2^-10 = 1*2^-10。数符为0时正数，所以尾数部分就是1*2^-10 阶码是补码的0001 => 反码0000 => 原码1111 => 15,阶符是1位负数 => -15 所以是B 
进制的转换
十进制转二进制（短除法）
商为0时结束，然后从下往上写值 小数：乘2取整法 将小数部分乘以2。 取乘积的整数部分作为二进制的小数位。 将乘积的小数部分继续乘以2，重复上述步骤，直到小数部分为0或达到所需的精度。 十进制的0.5转换为二进制 0.1（二进制）=1×2^−1=0.5 将十进制的小数 0.625 转换为二进制 0.625 × 2 = 1.25 整数部分是 1，小数部分是 0.25，因此二进制小数位是 1。 0.25 × 2 = 0.5 整数部分是 0，小数部分是 0.5，因此二进制小数位是 0。 0.5 × 2 = 1.0 整数部分是 1，小数部分是 0，因此二进制小数位是 1。 把这些结果连接起来： 0.625 = 0.101_2 0.101_2里面的_2表示二进制 1024(十进制) = 100 0000 0000（二进制） 2^10 = 1024
二进制转十进制（按权展开法）
1011.01转二进制是： 1*2^3 + 0*2^2 + 1*2^1 + 1*2^0 + 0 * 2^-1 + 1 * 2^-2。
二进制转八（2^3）进制（取三合一法）
以小数点分割，向左向右取三个为一组，将每组二进制转成十进制，然后将结果按照组的顺序排在一起即可。 二进制：11001。八进制：31 11 001 11 -> 1*2^0 + 1 *2^1 = 1 + 2 = 3 001 -> 1 *2^0 + 0 * 2^1+ 0 * 2^2 = 1 + 0 + 0 = 1 按顺序排在一起：31 八进制转二级制 例如31，分别求十进制3和十进制1的二进制 1的二进制为1，补全三位001 3的二进制为11，补全三位011. 合并就是011001，去掉左侧0就是11001 十六进制一样
二进制转十六（2^4）进制（取四合一法）
十六进制
以H结尾的就是16进制
A-F代表10-15。加减和是十进制类似，只不过借1做16，满16进1
校验码
奇偶校验
通过在数据末尾添加一个校验位来确保数据的奇偶性，从而判断数据是否被正确传输
奇校验
确保数据中所有 1 的个数为奇数 如果原始数据中 1 的个数是偶数，则添加的校验位设为 1，这样所有 1 的个数变为奇数。 如果原始数据中 1 的个数已经是奇数，则添加的校验位设为 0，保持奇数个 1。 示例： 假设要传输 7 位数据 1101001： 该数据中有 4 个 1，是偶数个，所以需要添加一个 1 作为校验位，使得 1 的个数变为奇数。 传输的数据变为 11010011。
偶校验
确保数据中所有 1 的个数为偶数 如果原始数据中 1 的个数是奇数，则添加的校验位设为 1，这样所有 1 的个数变为偶数。 如果原始数据中 1 的个数已经是偶数，则添加的校验位设为 0，保持偶数个 1。 示例： 假设要传输 7 位数据 1101001： 该数据中有 4 个 1，是偶数个，所以添加的校验位为 0，保持偶数个 1。 传输的数据变为 11010010。
循环校验码 CRC
了解： CRC示例 假设我们有一个简单的二进制数据 1101，并且选择一个生成多项式为 x^3 + x + 1，对应的二进制形式为 1011（可以理解为2^3 + 2^1 + 2^0） 1. 数据扩展 我们将数据 1101 后面添加 3 个零（因为生成多项式的最高阶数是 3），得到扩展后的数据 1101000。 2. 多项式除法 使用生成多项式 1011 对扩展后的数据 1101000 进行二进制除法。最终得到的余数是 CRC 校验码（例如，假设余数为 011）。 3. 发送 将原始数据 1101 和校验码 011 一起发送，得到发送的数据 1101011。 4. 接收校验 接收方收到 1101011 后，再次用相同的生成多项式 1011 进行二进制除法。如果余数为 000，则说明数据无误；否则，说明数据有错误。
海明码校验
基本思想
在n个数据位之间加上k（check）个校验位。 n和k必须满⾜ 2^k - 1 ≥ n + k 的关系，通过扩⼤码距来实现检错和纠错。 n + k就是添加校验位以后得总位数
步骤，1011示例
确定数据位个数
共4位，n=4
确定校验位个数
根据2^k - 1 ≥ n + k得出 k = 3
确定校验位下标
校验位有3个，下标从0开始。如下所示校验位在第1，2,4位置上。下标位0,1,2 2^0 = 1 2^1 = 2 2^2 = 4 信息位就是3,5,6,7.
信息位数转化
将信息位所在位数转成如下形式 7=2^2+2^1+2^0 6=2^2+2^1 5=2^2+2^0 3=2^1+2^0
校验位值计算
第一个校验位的下标为0，那么找出转化后有2^0次方的信息位数，有7,5,3，其对应的值为1,1,1。进行半加运算 1 + 1 + 1 = 1 第二个校验位的下标为1，那么找出转化后有2^1次方的信息位数，有7,6,3，其对应的值为1,0,1。进行半加运算 1 + 0 + 1 = 0 第三个校验位的下标为2，那么找出转化后有2^2次方的信息位数，有7,6,5，其对应的值为1,0,1。进行半加运算 1 + 0 + 1 = 0 也就是传过来的正确的情况下应该是1010101 1+1=0 1+0=1（半加运算，不进位）
判断和纠错
正确的应该是1010101，将传过来的和正确的校验位取异或，如果为0则正确，为1这错误 正确：1010101 传的：1010111 第二位取异或的值为1，就是错误的。 纠正：取反就行。
计算机体系结构
计算机体系结构的发展
计算机体系分类
Flynn分类法
_指令（Include）_数据流(Data) S：single；M：Multiy 2 * 2组合四种方式 控制器：等于指令(数量) 处理器：等于数据流(数量) 主存：指令和数据流只要有一个是多个，个数就是多个
单指令单数据流SISD
单指令多数据流SIMD
并行处理机 阵列处理机、 超级向量处理机
多指令单数据流MISD
理论不存在 流水线计算机
多指令多数据流MIMD
指令系统
CISC与RISC
CISC复杂指令集计算机
（Complex Instruction Set Computer）/ˈkɒmpleks/ 指令：数量多、使用频率差别大、可变长格式 寻址方式：多寻址 实现方式：微程序控制技术（微码）
RISC精简指令计算机
（Reduced Instruction Set Computer）/rɪˈdjuːst/ 指令：数量少、使用频率接近、定长格式，大部分为单周期指令，操作寄存器。 寻址方式：支持方式少。 实现方式：增加了通用寄存器、硬布线控制逻辑为主、适用于流水线。
指令的流水处理
流⽔线相关概念
流⽔线
流⽔线是指在程序执⾏时多条指令重叠进⾏操作的⼀种准并⾏处理实现技术。 一个指令正常情况下是：取指 + 分析 + 执行，也有可能十多个 
流⽔线建⽴时间
取指时间 + 分析时间 + 执行时间 ps:1，2,3代表的是流水线 
流⽔线周期
取指、分析、执行三个中时间最长的。 过了建立时间后，单位时间内会同时执行取指、分析、执行。所以周期就是执行最长的一个
流⽔线相关计算
流⽔线执⾏时间
理论公式：(t1+t2+..+tk)+(n-1)*∆t流水线建立时间 + (总指令数量-1) * 周期 实践公式：k*∆t +(n-1)*∆t周期 * 3 + (总指令数量-1) * 周期
吞吐率：指令条数/执行的时间
最大吞吐率：1/∆t
流⽔线加速⽐：顺序执行时间/流水线执行时间
存储系统
分级存储体系
存储体系结构

局部性原理
程序在执⾏时呈现出局部性规律，即在⼀段时间内，整个程序的执⾏仅限于程序中的某⼀部分。相应地，执⾏所访问的存储空间也局限于某个内存区域
时间局部性
如果程序中的某条指令⼀旦执⾏，则不久之后该指令可能再次被执⾏
空间局部性
⼀旦程序访问了某个存储单元，则不久之后，其附近的存储单元也将被访问
存储器分类
按存储器位置
内存 外存
按材质
磁存储器 半导体存储器 光存储器
按工作方式
读/写存储器：RAM 只读存储器：ROM
按访问方式
按地址访问的存储器 按内容访问的存储器
按寻址方式
随机存储器 顺序存储器 直接存储器
高速缓存
作用
提高CPU对主存的访问效率，解决CPU和主存之间速度和容量不匹配问题 除寄存器外是访问最快的方式
特点
容量小 速度快 成本高
映像方式
直接相联映像
硬件电路较简单，但冲突率很高
全相联映像
电路难于设计和实现，只适用于小容量的 cache，冲突率较低
组相联映像
直接相联与全相联的折中
主存
硬盘是辅存
存储单元（字长）
存储单元编址是连续的，用进制表示的。 个数 = 最大地址下标+1-最小地址下标 64位操作系统就是字长为64bit 32位操作系统就是字长为32bit
编址内容（存储单元内容）
容量不固定，默认一个存储单元占1Byte（8bit） 64位操作系统就是字长为64bit，容量8字节 32位操作系统就是字长为32bit，容量4字节
按字编址
存储体的存储单元是字存储单元，即最小寻址单位是一个字
按字节编址
存储体的存储单元是字节存储单元，即最小寻址单位是一个字节
总容量
总容量 = 存储单元个数 * 编址内容  因为是按字节编址，所以一个字节就是一个存储单元。问题求容量 = 个数 * 一个存储单元容量 而存储单元的个数 = 最大地址下标+1-最小地址下标 所以个数 = CFFFFFH + 1 - A0000H = D0000H - A0000H = 30000H。转十进制（按权展开法） = 3 * 16^4个 每个是1B所以共3 * 16^4B，转成KB 3 * 16^4 / 1024 = 192KB 第二空注意类型转化 192 * 1024 /（64 * 1024B） * 1B = 192 / 64 = 3
输入/输出技术

直接程序控制
指外设数据的输入/输出过程是在 CPU 执行程序的控制下完成的 降低CPU效率
无条件传送
在此情况下，外设总是准备好的，它可以无条件地随时接收CPU发来的输出数据，也能够无条件地随时向 CPU 提供需要输入的数据
程序查询方式
在这种方式下，利用查询方式进行输入/输出，就是通过 CPU执行程序来查询外设的状态判断外设是否准备好接收数据或准备好了向CPU输入的数据。根据这种状态，CPU有针对性地为外设的输入/输出服务。
中断方式
CPU不参与
直接存储器存取方式
直接内存存取(DirectMemory Access，DMA)是指数据在内存与I/0设备间的直接成块传送，即在内存与 IO设备间传送一个数据块的过程中，不需要 CPU的任何干涉， 采用DMA传送数据，每传送一个数据都需要占用一个总线周期
总线结构
总线分类
系统总线：主存以及外设部件 PCI：并行内总线SCSI：并行外总线
数据总线
在 CPU 与 RAM 之间来回传送需要处理或是需要储存的数据
地址总线
用来指定在 RAM（Random Access Memory）之中储存的数据的地址。
控制总线
将微处理器控制单元（Control Unit）的信号，传送到周边设备，一般常见的为 USB Bus 和 1394 Bus。
安全性、可靠性与系统性能评测
计算机可靠性
可靠性表示
可靠性：MTTF/(1+MTTF) 可用性：MTBF/(1+MTBF) 可维护：1/(1+MTTR)
串联系统计算
R 总=R1 * R2; R：可靠性
并联系统计算
R 总=1-（1-R）^2
N 模混联系统
先将整个系统划分为多个部分串联 R1、R2…等，再计算 R1、R2 内部的并联可靠性，带入原公式
第2章 程序语言基础知识
程序设计语言的基本概念
编译程序和解释程序
解释程序(解释器)
直接解释执⾏源程序(程序不独⽴)，解释程序(控制权)和源程序都要参与到程序的运⾏过程，边解释边执⾏，执⾏效率较低
编译程序(编译器)
将源程序翻译成⽬标语⾔程序(独⽴程序)，源程序和编译程序都不再参与⽬标程序的执⾏过程，执⾏效率较⾼。
程序设计语言的分类
命令式程序设计语言
C语言
⾯向对象程序设计语⾔
C++
Java
Python
有if...else, for...else, while...else.没有switch...case 创建一个元组时逗号不能省略 列表[1,2]*2 = [1,2,1,2] Number、String、Tuple（元组）是不可变数据 解释型
函数式程序设计语⾔
Lisp
逻辑型程序设计语言
Prolog
程序设计语言的基本成分
函数
函数调用
传值调用：值的改变不会影响原变量的值 引用调用：值的改变会影响原变量的值
语言处理程序基础
编译过程
词法分析：是否存在非法字符 语法分析：if else等，是否缺分号 语义分析：是否存在死循环 
词法分析
检查单词拼写之类
语法分析
检查例如三目运算的语法对不对
语义分析
校验参数的类型是否匹配
中间代码生成阶段
中间代码有后缀式、三元式、四元式、树等形式
求后缀表达式
求10*(40-30/5)+20后缀表达式
已知树：后续遍历法
 左-右-跟 10 40 30 5 / - * 20 +
已知表达式：添加括号法
添加括号：((10*(40-(30/5)))+20) 将符号移动到同级括号的外面：((10(40(305)/)-)*20)+ 去掉括号：10 40 30 5 / - * 20 +
文法和有限自动机
⽂法
概念
描述语言语法结构的形式规则称为文法 V：非终结符：还可以继续分解，可以理解为占位符 T：终结符：是最终结果 S：起始符，语言的开始符号 P：产生式。推导式
⽂法的分类
0型：短语文法
1型：上下文有关文法
2型：上下文无关文法
3型：等价于正规式
语法推导树
可以有多种推导结果，只要有一种符合aabAa就行 
有限⾃动机
是一种识别装置的抽象概念，它能够正确的识别正规集 技巧：能不能识别00101，就是从左侧开始带入，能不能从初态走到终态 初态和终态的顺序和字符都是从左到右的
确定的有限自动机
不确定的有限自动机
正规式与有限自动机之间的转化
 
第3章 数据结构
线性结构
线性表
是n个元素的有限序列
顺序存储
 可以随机存取表中元素，缺点是插入和删除复杂
链式存储
用节点来存储数据元素 不能随机存取表中元素，优点是是插入和删除不需要移动元素
双向链表
 每个结点包含两个指针指向直接前驱结点和直接后继结点，可在两个方向上遍历链表
循环链表
 表尾节点的指针指向表中的第一个节点，可在任意位置开始遍历整个链表
静态链表
 特别引入一个头结点
复杂度

栈和队列
栈
先进后出的线性表 栈顶元素：是最后被压入栈的元素，也是最先被弹出的元素 栈底 
队列
先进先出的线性表 队尾 队头 
循环队列
注意队满的条件是取余 
解题技巧
 D：相成一个管子 按照⼀定顺序输⼊栈，那么出栈的可能有很多，因为进去的同时就⽴马出去
数组、矩阵和广义表
数组
一维数组
a：第一个元素的地址 i：数组下标 len：每个元素占的字节数（存储单元） 
二维数组
a[m][n]：m行n列 a[i][j]：i行j列，按行存储i行是满的一行n个所以有i * n个 + j 
矩阵

特殊矩阵

稀疏矩阵

结题方法：采用带入法
 A[0,0]存在M[1]，A[1,0]存在M[2] 将00,10带入公式 A
⼴义表
LS = (a, (b,c,), d)
⼴义表是n个表元素组成的有限序列，是线性表的推⼴，LS=(a0, a1,…, an)。 长度：最外层表(LS)含有多少个元素；3 深度：包含括号的重数；2 取表头head(LS)：最外层表的第⼀个元素；head(LS) = (a) 取表尾tail(LS)：除表头以外元素组成的表；tail(LS) = ((b,c)d)
例题
LS=(a,(b,c),(d,e))取出b怎么操作？ head(head(tail(LS)))
树
树的定义及基本运算
树
树是n(n>=0)个节点的有限集合，n=0是称为空树 节点的度：当前节点孩子节点的个数，②为2，③为1 叶子节点：度为0的节点 内部节点：除了根和叶子之外的节点 节点的层次：根为第1层，其他加一 树的高度（深度）：最大层次数 树的度：节点度最多的 
二叉树
二叉树
二叉树由一个根节点及两颗互不相交的、分别成为左子树和右子树的二叉树所组成 二叉树和树的区别 要明确区分左子树和右子树，即使几点只有一颗子树的情况下 二叉树节点最大的度为2，树不限制节点的度数
二叉树的性质
在⼆叉树的第i层上最多有2^ i-1个结点
深度为k的⼆叉树最多有2^k -1个结点
任意一颗二叉树中，叶子节点数n，度为2的结点数m，则n = m + 1
如果对⼀棵有n个结点的完全⼆叉树的结点按层序编号（从第1层到 L log2n ˩+1层，每层从左到右），则对任⼀结点i（1≤i≤n），有
满二叉树
叶子节点外，所有节点都有两个子节点 
完全二叉树
1.除最后一层节点外，其他层节点都必须要有两个子节点（其他符合满二叉树） 2.最后一层节点都要左排列 
非完全二叉树

平衡二叉树
树中任⼀结点的左右⼦树⾼度之差不超过1 平衡度：就是高度差。所以只能是-1/0/1 
非平衡二叉树
39左子树深度为3，右子树深度为0，差为3所以不是平衡二叉树 
二叉树的遍历
时间和空间复杂度都是O(n) 
前序遍历
根、左、右 先遍历根，然后遍历左子树，当遍历左子树时还要按照根左右的遍历，就像调用递归方法一样。 1 24578 36
中序遍历
左跟右 42785 1 36
后序遍历
左右跟 48752 63 1
层次遍历
从左到右 12345678
线索⼆叉树
对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化
前序线索二叉树
就是按照前序遍历的方式先得到结果ABDEHCFGI 线索就是将度为0的结点穿起来，D、H、F、I 然后根据上面的排序，可以看到D的两边是BE，依次类推 前驱为B（绿色虚线表示）。后继为E（红色虚线表示） 
中序线索二叉树

后序线索二叉树

排序⼆叉树
根节点和左右孩子节点上数值大小关系为 左

插入节点
若该键值节点已存在，则不用插入，如48 将要插入节点键值与插入后父节点键值比较，就能确认是左还是右节点
删除节点
叶子结点直接删除
删除的节点有一个子结点，则将这个子结点与待删除结点的父节点直接连接
如删除56，直接将51和48相连
删除有两个节点的时候，在其左子树上，用中序遍历寻找关键值最大的节点S，用S替代待删除节点，同时删除S，如89，用56代替89的位置，同时删除56时要满足上面的条件
最优⼆叉树-哈夫曼树

路径
树中一个节点到另一个节点之间的通路 路径长度：路径上分支数目
树的路径长度
树根到每个叶子节点的路径长度之和
节点带权路径长度
权 * 节点路径长度
树的带权路径长度（树的代价）
所有叶子节点带权路径相加 1×1 + 2×2 + 4×3 + 8×3=41
构建步骤
最小的放到左边（也可以是最大的）。 
找出两个最小的构建一个父节点
用①中父节点的值替换两个最小的
继续找两个最小的
如果构建的点不是最小的，如14，那么其他两个最小的应该从构建的这一层开始继续构建，也就是14所在的这一层
哈夫曼编码
通常 大的方左边。可以放右边 所有哈夫曼编码不是唯一的 
构建ABAACDC哈夫曼编码
1.统计权值
字母出现几次，权值就是几 A：3 B：1 C：2 D：1
2.对权值构建哈夫曼树
对1,1,2,3构建哈夫曼树（不是唯一的） 
3.转化编码
左树枝记0，右树枝记1 A：0 B：100 C：11 D：101
4.将转化的编码带入即可
例题
哈弗曼编码的构建过程是两个最小值相加的，所以节点要么有两个子结点，要么没有，依此判断。 
反向构建二叉树
前序：ABHFDECG 中序：HBEDFAGC 前序中可以知道A为跟，然后带入中序，依此类推 
树和森林
树的遍历
先根遍历（前序遍历） 后根遍历（后续遍历）
森林的遍历
前序遍历 后续遍历
树、森林和二叉树的转化

图
图的定义
无向图

有向图

完全图
完全无向图

完全有向图

存储结构
邻接矩阵表示法
具有对称性，存储时可以只存出其中⼀个三⾓，有边存1，无边存0； 有几个节点就是几乘几矩阵，从自己开始遍历 1到1 = 0 1 - 2 = 1 1 - 3 = 1 1 - 4 = 0 1 - 5 = 0 所以第一行就是0 1 1 0 0 依次类推 
邻接链表表示法
竖直方向：顶点⽤链表⽰出来， 水平方向：然后⽤⼀个⼀维数组来顺序存储上⾯每个链表的头指针· 
图的遍历

深度优先
访问最坐下一直向下
广度优先
按照层次从左到右
生成树和最小生成树
左边是图，右边是树 
生成树
生成树是给定无向连通图的一个子图 包含所有节点：生成树必须包含原图的所有顶点（节点） 无环且连通：生成树是一个无环图，并且所有节点都是连通的。它没有任何回路，但连接了图中的所有节点 生成树是一个将图的所有顶点都连接起来的树，并且它不包含任何环。如果一个图有 n 个顶点，那么它的生成树将有n-1条边
最小生成树
权值最小的生成树。 克鲁斯卡尔算法 - 贪心算法 有6个点，选6-1条最小的边。 重复的也算- 比如小的里面有两个4，在不形成闭环的条件下选两个4
拓扑排序和关键路径
AOV网
若用顶点表示活动，用有向边表示活动之间的优先关系，则称这样的有向图为以顶点表示活动的网，简称AOV网
拓扑排序极其算法
拓扑排序
选择一个入度为0的顶点且输出它 从网中删除该顶点以及与它有关的所有边 重复上述步骤，直到网中不存在入度为0的顶点 时间复杂度为O(n+e) 
逆拓扑排序
选择出度为0的点。其他和拓扑排序相同
查找
静态查找表
顺序查找
将待查找的关键字依次与表中元素进⾏⽐较，时间复杂度为O(n)
折半查找
⽐较次数最多为log2n +1 时间复杂度为 O(log2n)，
排序
简单排序
直接插⼊排序
从左到右找出有序的（降序，升序都可以） [12, 11, 13, 5, 6] 过程： 初始数组：[12, 11, 13, 5, 6] 从第二个元素（即索引 1）开始，将它插入到前面的有序部分。 步骤 1：插入第 2 个元素（11） 比较 11 和 12，发现 11 小于 12，所以将 12 向后移动，插入 11 在位置 0。 数组变为：[11, 12, 13, 5, 6] 步骤 2：插入第 3 个元素（13） 13 大于 12，所以无需移动，保持原位。 数组保持不变：[11, 12, 13, 5, 6] 步骤 3：插入第 4 个元素（5） 5 小于 13，将 13 向后移动。 5 小于 12，将 12 向后移动。 5 小于 11，将 11 向后移动。 将 5 插入到数组的第一个位置。 数组变为：[5, 11, 12, 13, 6] 步骤 4：插入第 5 个元素（6） 6 小于 13，将 13 向后移动。 6 小于 12，将 12 向后移动。 6 小于 11，将 11 向后移动。 将 6 插入到索引 1。 数组变为：[5, 6, 11, 12, 13] 最终排序结果：[5, 6, 11, 12, 13]
冒泡排序
5,8,16,32,7,25,30,50。从小到大排序 第一轮 指针到1，比较5和8的大小，位置不变：5,8,16,32,7,25,30,50 指针到2，比较8和16，位置不变：5,8,16,32,7,25,30,50 指针到3，比较16和32，位置不变：5,8,16,32,7,25,30,50 指针到4，比较32和7，交换位置：5,8,16,7,32,25,30,50 指针到5，比较32和25，交换位置：5,8,16,7,25,32,30,50 指针到6，比较32和30，交换位置：5,8,16,7,25,30,32,50 指针到7，比较32和50，位置布标：5,8,16,7,25,30,32,50 后续重复第一轮比较
简单选择排序
过程： 初始数组：[64, 25, 12, 22, 11] 每次从未排序的部分中找到最小的元素，然后将其与当前的未排序部分的第一个元素交换。 步骤 1：第一轮选择 未排序部分：[64, 25, 12, 22, 11] 找到最小元素 11，将它与第一个元素 64 交换。 数组变为：[11, 25, 12, 22, 64] 步骤 2：第二轮选择 未排序部分：[25, 12, 22, 64] 找到最小元素 12，将它与第一个元素 25 交换。 数组变为：[11, 12, 25, 22, 64] 步骤 3：第三轮选择 未排序部分：[25, 22, 64] 找到最小元素 22，将它与第一个元素 25 交换。 数组变为：[11, 12, 22, 25, 64] 步骤 4：第四轮选择 未排序部分：[25, 64] 最小元素是 25，不需要交换。 数组保持不变：[11, 12, 22, 25, 64] 步骤 5：第五轮选择 未排序部分：[64]，已是最后一个元素，不需要处理。 最终排序结果：[11, 12, 22, 25, 64] 只需要一次就能找到最小值
希尔排序
[23, 12, 1, 8, 34, 54, 2, 3] 步骤 1：选择增量 选择增量 gap = 4（数组长度的一半）。此时，我们将数组按步长 4 进行分组。每组中的元素分别是： 组1：[23, 34] 组2：[12, 54] 组3：[1, 2] 组4：[8, 3] 对每组进行插入排序： 组1：[23, 34]（已排序） 组2：[12, 54]（已排序） 组3：[1, 2]（已排序） 组4：[8, 3] -> [3, 8]（需要排序） 此时数组变为：[23, 12, 1, 3, 34, 54, 2, 8] 步骤 2：减小增量 选择增量 gap = 2，再次按步长 2 分组： 组1：[23, 1, 34, 2] 组2：[12, 3, 54, 8] 对每组进行插入排序： 组1：[23, 1, 34, 2] -> [1, 2, 23, 34] 组2：[12, 3, 54, 8] -> [3, 8, 12, 54] 此时数组变为：[1, 3, 2, 8, 23, 12, 34, 54] 步骤 3：再次减小增量 选择增量 gap = 1，对整个数组进行插入排序： 对数组 [1, 3, 2, 8, 23, 12, 34, 54] 进行插入排序： 插入 2 -> [1, 2, 3, 8, 23, 12, 34, 54] 插入 12 -> [1, 2, 3, 8, 12, 23, 34, 54] 数组已排序，无需进一步调整。 最终排序结果：[1, 2, 3, 8, 12, 23, 34, 54]
快速排序
25,8,16,32,7,5,30,50 选择基准元素一般选择最左侧，有两个指针左指针L，和有指针R。L指向5所在的位置，R指向50所在的位置 将25拿出作为基准元素，L指向空，R指向50 先从右侧指针开始R指向50，50大于25位置不动， R指针向左移动指向30,30大于25位置不动 继续移动R指针指向5，5小于25，将5移动到L指针位置（原来25的） 移动L指针（前面都是R指针）指向8,8小于25位置不动 L指针右移指向16,16小于25位置不动 L指针右移指向32,32大于25，将25移动到R指针位置（原5的位置） 依此类推 第一轮结果如子主题中的图所示 将25的左侧和右侧分别重复第一轮
堆排序
归并排序
[8, 3, 5, 4, 7, 1, 9, 6] 步骤 1：分解 首先将数组分为两部分：[8, 3, 5, 4] 和 [7, 1, 9, 6]。偶数个对半分，奇数个前面多一个 对每一部分继续分解，直到每个子数组只有一个元素： [8, 3] 和 [5, 4] -> [8], [3], [5], [4] [7, 1] 和 [9, 6] -> [7], [1], [9], [6] 步骤 2：合并（头部比较） 从最小的子数组开始，将它们两两合并： 合并 [8] 和 [3] -> [3, 8] 合并 [5] 和 [4] -> [4, 5] 合并 [7] 和 [1] -> [1, 7] 合并 [9] 和 [6] -> [6, 9] 继续合并这些有序的子数组： 合并 [3, 8] 和 [4, 5] -> [3, 4, 5, 8] 合并 [1, 7] 和 [6, 9] -> [1, 6, 7, 9] 最后合并两个有序数组： 合并 [3, 4, 5, 8] 和 [1, 6, 7, 9] -> [1, 3, 4, 5, 6, 7, 8, 9]
基数排序
[170, 45, 75, 90, 802, 24, 2, 66] 第一步：按个位数排序 对所有数字的个位进行排序，将它们按个位数分入对应的桶中。 0: [170, 90] 2: [802, 2] 4: [24] 5: [45, 75] 6: [66] 合并桶后得到的排序结果：[170, 90, 802, 2, 24, 45, 75, 66] 第二步：按十位数排序 对所有数字的十位进行排序，将它们按十位数分入对应的桶中。 0: [2] 2: [24] 4: [45] 6: [66] 7: [75, 170] 8: [802] 9: [90] 合并桶后得到的排序结果：[2, 24, 45, 66, 75, 170, 802, 90] 第三步：按百位数排序 对所有数字的百位进行排序，将它们按百位数分入对应的桶中。 0: [2, 24, 45, 66, 75, 90] 1: [170] 8: [802] 合并桶后得到的排序结果：[2, 24, 45, 66, 75, 90, 170, 802] 最终结果：[2, 24, 45, 66, 75, 90, 170, 802]
排序方法的比较
第4章 操作系统知识
进程管理
基本概念
前趋图
描述并行计算中任务之间的依赖关系。它是一个有向图，其中节点代表任务，边表示任务之间的依赖关系 m -> n：m是n的前趋，n是m的后继
进程的状态及转化
三态模型

五态模型

进程下的线程的栈数据不共享
进程间的通信
同步与互斥
互斥
多个进程因抢用同一时间只能被一个进程使用的资源时互斥。如使用打印机
同步
需要合作的进程。比如进程A负责把数据加载到缓冲区，进程B负责加工数据。那么A和B之间就是同步的关系。B要等待A完成才行
临界资源
有一些资源一次只能拱一个进程使用，这个资源称为临界资源。 打印机
临界区
进程中对临界资源实施操作的那段程序
信号量与PV操作
信号量
相当于每一个进程控制开关。注意初始值 信号量S的物理意义，S>=0，表示某资源的可用数；S<0，其绝对值表示阻塞队列中等待该资源的进程数
PV操作的作用
是实现进程同步与互斥的常用方法 P操作和V操作相当于是一个判断。如某个进程访问资源时先做P操作（信号量+1判断）
P操作
P操作，进入临界区时 执行S: = S - 1，当 S >=0：继续执行 S < 0：该进程为阻塞状态，并将其插入阻塞队列
V操作
V操作，离开临界区时 执行S: = S + 1当 S > 0：则执行V操作的进程继续执行， S <= 0：从阻塞状态唤醒一个进程，并将其插入就绪队列，执行V操作的进程继续执行 执行S操作后不管结果如何，该进程都继续执行。区别是否唤醒另一个进程
PV操作实现进程的互斥
互斥是对同一个信号量操作 信号量初始值为1 
PV操作实现进程的同步
消费者进程需要等待生产者进程，如何实现等待？ S2初值为0,所以消费者的P(S2)等于-1，小于0，所以会一直阻塞。直到生产者进程完成后执行V(S2)操作。 信号量初始值为1 
示例
 注意S1和S2的初始值为0，所以开始不能是P操作，否则一直阻塞
前趋图和PV操作
进程前面是等待P，后面是通知V  B C A
进程调度
进程调度算法
先来先服务 时间片轮转 优先级调度 多级反馈调度
死锁
死锁
进程管理是操作系统的核心，但如果设计不当，就会出现死锁的问题。如果一个进程在等待一件不可能发生的事，则进程就死锁了。而如果一个或多个进程产生死锁，就会造成系统死锁。
不死锁数量
就是每个线程需要的资源数-1 之和，然后在加一个资源，保证有一个是可以完成的，完成后就会释放资源，所以永远不会死锁。3 * 4 + 1 = 13 必然死锁： <= 最少需要资源数- 1；4 可能发生死锁。必然死锁和不死锁之前的资源数 4到12 
避免死锁
有序资源分配法
银行家算法
主要就是剩余资源数和需要资源数的比较 
存储管理
段页式存储
页式存储
页式存储
将程序和内存均划分为同样大小的快，以页为单位将程序调入内存。有一张页表记录用户程序在内存中的位置 逻辑地址和物理地址的页内地址相同
逻辑地址
页号 + 页内地址（页内偏移量）
物理地址
页帧号(物理块号) + 页内地址
优点：利用率高，碎片小，分配及管理简单
缺点：增加了系统开销，可能产生抖动现象
缺页中断
 缺页中断：页帧号为空就是不在内存中，当使用的时候需要淘汰其他页号。 淘汰原则（依据局部性原理） 修改位为0的 访问位为0的
例题
 物理地址是？ 页为4KB也就是4*1024=4096字节 要表示4096个字节需要12位（2^12）二级制表示 所以逻辑地址的14位中有12位是页内地址，所以页号为10，转成十进制为3 根据页表页号3对应的块号是8，转成二进制为1000 所以物理地址是1000 1100 1101 1110
PS：容量和地址位数的关系

段式存储
逻辑地址：（段号，段内偏移）

判断逻辑：偏移量不能大于段长
例题
 B
磁盘管理
设备管理
设备管理软件分层

磁盘调度
磁盘结构

读取时间
找磁道时间
找扇区时间，即旋转时间
传输时间
例题
 (10 * 10 + 100 + 2) * 100 D
磁盘寻道方式
先来先服务(FCFS)
最短寻道时间优先(SSTF)
执行完第一个后，找距离第一个磁道最近的
扫描算法(SCAN)-电梯算法 双向
循环扫描(CSCAN)算法 单向
当磁头到达一端（例如最外侧）后，磁头直接返回到另一端（最内侧），不处理中途的请求。然后从头开始扫描新的请求。这类似于循环的方式。 从1楼到顶楼后直接回到1楼
例题
单双缓冲区
D，C  知识点：必须等缓冲区中的数据传送完才能再次输入。 单缓冲区 因为单缓冲区特性就相当于把输入和传送看成一个整体叫读取，共20微妙 读取和处理可以当做流水线来处理 改流水线的建立时间时21微妙，周期20，所以时间是21 + （20 * 9）= 201 双缓冲区  如上图所示，建立时间时21微妙，周期15，所以 21 + （15 * 9） = 156
寻道方式

顺序读取磁道物理块信息
 C，B 旋转周期为33ms，共11块，所以每块读取时间为3ms，后面可知处理时间为3ms，所以每块的处理时间为3=3=6 因为是单缓冲区，所以当R0处理完后，下标已经到了R1的右侧了，必须转一圈到R1的左侧， 所以 R0的时间为每块处理时间：6 R1的时间为旋转时间+每块处理时间：（3*10）+ 6= 36 R1和R10的处理时间都是一样的共36 * 10 = 360 所以共366 优化的逻辑就是第一个处理完后磁头刚好在R1处（不需要旋转了），所以最优时间为6*11 = 66
文件管理
文件的结构和组织
索引文件
示意图
 根据物理块大小(假设 1KB)和地址项长度(假设 4B)，可以计算存放间接索引的物理块可以存放的地址项个数:物理块大小V/地址项长度，向下取整(1KB/3B=256，注意单位和进制转换)。 直接索引的时候，指向的物理盘块存放的是文件 间接索引的时候，指向的物理盘快存放的是地址项
分类
直接索引
直接索引(即索引结点直接指向实际存储文件的物理块)，能够表示的逻辑页号范围是 0~9，能够表示的文件大小时 10*1KB。
一级间接索引
一级间接索引(即索引结点指向的物理块存放的是地址项，对应地址项个数 256 个，可以指向 256个实际存储文件的物理块)，能够表示的逻辑页号范围是 10~265，能够表示的文件大小是 256*1KB.
二级间接索引
二级间接索引(即索引结点指向的物理块存放的是间接索引的地址项，共 256 个，可以指向 256个存放地址项的物理块，每个物理块指向实际存储文件的地址项有 256 个，最终指向的物理块共有
三级间接索引
以此类推
文件目录
绝对路径与相对路径
绝对路径：从根目录/开始 相对路径：从当前目录开始（当前目录不写出，不带/） 全文件名：绝对路径+文件名称 
存取方法和存取空间的管理
位示图
概念
用位（bit）的形式记录磁盘块（物理块）的使用情况，表示哪些磁盘块是已分配的，哪些是空闲的。 位示图是一个位数组，每个位代表磁盘上的一个块： 0 表示该块是空闲的，可以被分配。 1 表示该块已被占用。 例如，如果某个磁盘有 8 个块，并且位示图是 10101000，那么表示： 第 1、3、5 个磁盘块已经被占用。 第 2、4、6、7、8 个磁盘块是空闲的
存储
按字存储 例如： 在一个 64 位的系统中，每 64 位会组成一个字，位示图的大小通常用字来表示。 比如位示图为2字，就是有2字长
字长
计算机处理器一次能够处理的二进制数据的位数，通常是32位或64位
例题
 计算物理块总量：521GB/4MB = 128*1024个 所以位示图共：128*1024位 而一个字是64位，所以共128*1024/64 = 2048个字 一个字长是64位所以共需128*1024/64
第5章 软件工程基础知识
软件工程概述
软件生存周期
可行性分析
需求分析
功能需求
性能需求
设计约束
概要（大概）设计
设计软件系统总体结构
数据结构及数据库设计
编写概要设计文档
评审
详细设计
数据结构设计 算法设计 数据库的物理设计
程序编码
软件测试
维护
软件过程
软件能⼒成熟度模型
统⼀过程（UP、RUP）
初启阶段：项⽬的初创活动，⾥程碑是⽣命周期⽬标 精化阶段：需求分析和框架演进，⾥程碑是⽣命周期架构 构建阶段：系统的构建，产⽣实现模型，⾥程碑是初始运作功能 移交阶段：将产品发布给⽤户进⾏测试评价，并收集⽤户的意见，产⽣软件增量，⾥程碑是产品发布
软件开发模型
瀑布模型
阶段明确，包括需求分析、设计、编码、运⾏与维护。⼀旦需求变，整个项⽬推倒重新开始。适⽤于需求明确或⼆次 开发的项⽬ 结构化模型 适用需求明确、二次开发 无法灵活应对需求变化，容易导致项目失败 
增量模型
结合了瀑布模型和原型模型，在完成核⼼功能的基础上，每轮迭代会都会产⽣新的增量来强化核⼼功能 
演化模型
原型：适⽤于需求不明确的场景 
螺旋模型
结合了瀑布模型和演化模型的优点，最主要的特点在于加⼊了风险分析 包括多个模型的特点。也适用需求不明确 特点：风险分析 
喷泉模型
面向对象的模型 迭代 ⽆间隙 支持软件重用
V模型
强调测试的模型，结构化的典型代表 
软件开发方法
结构化方法
原型方法
面向对象开发方法
敏捷方法
极限编程
四⼤价值观
沟通 简单 反馈 勇⽓
五⼤原则
快速反馈 简单性假设 逐步修改 提倡更改 优质⼯作
⼗⼆个最佳实践
计划游戏：快速制定计划、随着细节的不断变化⽽完善 ⼩型发布：系统的设计能够尽可能早的交付 隐喻：找到合适的⽐喻传达信息 简单设计：只处理当前的需求使设计保持简单 测试先⾏：先写测试代码在编程 重构：重新审视需求和设计，以符合新的和现有的需求 结队编程 集体代码所有制 持续集成：可以按日甚至小时为客户提供可运行的版本 每周工作40个小时 现场客户 编码标准
水晶法
强调经常交付，认为每⼀种不同的项⽬都需要⼀套不同的策略、约定和⽅法论
并列争球法
核⼼是迭代、增量交付，按照30天进⾏迭代开发交付可实际运⾏的软件
⾃适应软件开发
核⼼是三个⾮线性的，重迭的开发阶段：猜测、合作、学习
软件设计原则
⾼内聚、低耦合
内聚性
同一个类 一个模块应只负责一组相关的功能
偶然聚合
模块完成的动作之间没有任何关系
逻辑聚合
模块内部的各个组成在逻辑上具有相似的处理动作，但功能⽤途上彼此⽆关
时间聚合
模块内部的各个组成部分所包含的处理动作必须在同⼀时间内执⾏
过程聚合
模块内部各个组成部分所要完成的动作虽然没有关系，但必须按特定的次序执⾏
顺序聚合
模块内部的各个部分，前⼀部分处理动作的最后输出是后⼀部分处理动作的输⼊
通信聚合
模块的各个组成部分所使⽤同⼀个数据或产⽣同⼀输出数据
功能聚合
模块内部各个部分全部属于⼀个整体，并执⾏同⼀功能，且各部分对实现该功能都必不可少
耦合性
⾮直接耦合
两个模块之间没有直接关系，它们的联系完全是通过主模块的控制和调⽤来实现的
公共耦合
两个模块之间共享全局变量或者全局数据
外部耦合
依赖外部系统，如工具、库等
数据耦合
两个模块间有调用关系，传递简单数据
标记耦合
两个模块间有调用关系，传递数据结构，其实就是传数据结构的地址
控制耦合
两个模块彼此间传递的信息中有控制信息
内容耦合
⼀个模块需要涉及到另⼀个模块的内部信息
系统测试
测试策略和测试方法
软件测试策略
单元测试
也叫模块测试，在模块编写完成后就可以进行
集成测试
把各个模块组合起来测试
确认测试
检查功能和需求是否一致
系统测试
对系统整体的测试 恢复测试 安全性测试 强度测试 性能测试 可靠性测试 安装测试
测试方法
静态测试
程序不在机器上运行
人工检测
代码检查 静态结构分析 代码质量度量
计算机辅助静态分析
动态测试
通过运行程序发现错误
黑盒测试法
也叫功能测试，不知道内部结构
等价类划分
确定⽆效与有效等价类，设计⽤例尽可能多的覆盖有效类，设计⽤例只覆盖⼀个⽆效类
边界值分析
处理边界情况时最容易出错，选取的测试数据应该恰好等于、稍⼩于或稍⼤于边界值
错误推测
基于经验和直觉推测程序中所有可能存在的错误，然后针对测试
因果图
白盒测试法
结构测试
逻辑覆盖
语句覆盖
程序的每个语句(判断和赋值)⾄少执⾏⼀次， 每个判断至少执行一次 最弱的错误发现能力 x = 1即可以语句覆盖 if (x > 0) { y = 1; } else { y = -1; } z = 0;
判定覆盖
if中判断的表达式整体的结果必须true和false都有 每个语句⾄少执⾏⼀次，⽽且每个判定的真假分⽀都⾄少执⾏⼀次
条件覆盖
if中的表单式假如为A&&B，那么AB都要分别取指真假 if中每个条件独立地被测试到
条件/判定覆盖
同时满⾜判定覆盖和条件覆盖的逻辑覆盖
路径覆盖
选取⾜够多的测试⽤例，使得程序的每条可能执⾏到的路径都⾄少经过⼀次 并不是选取的用例能走完每条就行。而是要完整的路径，比如 ace和abd看似覆盖了所有的路径但是不是 ace还有acd，需要完整的每种可能 
循环覆盖
执行足够多的测试用例，使得循环中的每个条件都得到验证
基本路径测试
灰盒测试法
软件开发项目管理
成本估算
成本估算方法
自顶向下估算方法 自底向上估算方法 差别估算方法 专家估算方法 类推估算方法 算是估算方法
成本估算模型
Putnam模型 COCOMO模型
进度管理
Gantt图
⽢特图：能清晰的描述每个任务从何时开始、到何时结束以及各个任务之间的并行性，但是不能反应任务间的依赖关系，难以确定整个项目的关键所在 
PERT图
不能清晰的描述各个任务之间的并⾏关系 顶点表示项目里程碑 边表示活动 
关键路径
用时最长的时间、可以有多个，也是项目周期最快完成时间 关键路径上的节点有延迟，项目就会延迟
最早开始时间
从项目开始到该节点的最大的路径（要等该任务前的所有任务都完成才能开始，所以是前面任务用时最久的） FG的最早开始时间为10+ 8 = 18
最早完成时间
最早开始时间 + 持续时间
最晚开始时间
关键路径长度 - 终点到该点的最大值 比如G的最晚开始时间：G时间需要持续7天，而项目最快是38天，所以最迟也要38-7就开始，否则就会耽搁了。
最晚完成时间
最晚开始时间 + 持续时间
总时差(松弛时间)
最晚开始时间 - 最早开始时间 关键路径时差为0 会不会影响工期，就看松弛时间。 比如晚10天会不会影响工期，如果松弛时间时9天，会影响工期
示例
 最早开始时间 活动持续时间 最早完成时间 最晚开始时间 总时差 最晚完成时间 
风险管理
具有不确定性，可能会造成损失
风险分析
风险识别 风险预测 风险评估 风险控制
风险类别
项⽬风险 技术风险 商业风险：市场风险、策略凤险、管理风险和预算风险
软件度量
软件复杂性度量
McCabe复杂度量法
环路度量； V(G)=m-n+2p，其中m是有向边的条数，n是结点数，P是强连通分量的个数 闭环个数(循环个数)+1
⽂档知识
系统开发计划
总体规划和开发合同
测试计划
特点
针对性
精确性
完整性
灵活性
追溯性
第6章 结构化开发方法
结构化分析方法
数据流图
基本概念
概念

分层

数据字典

平衡原则
父与子的平衡
在顶层和 0 层放大的时候，看看有没有缺失，包括是否有数据流、以及方向
子图内的平衡
异常情况
黑洞

奇迹

输入和输出命名错误
第7章 ⾯向对象技术
基础知识
三⼤特征
封装
继承
多态
参数多态
重载
包含多态
一个类型是另一个类型的子类型
过载多态
同一个名字在不同的上下文中所代表的含义不同
两种绑定
静态绑定
在编译时，把过程调⽤和响应调⽤所需要执⾏的代码加以结合
动态绑定
在运⾏时，把过程调⽤和响应调⽤所需要执⾏的代码加以结合
设计原则
单⼀职责原则SRP
接⼝分离原则ISP
开放封闭原则OCP
⾥式替换原则LSP
依赖倒置原则DIP
组合重⽤原则
迪⽶特原则（最少知识法则）
面向对象开发技术
面向对象分析
认定对象
组织对象
描述对象间的相互作⽤
定义对象的操作
定义对象的内部信息
面向对象设计
面向对象测试
面向对象分析与设计
UML概述
统一建模语言是面向对象软件的标准化建模语言
关系
依赖：依赖是两个事物间的语义关系，其中一个事物（独立实物）发生变化会影响另一个事物（依赖事物）的语义 关联：关联是一种结构关系，它描述了一组链，链是对象之间的连接 聚合：是一种特殊类型的关联，描述了整体和部分间的结构关系 组合：是一种特殊类型的关联，描述了整体和部分间的结构关系，比聚合更强，也称为强聚合 泛化：是特殊到一般的关系，特殊可以替换一般 实现：接口之间的实现 第二个聚合是组合 
图
结构图
类图
展现一组对象、接口、协作及其之间的关系。给出了系统的静态设计视图 
用例图
系统与用户的交互关系，包含用例、参与者、扩展关系、包含关系、泛化关系。对系统的静态用例视图进行建模 
构件图
展现了一组构件之间的组织和依赖关系，专注系统的静态实现视图
部署图
展现了运行处理节点以及其中构件的配置，给出了系统的静态实施视图 
动态图
状态图
展现了一个状态机，它由状态、转换、事件和活动组成。关注系统的动态视图 
活动图
是一种特殊的状态图，展现了在系统内一个活动到另一个活动的流程，专注系统的动态视图 ⿊⾊粗线条代表并发 
交互图
顺序图（序列图）
是强调消息时间序列的交互图 同步消息 异步消息 返回消息 
协作图（通信图）
强调接受和发送消息的对象的结构的交互图 
设计模式（★★★★★）
创建型模式

结构型模式

⾏为型对象模式

第8章 算法设计与分析
算法设计与分析的基本概念
算法
是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。有以下5个重要特性 有穷性：不能无限执行下去 确定性：每条指令必须有确切的含义，理解不会产生二义性，并且在任何条件下，算法只有唯一的一条执行路径 可行性 输入 输出
算法设计
经常采用的算法设计技术主要有： 分治法 动态规划法 贪心法 回溯法 分支界限法 概率算法 近似算法
算法分析基础
时间复杂度
分析算法的运行时间，即算法执行所需要的基本操作数
复杂度关系
 O(1)：单个语句，⽆循环 O(n)~O(n3)：单层循环、双层嵌套循环、三层嵌套循环 O(log2n)：树形结构、⼆分法、构建堆过程 O(nlog2n)：堆排序、归并排序 O(2^n)：所有不同可能的排列组合
渐进符号
an^2 + bn + c。当n足够大时，bn和c对结果的影响微乎其微，所以可以看做结果只受n^2影响。用O就行了
时间复杂度计算
递归式
从算法的结构看，算法可以分为非递归形式和递归形式，此处讨论递归式算法时间复杂度
展开法
基本不考虑 
代换法
不考虑 
递归树法
不考虑
主方法（主定理）
掌握第一种即可 
例题
 主定理：T(n)=aT(n/b)+f(n) a = 8，表示每次递归调用会产生 a 个子问题量 b = 2，n/b 表示每个子问题的规模是原始问题的规模的 1/b d = lg2 8 = 3 f(n) = n2，表示除了递归调用之外的额外工作量 比较 f(n) 与 n^d 的增长速率 D
非递归式
对一段代码中执行次数最多的代码找规律 
空间复杂度
分治法
把⼀个⼤问题拆分成多个⼩规模的相同⼦问题，⼀般可⽤递归解决 分解：将n个元素分成各含n/2个元素的子序列 解决：用归并排序对两个子序列递归地排序 合并：合并两个已经拍好序的子序列以得到排序结果
二分搜索
以C为例： 和90比完，后面是85，说明90大了，后面又是61，说明85大了，依此类推  
动态规划法
⽤于求最优解
划分⼦问题（最优⼦结构），并把⼦问题结果使⽤数组存储，利⽤查询⼦问题结果构造最终问题结果
斐波那契数列、矩阵乘法、0-1背包问题、 LCS最长公共⼦序列
贪心法
（⽤于求满意解），都想要做好的，实际上不是最优的。局部最优
局部最优，但整体不见得最优。每步有明确的，既定的策略
经典问题：邻分(分数）背包、多机调度、找零钱问题
回溯法
通⽤的解题法
包含问题的所有解的树中，按照深度优先的策略，从根节点出发搜索树。系统的搜索⼀个问题的所有解或任⼀解
经典问题：N皇后问题、迷宫、背包问题
第9章 数据库技术基础
基本概念
数据库的三级模式

三级模式
外模式
对应视图
用户视图
概念模式/模式
对应数据库表
概念视图
内模式
对应物理文件
内部视图
两级映像
两层映像可以保证数据库中的数据具有较高的逻辑独立性和物理独立性
外模式-模式映像
模式-内模式映像
数据的独立性
数据与程序独立
数据的物理独立性
即数据库的内模式发生改变时，数据的逻辑结构不变。
数据的逻辑独立性
数据的逻辑独立性是指用户的应用程序与数据库的逻辑结构是相互独立的。数据的逻辑结构发生变化后，用户程序也可以不修改。但是，为了保证应用程序能够正确执行，需要修改外模式和概念模式之间的映像。
数据模型
数据模型三要素
数据结构 数据操作 数据的约束条件
ER 模型（★★★★★）
Entity-Relationship Model，是一种概念模式，代表实体-关系模型。 用于描述数据库中数据的结构和数据之间的关系 ER图 
实体
用矩形表示，矩形框内写明实体名
联系
实体间的联系。 用菱形表示，菱形框内写明联系名，并用无向边分别与有关实体连接起来， 同时在无向边旁标注上联系的类型（1:1、1:n、n:m-多对多）。 
属性
用椭圆表示，以无向边与对应实体进行连接 无向边：没有方向的横线
简单属性和复合属性
简单属性：性别，不可划分 复合属性：地址。还可以详细划分省市县 若不特别声明，通常指的是简单属性。
单值属性和多值属性
单值属性：年龄，是固定的，只有一个。 多值属性：亲人，有多个。
派生属性
可以根据出生年月算出年龄，年龄就是派生属性
NULL 属性
实体-联系方法

扩展的 E-R 模型
弱实体

特殊化

关系模式
可以简单理解为表结构 典型的形式是二维表，表格的名称为关系模式名称。表格的列为属性
关系模型
实体转关系模式
每个实体对应一个关系模式（一个实体对应一张表）
联系转关系模式
一对一关系
独立的关系模式
创建一个新的关系模式用来表示1对1的关系 属性：并入两端主键及联系自身属性 主键：任一端主键
归并(任意一端)
在实体的任一个关系模式中添加 属性：并入另一端主键及联系自身的属性 主键：保持不变
一对多关系
独立的关系模式
属性：并入两端主键及联系自身属性 主键：多端主键
归并（并入多端）
属性：并入另一端主键及联系自身的属性 主键：保持不变
多对多关系
独立的关系模式
属性：并入两端主键及联系自身属性 主键：联合主键
关系代数（★★★）
关系数据库的基本概念
关系的相关名词
目或度：关系模式中的属性的个数
主键
候选键
候选码 可以作为主键的集合，可以是联合主键。 学号+课程号，学号
图示法求候选键
 第3条，是把其他（有入度有出度）的并入入度为0的 示例 A ->B, AB -> C。A为候选键，A可以确定B，然后AB可以确定C 
主属性
组成候选键的属性就是主属性，其他就是非主属性
外键
完整性约束（★）
实体完整性
主键唯一不为空
参照完整性
（也称为引用完整性）：规定其外键为参照表的主键值或为空值。
用户自定义完整性
指用户针对某一具体的关系数据库的约束条件，反映某一具体应用所涉及的数据 必须满足的予以要求，由应用的环境决定，如年龄定义为 0~150 正整数。
五种基本的关系代数运算
并
并：二者元组之和去除一个重复行 
差
差：前者去除二者重复行 
笛卡尔积
列数为二者属性列数之和，行数为二者元素数乘积（s1的每一行分别和s2的每一行） 
投影
对指定表指定列的选择性展示。注意写法，写法可以用1,2,3,4表示 
选择
希腊字母 sigma 从给定的关系中选择出符合指定条件的元组，保留所有属性，但仅返回满足条件的行（相当于sql查询，比如age=18的） 
扩展的关系代数运算
交
交：二者重复行 
自然连接
列：为二者属性列数之和减去重复列 行：为二者同名属性列其值相同的结果元组。（结果相当于sql中的内连接，列数不一样） 笛卡尔积、选择、投影的组合表示可以与自然连接等价。 σ1=4：选择第1列的值等于第4列的值的数据 
关系数据库SQL语言简介
SQL 语言（★★★★）

关系数据库的规范化
函数依赖
函数依赖
x -> y x决定y，y依赖x。 依赖集1：{AB -> C,A -> C} 
部分函数依赖
组合候选中的某个属性可以决定非主属性时，就是部分函数依赖
传递函数依赖
也叫冗余函数依赖
主属性
组成候选键的属性就是主属性，其他就是非主属性
非主属性
组成候选键的属性就是主属性，其他就是非主属性
函数依赖的公理系统

规范化
第一范式（1NF）
若关系模式R的每一个分量是不可再分的数据项，则关系模式R属于第一范式。 面临的问题： 插入异常 删除异常 修改异常 数据冗余
第二范式（2NF）
在1NF的基础上，满足非主属性完全依赖候选键（不存在部分函数依赖）
问题
插入异常 删除异常 修改异常 数据冗余
解决方案
原理：将部分函数依赖部分分割出来一个关系模式
步骤

找出候选键，学号、课程号
将部分依赖的相关属性分离。创建新的关系模式（课程号、学分）
原来的关系模式中去掉学分。
BC 范式（BCNF）
当且仅当依赖集中的每个依赖的决定因素必定包含R的某个候选码 关系模式STJ（S，T，J） 依赖集1{T -> J, SJ -> T} 候选键位SJ和ST 没有非主属性，不存在传递依赖，所以符合3NF T 是 J 依赖的决定因素，不在SJ和ST中 所以不是BCNF
第三范式（3NF）
当且仅当关系模式R是第二范式，且R中没有非主属性传递依赖候选键是，才是3NF（不存在传递依赖）
解决方案
原理：将传递依赖分离出来
步骤

找出候选键：学号
找出非主属性：其他的几个
是否存在传递依赖，存在；学号 -> 系号 -> 系名
将传递依赖部分分离出来，创建关系模式 系号、系名、系位置
原来的修改成学号、姓名、系号
规范化过程-分解关系模式
保持函数依赖
无损联接分解
数据库的控制功能
事务管理
事务特性（ACID）
原子性
事务是原⼦的，要么都做，要么都不做
一致性
事务执⾏的结果必须保证数据库从⼀个⼀致性状态变到另⼀个⼀致性的状态 同时成功，同时失败
隔离性
事务相互隔离，当多个事务并发执⾏时，任⼀事务的更新操作直到其成功提交的整个过程，对其他事务都是不可见的
持续性
⼀旦事务成功提交，即使数据库崩溃，其对数据库的更新操作也将永久有效
数据库的备份与恢复
故障类型
事务内部故障
事务内部的故障有的可以通过事务程序本身发现。例如，银行转账事务，将账户A的金额转X到账户B，此时应该将账户A的余额-X，将账户B的余额+X。如果账户A的余额不足，那么，两个事务都不做，否则都做。但有些是非预期的，不能由事务程序处理，例如运算溢出、并发事务发生死锁等。
系统故障
通常称为软故障，是指造成系统停止运行的任何事件，使得系统要重新启动，例如 CPU 故障、操作系统故障和突然停电等
介质故障
通常称为硬故障，如磁盘损坏、磁头碰撞和瞬时强磁干扰。此类故障发生的几率小，但破坏性最大。
计算机病毒
计算机病毒是一种人为的故障和破坏，是在计算机程序中插入的破坏计算机功能或者数据可以繁殖和传播的一组计算机指令或程序代码
备份方法
是否停机
热备份-动态备份 冷备份-停机备份
数据多少
全量备份 增量备份：备份上一次之后的数据 差量备份：备份上一次全量备份以后得数据，期间可能有过多个增量备份
并发控制（★★）
并发操作带来的问题
丢失更新

不可重复读

脏读

并发控制技术
封锁
排他锁（X 锁）
若事务 T 对数据对象 A 添加了 X 锁，则只允许 T 读取和修改 A，其他事务不能再对A 加任何锁
共享锁（S 锁）
share：分享 若事务 T 对数据对象 A 添加了 S 锁，则只允许 T 读取 A，但不能修改 A。并且其他事务只能对 A 加 S 锁，不能加 X 锁。 共享时必须只读才能确保不出问题
三级封锁协议
第10章 网络与信息安全基础知识
计算机网络概念与ISO/OS网络体系结构
计算机网络概念
计算机网络分类
按分布范围： 
网络的拓扑结构
总线结构 星型结构 环形结构 树形结构 分布式结构 
ISO/OSI网络体系结构
ISO：国际标准化组织 OSI：开放系统互联参考模型 只是参考模型，不是标准 
应用层（Application Layer）
最高层协议 事务处理程序、电子邮件、网络管理程序
表示层（Presentation Layer）
负责数据的格式化和转换。数据的压缩、解压缩、加密和解密
会话层（Session Layer）
传输层（Transport Layer）
负责端到端通信，即为源和目的地的应用程序之间提供可靠的数据传输
网络层（Network Layer）：
负责数据在不同网络之间的路由和转发
数据链路层（Data Link Layer）
负责在两个相邻节点间的线路上无差错地传送以侦为单位的数据，并进行流量控制
物理层（Physical Layer）
OSI第一层
网络互联硬件
网络的设备
应用层互联设备
网关：用于在不同的网络系统之间通信
网络层互联设备
路由器：有很强的网络互联能力，判断网络地址和选择路径的功能。处理信息比网桥多，所以处理速度比网桥慢 三层交换机
数据链路层互联设备
网桥：是一个局域网和另一个局域网之间建立连接的桥梁，用于扩展网络和过滤帧 交换机 网卡
物理层互联设备
中继器：放大信号 集线器：特殊的多路中继器 双绞线
网络传输介质
有线介质
双绞线 同轴电缆 光纤
无线介质
微波 红外线 激光 卫星通信
网络的标准与协议
TCP/IP协议簇
TCP/IP分层模型
TCP/IP协议是Internet的基础和核心 
应用层
高层协议 NFS Telnet SMTP DNS SNMP FTP
传输层
TCP（Transmission Control Protocol）：传输控制协议，是TCP/IP簇中最重要的协议。为应用程序提供可靠、面向链接的、全双工的数据传输服务 UDP（User Datagram Protocol）：用户数据报协议，是一种不可靠的、无连接的协议，传输速度快
网际层（IP层）
IP协议：尽力传送的通信协议。将上层（TCP、UDP数据）或同层的其他数据（如ICMP数据）封装到IP数据报中 ARP（Address Resolution Protocol）：地址解析协议，将IP地址解析为物理地址（MAC地址）。 RARP：反地址解析协议，将物理地址解析为IP地址。 ICMP（Internet Control Message Protocol）：Internet控制信息协议用于当IP通信发生差错时用来发送差错报文的协议
网络接口层
Internet及应用
Internet地址
IP地址
长度32为（4字节），分为4段，每段8位，可以用十进制（192.168.1.1）可以用二进制表示 网络地址 + 主机地址 
A类地址：⽹络号8位，0开始
B类地址：⽹络号16位，10开始
C类地址：⽹络号24位，110开始
D类地址：组播地址，1110开始
E类地址：保留地址，11110开始
Internet服务
DNS域名服务
使用UDP端口：端口号53
远程登录服务
Telnet协议，使用TCP端口：端口号23
电子邮件服务
SMTP：简单邮件传送协议，端口号25 POP3：接受邮件协议，端口号110
WWW服务
HTTP协议：使用TCP端口，端口号80 HTTPS协议：443
文件传输服务
FTP协议：不安全的文件传输协议。传送协议端口号20，控制协议端口号21 TFTP：不安全不可靠 SFTP：安全的传输协议
网络安全
网络安全威胁
物理威胁 系统漏洞 编程威胁 网络攻击 身份鉴别
网络攻击手段
⽹络攻击分类
主动攻击
中断（可用性） 篡改（完整性） 伪造（真实性）
被动攻击
监听（保密性） 消息内容获取 业务流分析
常见的攻击⾏为
拒绝服务
攻击者利⽤众多傀儡主机向服务器发送服务请求，导致服务器资源被耗尽，⽆法提供正常的服务，向其他访问者发送拒绝服务应答
重放攻击
发送以前发送过得数据 有效防止加上时间戳
业务流分析
通过长期监听被攻击者的数据流，从⽽分析出相关业务流，可以依此了解被攻击者的⼀些倾向。 常见的⼴告推送就是建⽴在业务流分析基础上
网络的信息安全
常见的病毒分类
引导型
影响软盘或硬盘的引导扇区
⽬录型
修改硬盘上存储的所有⽂件的地址
⽂件型
感染可执⾏⽂件（包括EXE和COM⽂件）
宏病毒
宏病毒感染的对象是使⽤某些程序创建的⽂本⽂档、数据库、电⼦表格等⽂件
常见的病毒
系统病毒（KCOM）
蠕⾍病毒（Worm）
红⾊代码 爱⾍病毒 熊猫烧⾹ Nimda病毒 爱丽滋病毒
⽊马病毒（Trojan）：通过远程⽹络进⾏控制的恶意程序
脚本病毒（Script）
宏病毒（Macro）
防火墙技术
防外不防内
⼊侵检测IDS
不能主动阻止入侵，只能作为被动检测工具
加密与数字签名
加密技术
对称密钥密码体制
相同或者对称的密钥 AES DES 3DES IDEA TDEA RC2 RC4 RC5
非对称密钥密码体制
速度慢，强度高。成对使用，公钥加密，私钥解密 ECC RSA DSA
数字签名
用于确认发送者和消息完整性的一个加密的消息摘要，满足一下要求 接受者能够核实发送者 发送者事后不能抵赖对报文的签名 接受者不能伪造对报文的签名
信息摘要
（MD5加密）对原始数据进行哈希运算生成的固定长度的字符串，通常称为“散列值”或“哈希值” 不可逆，确保数据完整性 MD5(128位) SHA(160位)
数字签名
发送者使⽤⾃⼰的私钥对信息摘要签名， 接收者利⽤发送者的公钥对接收到的摘要进⾏验证。 验证数据的来源和真实性
数字证书
数字证书是由权威的第三方机构（CA，证书颁发机构）颁发的 颁发者信息 用户信息 用户公钥 有效期 确保数字签名中使用的公钥的可信性，验证发送方的身份
第11章 标准化和软件知识产权基础知识
标准化基础知识
国际标准
ISO、IEC等国际标准化组织。代号：标准代号+专业类号+顺序号+年代号
国家标准
GB—中国、ANSI—美国、BS—英国、JIS—⽇本。代号：我国强制性标准代号为GB、推荐性标准代号为GB/T、指导 性标准代号为GB/Z、实物标准代号GSB
区域标准
⼜称为地区标准，如PASC—太平洋地区标准会议、CEN—欧洲标准委员会、ASAC—亚洲标准咨询委员会、ARSO —⾮洲地区标准化组织
⾏业标准
GJB—中国军⽤标准、MIT-S—美国军⽤标准、IEEE—美国电⽓电⼦⼯程师协会。代号：由汉语拼⾳⼤写字母组
地⽅标准
国家的地⽅⼀级⾏政机构制订的标准。代号：由DB加上省级⾏政区代码的前两位
企业标准
代号由Q加上企业代号组成
知识产权基础知识
法律知识（★★）
法律法规

作品保护期限

知识产权⼈确定（★★★）
作品区分

作品归属

侵权判断（★★★★）
判断

特殊
中国公民、法⼈或者其他组织的作品，不论是否发表，都享有著作权。
开发软件所⽤的思想、处理过程、操作⽅法或者数学概念不受保护
著作权不适⽤的情形
法律、法规，国家机关的决议、决定、命令和其他具有⽴法、⾏政、司法性质的⽂件，及其官⽅正式译⽂
时事新闻、历法、通⽤数表、通⽤表格和公式
第12章 计算机专业英语
下午试题
数据流图
补充实体
就在文中描述的，一般是用户，装置、第三方服务之类
补充存储名称
文中描述，一般什么表、文件
缺失的数据流
根据父子平衡找：顶层图和0层图的平衡 0层图中的输入和输出是否都在， 比如维护信息，**实体 -> **管理 -> **表 比如读取信息，**表 -> ** 管理 -> **实体
数据流的组成
数据流：由一组固定成分的数据组成，表示数据的流向。每个数据流通常有一个合适的名词反映数据流的含义。 数据流的组成：就是包含哪些数据信息
结构化程序语言

数据库设计
补充实体联系图
补充实体 补充联系
补充关系模式
补充主外键
新增关系模式
注意写法：员工(姓名，性别，年龄，身份证号)
数据库设计步骤
需求分析 概念设计：ER图 逻辑设计：关系模式 规范化：范式 物理设计：具体实施数据库结构，定义存储引擎、索引、分区、视图等物理结构 数据库实现：创建表等 测试和优化
UML建模
补充用例
包含《include》
A----------<>B：A包含B
扩展《extend》
A----------<>B：A扩展B 例：找回密码是登录的扩展
类图
依赖
ClassA ─ ─ ─ ─ ▷ ClassB
关联
ClassA ────────────── ClassB
聚合
Class ◇───────────── Student
组合
School ◆───────────── Class
继承/泛化
GraduateStudent ─────────▷ Student
实现
ClassA ─ ─ ─ ─ ─ ─▷ InterfaceB
多媒体基础？
⾳频
声音
声⾳数字化过程
 采样→ 量化→ 编码
计算机通过话筒收到的信号是⾳频模拟信号
数字⾳乐合成技术为FW和Wave Table
声⾳信号数字化过程⾸先要进⾏的是A/D转换
声⾳格式
wav：微软，数据量大，质量高 mod：乐谱和乐曲使⽤的各种⾳⾊样本 mp3
计算
每秒容量=采样频率(Hz)/采样位数(位)×量化×声道数÷8
视频
视频格式
gif：网络传输 avi：微软公司发布的视频⽂件格式（AVI⽂件） mov/qt rm/rmvb mpeg/mpg/dat/mp4：运动图像压缩标准，压缩效率⾼，质量好，兼容性好 fli / foc
计算
容量=每帧图像容量(Byte) ×每秒帧数×时间+⾳频容量×时间
图像
基本参数
亮度：画⾯的明亮程度
⾊调：颜⾊的种类
饱和度：⾊彩的纯洁性，即颜⾊的艳丽程度
显⽰分辨率
显⽰屏上能够显⽰的像素数⽬，1024*768表⽰显⽰屏分为768⾏（垂直分辨率），每⾏（⽔平分辨率）显⽰1024个像素
DPI
每英⼨像素点数。 （在⼆维计算中，需要⾏、列分别乘⼀次。）
图像分辨率
图像深度
光的三原色
印刷三原色
彩⾊空间
RGB(普通显⽰器)
YUV(电视，兼容)
CMY/CMYK(印刷)、
HSV/HSB(艺术家)
图像格式
bmp：windows标准位图⽂件格式
gif：⽤于⽹络传输，数据块为单位传输信息，采⽤⽆损压缩算法
png：作为GIF替代品
jpg：有损压缩，压缩⽐例⾼，适合于处理⼤量图像的场合
计算
种类
多媒体定义
传播信息的载体，如语⾔、⽂字、图像、视频、⾳频等；
存贮信息的载体，如ROM、RAM、磁带、磁盘、光盘等
分类
感觉媒体
表⽰媒体
表现媒体（显⽰媒体）
存储媒体
传输媒体
数据压缩技术
有损压缩
⽆损压缩