软考中级复习笔记【自用】

一、数据结构与算法

1.线性链表：
带头结点的线性链表头指针指向头结点，头结点不可被删除，头指针的值不需要修改；
不带头结点可删除头结点，删除后需要将头指针指向新的第一个结点。

2.线性表存储方式
顺序存储：顺序存储，随机存取，查找元素 i 与时间 i 无关

链式存储：随机存储，顺序存取，访问元素时，必从头指针开始逐个访问

3.双向循环链表，p所指向的结点之后插入s所指向的结点，其修改指针的操作是____，其中p指向的不是最后一个结点。
捷径：判断p->next = s;后面是否还有通过指针 “p->next”访问p以前的直接后继的引用，有则错误。
语句p->next = s; 写到插入算法最后

4.二叉树
度为0的结点：叶子结点

先序遍历：根左右
中序遍历：左根右
后序遍历：左右根

5.查找算法：
时间复杂度
顺序查找：O(n)
折半查找：O(log2n) = O(lbn)
哈希散列法(哈希表)：O(1)
分块查找：O(logn)

二叉树排序： O(log2N)

• 特点是：

  a.若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

  b.若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

  c.它的左、右子树也分别为二叉排序树。

  搜索原理：

  a.若b是空树，则搜索失败，否则：

  b.若x等于b的根节点的数据域之值，则查找成功；否则：

  c.若x小于b的根节点的数据域之值，则搜索左子树；否则：

  d.查找右子树。

  数据结构：二叉排序树

6.满二叉树一定是完全二叉树

7.哈夫曼编码是前缀编码
任一字符的编码都不为另一字符编码的前缀

8.36条边的完全图有多少个顶点
非连通图：至少含有两个连通子图
n* (n-1) /2 + 1 = 边数

9.递归算法：
先后分为递推和回归两个阶段

10.完全二叉树 结点数 N
叶子结点数：N/2

11.结点拥有的子树数目称为结点的度。
哈夫曼树是严格的二叉树，是在叶子结点和权重确定的情况下，带权路径长度（WPL）最小的二叉树，也被称为最优二叉树。
WPL计算：结点权值*路径长度，求和
应当构建怎样的二叉树，才能保证其带权路径长度最小？
原则上，我们应该让权重小的叶子结点远离树根，权重大的叶子结点靠近树根

N:总结点数（顶点数）……N = 2 * N2 + 1
N0：叶子结点数…………N0 = N2 +1
N2：度为2的结点数

12.贪心算法 该策略与递归技术的联系最弱

13.若只能得到其中第K个元素之前的部分排序，采用堆排序

14.某树有N个结点，所有分支结点度为K（非叶子结点的子树数目），则该树叶子结点数量：
[N * (K-1) ] / K

二、程序语言与语言处理

1.调用方式：
传值调用：
实参值–>形参，形参作为过程中的局部变量，无返回
引用调用：
实参地址–>形参，有返回

2.单词符号分解成句子：语法分析

3.确定性有限自动机A 与 非确定性有限自动机B等价
说明 A与B可识别的记号相同

4.解释型程序：不生成目标代码
编译型程序：生成目标代码

5.C语言程序
编译–》OBJ目标文件–》链接–》EXE可执行文件–》执行

*闭包（0~n次）
| 或
` 连接

不能用正规式表示：

1. 配对括号构成的串的集合
2. 语句的嵌套
3. 重复串

上下文无关----- 包含—>> 正规式可描述的每种结构

8.死循环：语义错误

9.Pascal语言最早是为教学目的开发而成

三、操作系统

四、软工

1.达到100%CDC（条件/判定覆盖） 一定满足100%的CC（条件覆盖）

2.定义风险参照水准是风险评估活动常用的技术

3.一个模块的作用范围应在其控制范围内

4.（SC）语句覆盖：每个语句执行一次（最弱）

5.（DC）判定覆盖：也叫分支覆盖。包含语句覆盖，且每个分支都至少执行一次

6.（CC）条件覆盖：包含语句覆盖，且每个条件都取到各种可能的结果。

DC判定覆盖与CC条件覆盖无关

7.（CDC）判定/条件覆盖：使判定表达式 每个条件的所有可能结果 至少出现一次；且每个判定本身的所有可能结果也至少出现一次

8.（MCC）条件组合覆盖：每个判定表达式中 条件结果的所有可能组合 至少出现一次

满足条件组合覆盖一定符合判定/条件覆盖

9.路径覆盖：使程序的 每条执行到的路径 都至少经过一次，若有环路，每条环路至少经过一次

10.螺旋模型：结合了演化模型和瀑布模型的优点，加入风险分析

11.极限编程4大价值观
1）沟通
2）简单
3）反馈
4）勇气
重用户反馈、提倡减少文档

五、面向对象

1.特定多态：
··过载、
··强制
2.通用多态：
参数多态
包含多态

3.行为事务是模型的动态部分，描述跨越时间和空间的行为。

4.结构性视图：
对象图、
包图、
构件图、
部署图、
类图、

5.开闭原则可以扩展已有系统，并为之提供新的行为

6.边界类主要职责是存储和管理系统内部信息，可以有行为，甚至很复杂的行为

7.聚合 不同周期

8.组合 整体和部分同生命周期

9.UML图，关联多重性
0…1 最少0，最多1
0…*
1…*

10.多计算机属于MIMD
多指令多数据

MISD多指令单数据被认为不可能

11.控制器：
程序计数器（PC）
指令寄存器
指令译码器
状态/条件寄存器
时序发生器
微操作信号发生器

12.字长（32位/64位）----->数据总线----->CPU同一时间处理的二进制位数

内存容量（8GB）—>地址总线宽度