软件设计师考试

	表示1	表示-1	1-1结果	解释	范围	备注
原码	00000001	100000001	100000010 结果为 2	高位为符号为，0正数，1负数	-2n-1 ~ 2n-1	不适合负数运算
反码	00000001	111111110	111111111 结果为 -0	高位为符号为，0正数，1负数。对于负数，非符号位在原码的基础上取反	-2n-1 ~ 2n-1
补码	00000001	111111111	00000000 结果为0	对于负数，在原码的基础上，取反+1	-2n ~ 2n-1	计算机的实际储存方式
移码	100000001	011111111	100000000 结果为0	在补码的基础上， 符号位取反	-2n ~ 2n -1	在处理浮点数时使用

对于原码和反码， 因为有 -0 这个数， 所以范围少了1

对于补码， 没有 -0 ， -128 可通过 -127 - 1 计算， 也就是 100000001 + 111111111 = 100000000

数据到计算机内存的过程：

数据（-1） -> 原码（100000001） -> 反码 (111111110) -> 补码（111111111） -> 计算机内存

浮点数表示： N = M * R^e

• M 尾数
• R 基础
• e 指数

运算步骤

• 对阶： 指数按高次对齐
• 尾数计算
• 结果格式化： 确保 尾数 小数点左边为个位数，且不为0

流水线指在程序执行时，多条指令重叠进行操作的一种准并行处理实现技术

• 流水线的周期： 执行时长最长的一段
• 流水线的总执行时间：
  • 理论公式： 1条指令的执行时间 + （指令条数-1）* 流水线周期。 \((k+n-1)*\Delta t\)
  • 实践公式： 假定每个步骤的时间与周期相等， 如上图，总的步骤为 （指令条数+单条指令的步骤数-1）， 再乘以周期则为总时间
• 示例： 若指定流水线分为取指、分析、执行3部分，时间分别为2ns 2ns 1ns, 那么周期是多少？100条指令全部执行完需要多久？
  • 周期为 2ns
  • 按照理论公式： （2+2+1）+ 99*2 = 203
  • 按照实践公式： （3+99）*2= 204

• 吞吐率（Though Put rate, TP）指单位时间内流水线完成的任务数量

\begin{equation} TP = \frac{指令条数}{流水线执行时间} \end{equation}

• 对于上述例子，TP=100/203
• 最大吞吐率

\begin{equation} TP_max=\lim_{n->\infty}\frac{n}{(k+n-1)*\Delta t} = \frac{1}{\Delta t} \end{equation}

• 相当于看成每条指令的执行时间都为周期。n 无穷大时，可以忽略流水线的建立时间

\begin{equation} 加速比=\frac{不使用流水线的执行时间}{使用流水线的执行时间} \end{equation}

上述例子： 5*100/203

流水线的效率指的是流水线的设备利用率

\begin{equation} 流水线的效率E = \frac{n个任务占用的时空区}{k个流水线段的总时空区} = \frac{T_0}{kT_k} \end{equation}

上述的效率为 E=(1+1+1+3)*4 / (15*4)

• Cache的功能： 提交CPU数据输入输出的速率，突破冯诺依曼瓶颈，即CPU与储存系统间数据传输的带宽限制
• 程序执行的局部性原理，当引入Cache时，会大大加快执行效率。 例如把循环语句的变量储存到Cache中，就大大减少寻址时间
• 计算系统的平均周期： 假定 h 为Cache的命中率， t₁ 为Cache的周期时间， t₂ 为主存的周期时间， 那么两者结合的系统平均周期为：

\begin{equation} t_3 = h * t_1 + (1-h)*t_2 \end{equation}

如果 h=95%, t₁ = 1ns , t₂=1000ns, 得到 t₃= 50.95ns， 而没有Cache时，t₃ 会是 1000ns.

• 时间局部性： 例如 循环语句变量的储存
• 空间局部性： 例如 数组的储存
• 工作集理论：工作集指的是进程运行时被频繁访问的页面集合

