软件设计师学习记忆点

原码就是符号位加上真值的绝对值，即用第一位表示符号，其余位表示值。比如：如果是8位二进制：
[+1]原= 0000 0001
[-1]原= 1000 0001
第一位是符号位，因为第一位是符号位，所以8位二进制数的取值范围就是：（即第一位不表示值，只表示正负。）
[1111 1111 , 0111 1111]即[-127 , 127]

最高位是符号位，其余低位表示数值的绝对值

反码的表示方法是：
正数的反码是其本身；
负数的反码是在其原码的基础上，符号位不变，其余各个位取反。
[+1] = [0000 0001]原= [0000 0001]反
[-1] = [1000 0001]原= [1111 1110]反

正数的反码与原码相同，负数的反码是其绝对值按位取反（符号位不变）

补码的表示方法是：
正数的补码就是其本身；
负数的补码是在其原码的基础上，符号位不变，其余各位取反，最后+1。(也即在反码的基础上+1)
[+1] = [0000 0001]原= [0000 0001]反= [0000 0001]补
[-1] = [1000 0001]原= [1111 1110]反= [1111 1111]补

1000 0000 - 0111 11111，其中-128的补码为1000 0000是人为规定的，这点比较特殊

正数的补码与原码相同，负数的补码是其反码末位加1（符号位不变）

计算机计算是用补码进行的

补码的符号位按位取反

只用于浮点数的解码

移码只能用于表示整数

码距：任何一种编码都由许多码字构成，任意两个码字之间最少变化的二进制位数就称为数据校验码的码距

奇偶校验码的编码方法是：由若干位有效信息（如一个字节），再加上一个二进制位（校验位）组成校验码

奇校验：整个校验码（有效信息为和校验位）中“1”的个数为奇数

偶校验：整个校验码（有效信息位和校验位）中“1”的个数为偶数

可检查1位（奇数位）的错误，不可纠错

编码方式：在k位信息码之后拼接r位校验码。应用CRC码的关键是如何从k位信息位简便的得到r位校验码（编码），以及如何从k+r位信息码判断是否出错

把接收到的CRC码用约定的生成多项式G(X)去除（模二除法），如果正确，则余数为0；如果某一位出错，则余数不为0.不同的位数出错其余数不同，余数和出错位序号之间有唯一的对应关系

可检错，不可纠错

原理：在有效信息位中加入几个校验位形成海明码，使码距比均匀的拉大，并把海明码的每个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现错误，还能指出错误的位置，为自动纠错提供了依据。

海明校验位求取公式

可检错，也可纠错

输入/输出设备与存储器之间的数据传送通过运算器完成

CPU结构

一台计算机的所有指令的集合构成该机的指令系统，也称为指令集

操作码：指明操作的类型；地址码：主要指明操作数及运算结果存放的地址

特点：操作数直接在指令中，速度快，灵活性差

特点：指令中存放的是操作数的地址

特点：指令中存放了一个地址，这个地址对应的内容是操作数的地址

特点：寄存器存放操作数

特点：寄存器内存放的是操作数的地址

内存+外存划分在一起叫虚拟存储体系（蓝色虚框）；外存，内存，cache组合起来叫三级存储体系（黄色虚框）

虚拟存储器

在计算机的存储系统体系中，Cache是访问速度最快的层次（若有寄存器，则寄存器最快）

Cache并不是主存的扩展，一定要牢记

使用Cache改善系统性能的依据是程序的局部性原理

命中率和平均周期的计算

主要记住：主存与cache之间的地址映射是硬件直接完成的

答案：A，D

多个存储器可以串联或者并联形成更大的存储器，串联的话还是4比特。并联的时候，一个存储单元就会变成8bit（字节1B=8bit）。考试中没有明确说明的时候，默认一个存储单元都是8bit。

答案：D，B

总线分类

集合

线性结构

树形结构

图状结构（网状结构）

顺序存储

链式存储

索引存储

散列存储

一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成

算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出

算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现

一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合

一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量

时间开销与问题规模n之间的关系

空间开销（内存开销）与问题规模n之间的关系

双向链表

循环链表

静态链表

性能

答案D

答案：a+26，需要记忆公式 

例题

答案：例1：长度3，深度2；例2：head(head(tail(LS1)))

根左右

左根右

左右根

按层从左到右逐次遍历

前序遍历：1,2,4,5,7,8,3,6

中序遍历：4,2,7,8,5,1,3,6

后序遍历：4,8,7,5,2,6,3,1

