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

蔚落 2022-10-15 12:51 330阅读 0赞

## 一、数据结构与算法 ##

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.查找右子树。
    
    数据结构：二叉排序树

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FkaWRhczc0ODkxNDk2_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FkaWRhczc0ODkxNDk2_size_16_color_FFFFFF_t_70 1]

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）—>**地址总线**宽度

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FkaWRhczc0ODkxNDk2_size_16_color_FFFFFF_t_70]: /images/20221014/367e7998cf7e4ecb86fa5601d2da0697.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FkaWRhczc0ODkxNDk2_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210525144514182.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FkaWRhczc0ODkxNDk2,size_16,color_FFFFFF,t_70