• 随机存取储存器（RAM）： 我们常说的内存。 断电后信息丢失
• 只读存储器（ROM）： 比如说 BIOS。 断电后信息不丢失

• 主存的编址指的是把芯片组成响应的储存器
• 内存地址忽略后面的 H , 且是16进制
• 上图中， 8*4 表示有8个地址单元， 每个地址单元有 4bit
• 芯片组成储存器时，可以并排或竖排
• (c7fff+1-ac000)/1024, 共 112 个地址单元
• (112*16)/(28*16)=4 位

\begin{equation} 存取时间=寻道时间+等待时间（平均定位时间+转动延时） \end{equation}

• 机械硬盘，软盘等： 扇区储存数据，磁头读取数据
• 寻道时间指磁头移动到磁道所需的时间
• 等待时间为等待读写的扇区转到磁头下方所用的时间

• 注意，磁头经过后，才算读取完。对于上述，读取需要3ms
• 单缓冲区意味着缓冲只能储存一个物理块的信息
• 处理记录时，磁盘还是会继续转动
• 最长： (33+3)*10+(3+3)=366
• 最短： (3+3)*11=66 ， 处理当前的物理块，磁盘刚好准备读下一个物理块

• 可靠度 = 所有系统的可靠度之积

• R 为可靠度
• u 为失效率

• R₁ -> R_m 为功能相同的冗余系统

• R 可靠度

• 检错： 检查出错误
• 纠错： 检查出错误并纠正。 （通过冗余信息）
• 码距： 整个编码系统中任意两个码字的最小距离 （即变化多少位可以得到另外一个码字）
  • 若用1位二进制编码， A=0，B=1， 那么码距为1。假设传输时0变成1，无法检错，因为0/1都是合法的
  • 若用2位，A=00，B=11, 那么码距为2。假设传输时有个0变成1，可以检错，因为编码出来的是非法的
  • 若用3位，A=000，B=111，码距为3，可以检错。也可以纠错，比如把110看成111

• 2ⁿ 放校验位 （n从0算起）

  

\begin{equation} 2^r >= I + r +1 \end{equation}

根据上述公式，算出有 I 个信息位时，需要多少校验位

• 前趋图用来表达完成一系列任务的先后的约束关系

• 互斥，在某一个时刻，某个资源只允许一个进程使用

• 同步，当差距较大时，速度大的等待速度小的

  

• 市场是互斥问题，只能生产者或消费者之一入场
• 入市场是同步问题，生产者需要等消费者消费完，才能再次将商品搬入市场

• 临界资源： 进程间需要互斥方式对其进行共享的资源，如打印机等
• 临界区： 每个进程中访问临界资源的那段代码
• 信号量： 运用于PV操作中的特殊变量，如上图S
• P操作：当 S<0 时，将进程放入进程的等待队列, （阻塞）
• V操作：当 S<=0 时， 将进程从等待队列取出， （唤醒）即使F也不会阻塞

• PV操作用来解决并发进程间某些约束关系的问题

  

• 生产者和消费者分别执行PV操作，可以防止缓冲区溢出

  

• 主要注意， P操作会阻塞，V操作不会阻塞

  

• 将前趋图转成PV操作

• 如果一个进程在等待不可能发生的事情，则发生 死锁
• 如果一个或多个进程发生死锁，则造成 系统死锁

• 13个， 因为多出来的一个资源分配给其他一个进程后，他的资源满足了，从而运行下去直至资源释放。

  

• 满足四大条件才会产生死锁
  • 互斥
  • 保持和等待
  • 不剥夺
  • 环路等待

分配资源的原则：

• 当进程需要的资源，不超过系统所能提供的最大资源时，可以接纳该进程
• 进程可以分期请求资源，但请求的总数不能超过最大的需求量
• 当系统的资源不能满足进程的请求资源时，可以推迟分配，但总能使进程在有限的时间内得到资源

• 最佳适应算法会导致很多小的内存块

• 使用分区储存，可能无法提供足够大的连续内存给用户空间。