层次遍历：1,2,3,4,5,6,7,8

反向构造二叉树思想要掌握

示例

每一层都跟它的根作比较

示例

构造霍夫曼树的权值组都仅作为叶子节点存在，中间节点都是两个节点的加和。首先选择两个做小的数做叶子节点，然后相加得到两个节点的根节点，之后再选择剩下的最小的两个，和当前根节点比较，如果有一个比根节点小，一个比根节点大或者相等，则取一个作为根节点的兄弟节点，继续计算；如果两个都比跟节点小，则单独取出两个节点作为新的一组节点，和当前根节点同层，循环该步骤直至全部算完。整体思想就是权值越大需要路径越小。

示例

左边的不是平衡二叉树，右边的是平衡二叉树。判断是否是平衡二叉树，需要对每个节点的子树深度进行计算，左右子树深度相减

以一个点为起点，不断引入权值最小的点路径

直接找权值最小的先连接起来，然后寻找没有连接的节点，找最小权值相连

mid=(low+high)/2，向下取整，在切换low或者high的值的时候，注意比mid小一或者比mid大1

处理冲突的方法

稳定与不稳定排序

内部排序与外部排序

插入类排序

交换类排序

选择类排序

归并排序

基数排序

需要记忆

分而治之

答案：AD

局部最优

和分治法最大的区别是子问题不独立

整体最优

答案：CA（0-1背包问题是全部装进去，部分背包问题是可以把商品劈开装一部分）

并发

共享

虚拟

异步

手动操作阶段

批处理阶段

分时操作系统

实时操作系统

网络操作系统

分布式操作系统

个人计算机操作系统

答案C

主要考察实时操作系统和嵌入式操作系统

主要考察线程有哪些可以共享，哪些不可以共享

互斥模型下会产生间接制约关系，同步模型下会产生直接制约关系

P操作为加锁的过程（会检查前驱是否完成），V操作为解锁的过程（会通知后继是否可以开始）

S1和S2为同步信号量

接下一张图

信号量数量跟箭线数量相关

接下图

答案：C,D

w表示每个进程所需的资源数，m是进程数，n是系统不可能发生死锁的最小资源数

更正：第三段第二句：如果系统进入不安全状态就没有安全序列

答案B

答案B

单一连续分配

固定分区分配

动态分区分配（主要考察）

概念：将程序与内存均划分为同样大小的块，以页为单位将程序调入内存

页式存储调用过程

页面置换算法

例题

概念：按用户作业中的自然段来划分逻辑空间，然后调入内存，段的长度可以不一样。 其中自然段指的就是逻辑长度，比如一个完整的for循环

合法段地址，对应段号内的偏移量不能超过段长

例题

先分块，在分段，在分页

最佳置换算法（OPT）

先进先出置换算法（FIFO）

最近最久未使用置换算法（LRU）

时钟置换算法（CLOCK）

所有磁头在一个主杆上，即磁头的移动是一致的，所以一次只能有一个磁头在读取数据

相当于流水线时间计算

讲解

层次，中间的三层是为了屏蔽硬件的，用户只需要操作软件就可以了

什么是I/O设备

按使用特性分

按传输速率分

按信息交换单位分

答案D

windows系统为三级目录结构

答案A

磁盘访问次数都是1次，无论是绝对路径还是相对路径

例题

无结构的流式文件

有结构的记录式文件

连续分配

链接分配

索引分配

位示图（重点考）

答案B，需要计算响应比来选择作业调度序列

分布式数据库特点

分布式数据库透明性

答案D，A

答案C

答案B

答案B

答案D

答案C

E-R模型

需要掌握什么是实体，联系，属性

扩充的E-R模型

数据模型

关系的三种类型

完整性约束

例题

转换依据：一个实体型必须转换为一个关系模式

总结

简单的关系代数：并交叉

复杂的关系代数：笛卡尔积

投影操作是对列的操作

选择操作是对行的操作

连接操作

查询优化原则

例题

函数依赖

Amstrong公理体系

候选键

例题

只要没有达到第三范式，都会有上图问题

规范化理论

范式

保持函数依赖分解

无损分解

例题

答案AC

答案：ADC；针对第三个空，SP_P表里面存储的是项目号，零件号，数量，一个项目可以供应多种零件，所以需要对项目号去重

答案C

答案D

答案D

答案：D，C

数据仓库是OLAP，A是分析的意思；数据库是OLTP，T是事务的意思。

答案B

1.可行性分析：由软件开发方与需求方共同讨论，主要确定软件的开发目标及其可行性。