• 当内存分成相同大小的块状（比如4K）
• 逻辑地址记录页号，从0算起

• 物理地址使用块号，可能不是从0算起，使用页表查询出来。

  

• 4k表示 2¹², 说明地址的后12位是页内地址， 为A29
• 剩余的5即是页号，其物理块号就是页帧号，为6
• 可以淘汰的页号需要是没访问的，也就是访问位为0，为1

• 段大小可以不一致

• 段表储存 段号，段长，基址

  

• 先分段，再分页

• 小容量的相联存储器
• 由高速缓存组成，速度快
• 从硬件上保证内容按并行查找
• 一般存放当前访问最频繁的少数活动页面的页号

• 解决系统能提供的页数少于程序申请的页数的问题
• 最优算法 OPT
• 随机算法 RAND
• 先进先出算法 FIFO： 可能产生抖动，即分配的页数多，反而效率低了（如下图）
• 最近最少使用算法 LRU： 不会产生抖动

• 缺页：页不在内存中

  

• 没有快表，说明每读一次块，需要两次内存访问（因为要查表）
• 指令只产生一次缺页中断

• 一般是13个节点
• 一个盘块4K
• 一个索引节点可以储存 4k/4 = 1024 个地址

• 逻辑块号从0开始计数

• 空闲区表法
• 空闲链表法
• 位示图法

• 成组链接法

  

• 用 0（空闲） 1（占用）表示物理块

• x个字中，从1算法， 第x位置，从0算起
• 4195号物理块，是第4196个物理块
• 4196/32=131.125， 说明前131个字占满了，故放在132个字中
• 131*32=4192, 4196-4192=4， 故放在该字的第4个，也就是第3位置

内存与外设间的传输控制方案：

• 程序控制方式： 又称为程序查询方式，CPU介入最多。需要CPU每隔一段时间询问外设传输状态
• 程序中断方式： 如果外设完成数据传输，会发出中断信号
• DMA方式： 有专门的DMA控制器管控内存与外设的数据交换，CPU参与少
• 通道
• 输入输出处理机

• 将输入的内存先放入缓冲区
• 类似于任务队列

• 内模式：与物理数据库关联， 关注数据的储存方式
• 概念模式：数据表
• 外模式：视图
• 外模式-概念模式映射
• 概念模式-内模式映射

• 如果函数X可以决定函数Y， 那么称 Y 依赖于 X，记作 X->Y
• 比如，在数据库中， 根据 学号 确定 姓名
• 部分函数依赖： 主键是多个组合字段， 但是其中一个字段也可以确定一条记录。 (A+B)->C , A->C
• 传递函数依赖： A->B , B->C , 可以得出 A->C ，（注意 B->A 不能成立）

非规范化的关系模式存在的问题：

• 数据冗余
• 更新异常
• 插入异常
• 删除异常

• 超键可能存在多余属性， 而候选键不存在
• 候选键可以有多个，主键只有一个

• 画出有向图
• 留意 ABD->E 这个的箭头

• 保持函数依赖的分解
  • p={A,B,C} 存在 A->B B->C 如果有两个关系模式 {A,B} {B,C} ,就保持了函数依赖。如果是 {A,B} {A,C} 则没有， 因为无法推出 B->
• 无损分解
  • 有损，不能还原
  • 无损，可以还原. 就是通过联表操作，可以还原成原来的整表

事务：

• 原子性
• 一致性： 执行之前和之后状态一致， 比如转账操作，执行前后金额总数相同
• 隔离性
• 持续性： 事务执行后，结果与影响是持续的

并发产生的问题：

• 丢失更新
• 不可重复读问题
• “脏”数据的读出

• 一级封锁协议： 事务T在修改数据R之前必须对其进行加X锁（写锁），直到 事务结束 后释放。 （可以防止丢失更新）
• 二级封锁协议： 在一级封锁协议的前提下，再加S锁（读锁）， 直到 读取 完后释放。（可以防止丢失更新和脏数据的读出）
• 三级封锁协议： 与二级封锁协议不同的是，直到 事务结束 后释放。 （三个问题都可以防止）
• 两段锁协议： 可串行化， 可能发生死锁

• TCP/IP协议： Internet, 可扩展，可靠，应用最高，牺牲速度和效率
• IPX/SPX协议： 路由，大型企业网， 局域网对战游戏

• NETBEUI协议： IBM， 不支持路由，速度快

  

TCP/IP 协议组

• ARP： IP -> Mac
• RARP: Mac -> IP

• 基于UDP， 动态分配IP
• 特殊的IP：
  • 169.254.X.X window
  • 0.0.0.0 linux
  • 说明没有和 DHCP 联系上

• 主机向本地域名服务器的查询采用 递归查询 。 服务器必须回答映射关系
• 本地域名服务器向根域名服务器的查询采用 迭代查询 。 服务器收到一次回复一次，该结果可能是其他DNS服务器地址

• 核心层一般有冗余机器， 防止出故障

• 加密密钥和解密密钥一致
• DES: 替换+移位、56位密钥、64位数据块、速度快、密钥易产生
• 3DES（3重DES）： 两个56位密钥K1，K2
  • 加密 K1加密->K2解密->K1加密
  • 解密 K1解密->K2加密->K1解密
• AES
• RC-5
• IDEA
• 加密速度快
• 加密强度不高
• 密钥分发困难

• 有公钥和私钥
• 加密速度慢
• 公钥加密，私钥解密
• RSA： 512（现在1024）位密钥、计算量大、难破解
• Elgamal
• ECC
• 其他算法：背包算法、Rabin、D-H

威胁	描述
重放攻击（ARP）	截获某次合法通信，拷贝后重复发送
拒绝服务（DOS）	对信息或其他资源的合法访问被无条件阻止
窃听	窃取系统中的信息资源和敏感信息。例如对通信线路中的传输信号进行搭线监听
业务流分析	长期窃听 ， 利用统计分析方法对通信频度、信息流向进行研究
信息泄漏
破坏信息的完整性
非授权访问
假冒
旁路控制	利用系统的安全缺陷获取非授权的权利
授权侵犯	也被称为“内部攻击”， 被授权的某个人将此权限用于其他目的
特洛伊木马	木马程序，被执行时会破坏用户的安全
陷阱门	某个系统设置了“机关”，使得当提供特定的输入数据时，允许违反安全策略
抵赖	一种来自用户的的攻击，例如：否认自己发布过的某条消息

• (a₁, a₂, … , a_n)
• 两种存储方式
  • 顺序表：储存空间连续
  • 链表： 储存空间不一定连续 （会包含下一个位置的指针）
    • 单链表
    • 循环链表
    • 双向链表

	顺序储存	链式存储
储存密度	1，更优	<1
容量分配	事先确定	动态改变
查找运算	O(n/2)，有序时更优	O(n/2)
读运算	O(1)	O([n+1]/2) good:1, bad:n
插入运算	O(n/2),good:0,bad:1	O(1)
删除	O([n-1]/2)	O(1)

• 循坏队列
  • 队空条件： head = tail
  • 队满条件： head = (tail+1)%size

• 节点的度： 一个节点拥有的child的个数. 上述，1的度为2； 3为1； 7为0
• 树的度： 树中所有节点最大的度，上述为2
• 叶子节点： 度为0的节点
• 分支节点：
• 内部节点： 非叶子和根， 2，3，6
• 父节点：
• 子节点：
• 兄弟节点：同一层次的节点
• 层次：

• 满二叉树： 没有缺失的节点
• 完全二叉树： 最底层只缺了右边的节点，其他的层的节点都是满的

二叉树的特性：

• 层次从1开始算
• 第i层最多有 2^(i-1) 个节点
• 深度为k的二叉树， 最多有 2ⁱ - 1 个节点
• 叶子节点 n₀ 与度为2的节点 n₂ , 满足 n₀=n₂+1
• 如果对有 n 个节点的完全二叉树有以下特征：
  • 如果 i = 1， 则无父节点； 如果 i>1, 其父节点为 |i/2|(向下取整)
  • 如果 2i > n, 则i为叶子节点，无左子节点；否则，其左子节点是2i
  • 如果 2i + 1 > n, 则 i 无右子节点；否则，其有子节点为 2i+1