2.需求分析：在确定软件开发可行的情况下，对软件需要实现的各个功能进行详细分析。主要解决“做什么”的问题

3.概要设计：主要根据需求分析的结果，对整个软件系统进行设计，如系统框架设计、数据库设计等

4.详细设计：是对每个模块完成的功能进行具体描述，要把功能转变为精确的、结构化的过程

5.程序编码：将软件设计的结果转换成计算机可运行的程序代码。在程序编码时，必须要指定统一、符合标准的编写规范，以保证程序的可读性、易维护性，提高程序的运行效率。

6.软件测试：在软件设计完成后要经过严密的测试，以发现软件在整个设计过程中存在的问题并加以纠正

7.维护：在软件开发完成后并投入使用后，由于各种原因，软件会不能继续适应用户的要求。延续软件的使用寿命，就要对软件进行维护，包括纠错性维护和改进性维护两个方面

1.初始级：软件过程是无序的，有时甚至是混乱的，对过程几乎没有定义，成功取决于个人努力

2.可重复级：建立了基本的项目管理过程来跟踪费用、进度和功能特性，制定了必要的过程纪律，能重复早先类似应用项目取得的成功

3.已定义级：已将软件管理和工程两方面的过程文档化、标准化，并综合成该组织的标准软件过程。所有项目均使用经批准、裁剪的标准软件过程来开发和维护软件

4.已管理级：收集随软件过程和产品质量的详细度量，对软件过程和产品都有定量的理解和控制

5.优化级：过程的量化反馈和新晋的新思想、新技术促使过程不断改进。

结构类似于CMM，它关注组织的成熟度。有五个成熟度等级

关注每个过程域的能力，一个组织对不同的过程域可以达到不同的过程能力等级。CMMI中包括6个过程域能力等级，等级编号为0~5

系统设计基本原理

系统总体结构设计

数据流图

水晶法认为每一个不同的项目都需要一套不同的策略、约定和方法论，认为人对软件质量有重要的影响，因此随着项目质量和开发人员素质的提高，项目和过程的质量也随之提高。通过更好地交流和经常性的交付，软件生产力得到提高。

并列争球法使用迭代的方法，其中，把每 30 天一次的迭代称为一个“冲刺”，并按需求的优先级别来实现产品。多个自组织和自治的小组并行地递增实现产品。协调是通过简短的日常情况会议来进行，就像橄榄球中的“并列争球”。

ASD有6个基本的原则：有一个使命作为指导；特征被视为客户价值的关键点；过程中的等待是很重要的，因此“重做”与“做”同样关键；变化不被视为改正，而是被视为对软件开发实际情况的调整；确定的交付时间迫使开发人员认真考虑每一个生产的版本的关键需求；风险也包含其中。

敏捷统一过程（Agile Unified Process，AUP）采用“在大型上连续”以及在“在小型上迭代”的原理来构建软件系统。采用经典的 UP 阶段性活动（初始、精化、构建和转换)，提供了一系列活动，能够使团队为软件项目构想出一个全面的过程流。在每个活动里，一个团队迭代使用敏捷，并将有意义的软件增量尽可能快地交付给最终用户。每个 AUP 迭代执行以下活动:
建模。建立对商业和问题域的模型表述，这些模型“足够好”即可，以便团队继续前进。
实现。将模型翻译成源代码。
测试。像 XP -样，团队设计和执行一系列的测试来发现错误以保证源代码满足需求。
部署。对软件增量的交付以及获取最终用户的反馈。
配置及项目管理。着眼于变更管理、风险管理以及对团队的任一制品的控制。项目管理追踪和控制开发团队的工作进展并协调团队活动。
环境管理。协调标准、工具以及适用于开发团队的支持技术等过程基础设施。

人工检测

计算机辅助静态检测

黑盒测试

白盒测试

甘特图可以表示任务间的并发，但是不能清晰地反映出各任务之间的依赖关系

可以表示任务之间的依赖关系，但是无法反应任务之间并行关系

1.风险识别

2.风险预测

3.风险评估

4.风险控制

不成文的方法，数环+1就是环路度量

结构事物（Structural Thing）

行为事物（Behavior Thing）

分组事物（Grouping Thing）

注释事物（Annotation Thing）

依赖（Dependency）

关联（Association）

泛化（Generalization）

实现（Realization）

类图一定会考。模型管理和可扩展性不考

代码调用

代码接口示例

类适配器

对象适配器

接口适配器

代码

代码

命令模式代码

中介者模式代码

观察者模式代码