• 层次遍历： 1 2 3 4 5 6 7 8
• 前序遍历: （根 -> 左子树 -> 右子树） 1 2 4 5 7 8 3 6
• 中序遍历： （左子树 -> 根 -> 右子树） 4 2 7 8 5 1 3 6
• 后序遍历： （左子树 -> 右子树 -> 根） 4 8 7 5 2 6 3 1

• 根据已知的二叉树遍历序列，还原出二叉树
• 前+中 或 中+后 可以构建出
• 如果只有 前+后 不可以构建

• 孩子节点 -> 左子树节点

• 兄弟节点 -> 右孩子节点

  

• 左子树小于根
• 根小于右子树
• 又称排序二叉树
• 极大提高查找效率
• 不能有相同的节点

• 常用用于哈夫曼编码（无损压缩）
• 树的路径长度：树中的路径累加的值， （上面的12， 为2）
• 权： 节点的值
• 带权路径长度： 路径长度乘以权（上面的12 为 2*12 = 24）
• 树的带权路径长度： 叶子节点带权路径长度之和 （左树为 2*2+4*3+8*3+1=41）

• 哈夫曼的树的树的带权路径长度最小

  

• 构造哈夫曼树时，只有叶子节点才是初始的权值

• 为了方便遍历，利用其叶子节点的指针
• 前序线索二叉树
  • 叶子的左指针指向前序遍历的左边，右指向右边
  • 上述的，前序遍历顺序为 ABDEHCFGI
  • 故D左指向B，右指向E
• 中序和后序类似

• 同一序列，排序二叉树会有多种
• 任意节点的左右子树深度相差不超过1
• 每个节点的平衡度只能为 +1 0 -1
  • 平衡度的计算， 左子树深度为正， 右子树为-

• 无向图： 节点之间没有方向， 若每个顶点间都有边相连，则是 完全图
• 有向图： 节点之间有方向，若每个顶点间都有两条有向边相连 ， 则是 完全图

• 深度优先遍历 (上->下, 左->右)： V₁ V₂ V₄ V₈ V₅ V₃ V₆ V₇

• 广度优先遍历 (左->右，上->下)： V₁ V₂ V₃ V₄ V₅ V₆ V₇ V₈

  

• 广度优先： 从 0 的链表开始， 先访问完当前链表，再递归访问。 0 4 3 1 6 2 7 5
• 深度优先： 从 0 的链表开始， 从当前链表第一个就开始递归访问。 0 4 6 7 1 2 5 3

• 用有向边表示活动的先后关系。这种有向图称之为 AOV网络
• 上图的拓扑排序有：02143567 01243567 02143657 01243657

• 图有环路，树没有环路

• 假设有 n 个节点， 那么树的边最多 n-1 条， 故图的最小生成树有 n-1 边

  

• 有穷性： 执行有穷步骤后结束
• 确定性： 指令必须明确
• 输入 >=0
• 输出 >=1
• 有效性： 算法每个步骤能有效执行并得到确定的结果， 例如 b=0 , a/b 就是无效的

• 时间复杂度： O(1) < O(lgn) < O(n) < O(nlgn) < O(n²) < O(n³) < O(2ⁿ)
• 空间复杂度： 执行过程中需要用到的临时空间

• 按照计算优先级依据中缀遍历构造树
• D

• 适合需求明确，二次开发
• 应用于结构化开发

• 中小型项目

• 架构模式： 软件设计中的高层决策，例如 C/S 结构就属于架构模式， 架构模式反映了开发软件系统过程中所作的基本设计决策
• 设计模式： 比架构模式低一个层次。关注软件系统的设计， 与具体的实现语言无关。
• 惯用法： 最底层的模式，关注软件系统的设计与实现，与语言相关