## 编译与解释

![image.png](/static/img/f8d6a14a6e083c7a0f909f49e6ab970f.image.png)



## 文法

![image.png](/static/img/8ddfe9e56e9f20ae666cc1df9bedaf55.image.png)

![image.png](/static/img/cde70f0d587a77595591e088f0c5aae8.image.png)

语法推导树

![image.png](/static/img/afee69279fdd615589e498402e9b50f8.image.png)

## 有限自动机

![image.png](/static/img/cd229dfa91f6f3d62ada28f4725f5a89.image.png)

> ![image.png](/static/img/3ee3e823c68d87b9bed673e27fb70a6d.image.png)

## 正规式

正规式是对有限自动机的另外一种表达形式

![image.png](/static/img/a24f7f3a0bc4b6a60a6f90a79fa30e50.image.png)

`*` 表示循环多次

> ![image.png](/static/img/2b1d1c78750f4f131f4d6a47e2d4342e.image.png)

## 表达式

![image.png](/static/img/69a5079bca234be1dfa22920dc7cfed4.image.png)

![image.png](/static/img/5157cd19e4efb094aa48195cd41b04e6.image.png)

## 函数调用（传值与传址）

| 传递方式         | 主要特点                                                     |
| ---------------- | ------------------------------------------------------------ |
| 传值调用         | 形参取的是实参的值，形参的改变不会导致调用点所传的实参的值发生改变 |
| 引用（传址）调用 | 形参取的是实参的地址，即相当于实参存储单元的地址引用，因此其值改变的同时就改变了实参的值 |

## 各种程序语言特点

![image.png](/static/img/b06ef088c824dcf2371ab89500f68574.image.png)

软件设计师07-程序设计语言与语言处理程序基础

## 数组

| 数组类型          | 存储地址计算                                                 |
| ----------------- | ------------------------------------------------------------ |
| 一维数组`a[n]`    | `a[i]`的存储地址为：`a + i * len`                            |
| 二维数组`a[m][n]` | `a[i][j]`的存储地址（按行存储）：`a + (i * n + j) * len`<br />`a[i][j]`的存储地址（按列存储）：`a + (j * m + i) * len` |



![image.png](/static/img/4490fb2f7a0fef4b91dad30021a16b68.image.png)

## 稀疏矩阵

一个矩阵中存储的大量元素是0

| 稀疏矩阵   | 示意图                                                       | 要点                                                         |
| ---------- | ------------------------------------------------------------ | ------------------------------------------------------------ |
| 上三角矩阵 | ![image.png](/static/img/b4aa95b4d24446901dfa89b78fa16701.image.png) | 在矩阵中下标分别为 `i` 和 `j` 的元素，对应的一维数组的下标计算公式为：$(2n-i+1) \times i \div 2 + j$ |
| 下三角矩阵 | ![image.png](/static/img/13a94c2bd233cc765354e7b475a519f7.image.png) | 在矩阵中下标分别为 `i` 和 `j` 的元素，对应的一维数组的下标计算公式为：$(i+1) \times i \div 2 + j$ |

考试中常用代入法：

![image.png](/static/img/5944f02b7771ca852f76c8cfd8d97bb4.image.png)

## 数据结构的定义

数据结构是相互之间存在一种或多种特定关系的数据元素的集合，是一种数据组织、管理和存储的格式。

逻辑结构：线性结构、非线性结构（树、图）

![image.png](/static/img/fdbe969218e0d7bf1e76ea5261b24c95.image.png)

## 线性表

线性结构的基本表现，分顺序存储结构（顺序表）和链式存储结构（链表）

![image.png](/static/img/633148a148aa9652a51ad6f86860314c.image.png)

![image.png](/static/img/03c9e0dbf8df92661e14bc3ca8a82112.image.png)

顺序存储与链式存储对比：

![image.png](/static/img/a0cec6ea08d9492784eaf04f31c40ff2.image.png)

## 队列与栈

![image.png](/static/img/568d0a12e33a88987a230c518a1ea7ff.image.png)

> 元素按照a、b、c的次序进入栈，写出所有可能的出栈序列：
>
> - a进，a出，b进，b出，c进，c出，顺序：a，b，c
> - a进，b进，b出，a出，c进，c出，顺序：b，a，c
> - a进，b进，c进，c出，b出，a出，顺序：c，b，a
> - a进，a出，b进，c进，c出，b出，顺序：a，c，b
> - a进，b进，b出，c进，c出，a出，顺序：b，c，a

![image.png](/static/img/616402ad178f527f978b7aba90e3f4de.image.png)

## 广义表

广义表是由n个表元素组成的有限序列，是线性表的推广

通常用递归的形式进行定义，记作：$LS=(a_{0}, a_{1}, ...,a_{n})$

LS是表名，$a_{i}$是表元素，可以是表（称作子表），也可以是数据元素（称作原子），n是广义表的长度（最外层包含的元素个数）

n=0的广义表为空表，递归定义的重数是广义表的深度，简单来说就是定义中所含括号的重数（原子的深度为0，空表的深度为1），也就是嵌套层数

基本运算：取表头head(Ls)和取表尾tail(Ls)，

若有：`LS1=(a, (b, c), (d, e))`，则 `head(LS1) = a`，`tail(LS1) = ((b, c), (d, e))`

![image.png](/static/img/c3031435a00013d58045018de8d93f75.image.png)

## 树与二叉树

### 基本概念

![image.png](/static/img/161418e52756334a788181ac8a763695.image.png)

- 结点的度：结点拥有的孩子数
- 树的度：所有结点中最高的度
- 叶子结点：没有孩子结点的结点
- 分支结点：有分支的结点
- 内部结点：不是根节点和叶子结点
- 父结点、子结点、兄弟结点
- 层次

### 二叉树

几种特殊的二叉树：

![image.png](/static/img/e5a315e054f2a2de17ba9e54b0a05063.image.png)

二叉树的重要特性：

![image.png](/static/img/c93a4bd45695dd0f775b54e49087145e.image.png)

### 二叉树的遍历

![image.png](/static/img/93793f3c06e4671ffc34b31895696b37.image.png)

#### 层次遍历

按层进行遍历：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

### 反向构造二叉树

知道一定的二叉树的遍历序列，反向推出二叉树的情况

![image.png](/static/img/c2d39956cbf093880e50c065158ec6da.image.png)

### 树转二叉树

基本原则：

- 孩子结点→左子树结点（只取最左边的作为左子树结点）
- 兄弟结点→右子树结点
- 可以用连线法简化转换流程

![image.png](/static/img/dd2a9356d6daf90d02e7417269151761.image.png)

### 查找二叉树（二叉排序树）

一类比较特殊的二叉树

- 左孩子小于根
- 右孩子大于根

![image.png](/static/img/b27a8ebbb90e6df97d4fce3fb0e25d4e.image.png)

插入结点：

1. 若该键值结点已存在，则不再插入
2. 若查找二叉树为空树，则以新结点为查找二叉树
3. 将要插入结点键值与插入后父结点键值比较，就能确定新结点是父结点的左子结点还是右子结点

删除结点：

1. 若待删除结点是叶子结点，则直接删除
2. 若待删除结点只有一个子结点，则将这个子结点与待删除结点的父结点直接连接
3. 若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找键值最大的结点s，用结点s的值代替结点p的值，然后删除结点s，结点s必属于以上两种情况之一

### 最优二叉树（哈夫曼树）

用于哈夫曼编码，让原始信息的编码长度变得更短，属于无损压缩

- 树的路径长度
- 权：结点的值
- 带权路径长度：`权*路径长度`
- 树的带权路径长度（树的代价）：所有叶子结点带权路径长度的累加

构造一个哈夫曼树要达到的效果是树的带权路径长度最短

![image.png](/static/img/02d673d8e14879e2083c583e0c480eb1.image.png)

### 线索二叉树

![image.png](/static/img/d9d0a8b1caa63c6d09bedb3cc5d0fa9c.image.png)

目的：将空闲的结点分支利用起来，方便遍历，左子树结点指向对应遍历顺序的前序结点，右子树结点指向对应遍历顺序的后序结点

### 平衡二叉树

![image.png](/static/img/45e53bc6b5ddc522da3f4a0910b86db8.image.png)

平衡度：左子树深度-右子树深度，所有叶子结点的平衡度都是0

## 图

### 基本概念

- 有向图：边有方向
- 无向图：边没有方向
- 完全图：无向图每对顶点间都有一条边相连，有向图每对顶点间都有两条有向边相互连接

![image.png](/static/img/8f825ea931eae85e6005720fff8c54a8.image.png)

### 图的存储

#### 邻接矩阵

用一个n阶方阵R来存放图中各结点的关联信息

对于无向图，邻接矩阵为了节省存储空间，可以只存上三角或下三角

![image.png](/static/img/62e3541261f8ff6a5c90a4c3a0af82b1.image.png)

#### 邻接表

首先把每个顶点的邻接顶点用链表示出来，然后用一个一维数组来顺序存储上面每个链表的头指针

![image.png](/static/img/c149cae2898f94eacccd2d976ea3eed3.image.png)

### 图的遍历

![image.png](/static/img/0d7d299a83f220b187bb01030c7a8902.image.png)

#### 深度优先遍历DFS

1. 首先访问出发顶点V
2. 依次从V出发搜索V的任意一个邻接点W
3. 若W未访问过，则从该点出发继续深度优先遍历

类似于树的前序遍历

V1，V2，V4，V8，V5，V3，V6，V7

#### 广度优先遍历BFS

1. 首先访问出发顶点V
2. 然后访问与顶点V邻接的全部未访问顶点W、X、Y...
3. 然后再依次访问W、X、Y...邻接的未访问顶点

V1，V2，V3，V4，V5，V6，V7，V8

### 拓扑排序

用一个序列来表达一个图中哪些序列可以先执行，哪些序列可以后执行

把有向边表示活动之间开始的先后关系，这种有向图称为用顶点表示活动网络，简称AOV网络

![image.png](/static/img/0b486202c2ff213b674063148eb34f9a.image.png)

### 图的最小生成树

把图中的边只留下若干条权值最小的，能够把所有顶点连接起来，成为一棵树

#### 普利姆算法

基本思想：从任意一个结点出发，将其定为红点集，其它为蓝点集，选出一条从红点集到蓝点集最短距离的边，并将连接到的点纳入红点集，重复进行

![image.png](/static/img/25790710b32578aa017aa29148a960dd.image.png)

#### 克鲁斯卡尔算法

首先确定选几条边，然后从最短的边开始选起，但不能选边之后成环

![image.png](/static/img/9f91567280acdc748c4424af8ecfcd9d.image.png)

## 算法基础

### 算法的特性

- 有穷性：执行有穷步后结束
- 确定性：算法中每一条指令都必须有确切的含义，不能含糊不清
- 输入：≥0
- 输出：≥1
- 有效性：算法的每个步骤都能有效执行并能得到确定的结果

### 算法的复杂度

时间复杂度：程序运行从开始到结束所需要的时间

空间复杂度：一个算法在运行过程中临时占用存储空间大小的度量

一般来说，算法中原操作重复执行的次数是规模n的某个函数$T(n)$，由于许多情况下要精确计算$T(n)$是困难的，因此引入了渐进时间复杂度在数量上估计一个算法的执行时间

如果存在两个常数$c$和$m$，对于所有的$n$，当$n \geq m$时有$f(n) \leq cg(n)$，则有$f(n) = O(g(n))$。也就是说，随着$n$的增大，$f(n)$渐进地不大于$g(n)$。例如，一个程序的实际执行时间为$T(n) = 3n^3+2n^2+n$，则$T(n)=O(n^3)$

常见的对算法执行所需时间的度量：
$$
O(1) < O(log_2n) < O(n) < O(nlog_2n) < O(n^2) < O(n^3) < O(2^n)
$$
$O(log_2n)$多用于树中

## 查找

### 顺序查找

从头到尾进行比较，若存在则成功

查找成功时，顺序查找的平均查找长度为（等概率情况下）：
$$
ASL = \sum^n_{i=1}{P_i \times (n-i+1)} = \frac{1+2+L+n}{n} = \frac{n+1}{2}
$$
时间复杂度为$O(n)$

### 二分查找

前提：序列是有序的

mid为小数是向下取整

![image.png](/static/img/807e14bfb47a1848b465be886bf62200.image.png)

![image.png](/static/img/e1c7121bc7ec32234f678212abfe8495.image.png)

二分查找在查找成功时关键字的比较次数最多为$\lfloor log_2n \rfloor + 1$次

二分查找的时间复杂度为$O(log_2n)$

### 散列表

基本思想：已知关键字集合U，最大关键字为m，设计一个函数Hash，它以关键字为自变量，关键字的存储地址为因变量，将关键字映射到一个有限的、地址连续的区间T[0..n-1]（n<<m）中，这个区间就称为散列表，散列查找中使用的转换函数称为散列函数

![image.png](/static/img/4c30b636d34e78b656d3f46bef80b948.image.png)

散列表冲突的解决方法：线性探测法、伪随机数法

## 排序

![image.png](/static/img/119b69e3f77f130abfb101ab7e0c7082.image.png)

稳定排序：相同的元素在排序后的相对位置不变

内排序：在内存中的排序

### 直接插入排序

当插入第i个记录时，R1，R2，...，Ri-1已经排好序，因此Ri与他们进行比较，找到合适的位置插入，速度很慢

![image.png](/static/img/0381c7c74f3793ca4ade3e86a7474fd0.image.png)

### 希尔排序

希尔（Shell）排序：先取一个小于n的整数$d_1$作为第一个增量，把文件的全部记录分成$d_1$个组。所有距离为$d_1$的倍数的记录放在同一个组中。先在各组内进行直接插入排序，然后去第二个增量$d_2 < d_1$重复上述的分组和排序，直至所取的增量$d_t=1(d_t<d_{t-1}<O<d_2<d_1)$，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法，比直接插入排序快

![image.png](/static/img/d87767af89fc27d38ea38d4ab14f553b.image.png)

### 直接选择排序

首先在所有记录中选出最小的记录，把它与第1个记录交换，接下来从剩下的纪录中选出最小的与第2个记录交换，以此类推

![image.png](/static/img/160fd47e7d0c54a8769fb5a47c115622.image.png)

### 堆排序

所有排序算法中最复杂的算法

堆：

![image.png](/static/img/ecc70bd9b1ac9078cdc6a60f238c6c0d.image.png)

先将序列建立堆，然后输出堆顶元素，再将剩余元素建立堆，输出堆顶元素

![image.png](/static/img/6d020faddb50b6de2ea9c00d5a5d612a.image.png)

初建堆的过程：从最后一个非叶子结点开始调整，与其子结点比较大小

![image.png](/static/img/e17b24e0d334081c864307709af851ba.image.png)

排序过程：

![image.png](/static/img/9bf1634603c67079a093a949f42470b8.image.png)

效率比直接选择排序高，应用场景在取前n个排序后元素

### 冒泡排序

通过相邻元素之间的比较和交换，将排序码较小的元素逐渐从底部移到顶部

![image.png](/static/img/224a69d6628c71197ac725b4a8c781aa.image.png)

### 快速排序

采用分治法，基本思想是将原问题分解成若干个规模更小但结构与原问题相似的子问题，递归地解决子问题

1. 在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录都分成两组，第一组都小于该数，第二组都大于该数
2. 采用相同的方法对左右两组分别进行排序，直到所有记录都排到相应的位置为止

![image.png](/static/img/c81ef0fd09f67b25ac52a9cfd674d17c.image.png)

### 归并排序

把两个或两个以上有序子表合并成一个新的有序表

若只合并两个，称为二路合并

合并过程：比较`A[i]`和`A[j]`的排序码大小，若`A[i]`的排序码小于等于`A[j]`的排序码，则将第一个有序表中的元素`A[i]`复制到`R[k]`中，并令i和k分别加1，如此循环下去，知道其中一个有序表比较和复制完，然后再将另一个有序表的剩余元素复制到R中

![image.png](/static/img/9f23a475a252554fa63a9142d0a88519.image.png)

### 基数排序

借助多关键字排序思想对但逻辑关键字进行排序的方法。适合于元素很多而关键字较少的序列

基数的选择和关键字的分解是根据关键字的类型来决定的，例如关键字是十进制数，则按个位、十位、百位来分解

![image.png](/static/img/9e5997fa9a96b568c9e7e24b80f7320b.image.png)

### 排序算法的比较（重要）

![image.png](/static/img/1cc40933ae573b372f659f4d3dc2022d.image.png)

软件设计师06-数据结构与算法基础

## 信息系统安全属性

1. 保密性：最小授权原则、防暴露、信息加密、物理加密
2. 完整性：安全协议、校验码、密码校验、数字签名、公证
3. 可用性：综合保障（IP过滤、业务流控制、路由选择控制、审计跟踪）
4. 不可抵赖性：数字签名

## 对称加密与非对称加密

### 对称加密

加密与解密时密钥完全相同

缺陷：

1. 加密强度不高
2. 密钥分发困难



![image.png](/static/img/35f17642a1adf14b0596e0ce5f4374b5.image.png)

### 非对称加密

加密密钥与解密密钥不同，分公钥和私钥

缺陷：加密速度慢

![image.png](/static/img/6e7d03fe5947fa3d5b419b18aa16aa6e.image.png)

## 信息摘要

信息摘要是一段信息的特征值，信息发生变化，特征值也变化

单向散列函数（单向Hash函数）、固定长度的散列值

常用的信息摘要算法：MD5、SHA等，SHA散列值分别为128位和160位，由于SHA通常采用的密钥长度较长，因此安全性高于MD5

## 数字签名

防抵债技术

通常首先产生摘要，然后进行数字签名，接收后进行数字签名的验证过程，得到摘要，与接收到的信息产生的摘要进行比对

![image.png](/static/img/ff74bc71d37d888758c6c1888434114e.image.png)

## 数字证书（数字信封）与PGP

发送方将原文用对称密钥加密传输，而将对称密钥用接收方公钥加密发送给对方

接收方收到电子信封，用自己的私钥解密信封，取出对称密钥解密得原文

![image.png](/static/img/1e5075a2a2b5e2723635dd518901c512.image.png)

## 练习题：设计邮件加密系统

要求：邮件以加密方式传输，邮件最大附件内容可达500MB，发送者不可抵赖，若邮件被第三方截获，第三方无法篡改

![image.png](/static/img/17e748ef45f47c31dbdaf3a1c8af6945.image.png)

## 各个网络层次的安全保障

![image.png](/static/img/d7b6fab92c124bb0af02fdb4066f8cb2.image.png)

## 网络威胁与攻击

| 威胁名称         | 描述                                                         |
| ---------------- | ------------------------------------------------------------ |
| 重放攻击（ARP）  | 所截获的某次合法的通信数据拷贝，出于非法的目的而被重新发送   |
| 拒绝服务（DOS）  | 对信息或其它资源的合法访问被无条件地阻止                     |
| 窃听             | 用各种可能的合法或非法的手段窃取系统中的信息资源和敏感信息。例如对通信线路中传输的信号进行搭线监听，或者利用通信设备在工作过程中产生的电磁泄露截取有用信息等 |
| 业务流分析       | 通过对系统进行长期监听，利用统计分析方法对诸如通信频度、通信的信息流向、通信总量的变化等参数进行研究，从而发现有价值的信息和规律 |
| 信息泄露         | 信息被泄露或透露给某个非授权的实体                           |
| 破坏信息的完整性 | 数据被非授权地进行增删、修改或破坏而受到损失                 |
| 非授权访问       | 某一资源被某个非授权的人、或以非授权的方式使用               |
| 假冒             | 通过欺骗通信系统（或用户）达到非法用户冒充成为合法用户，或者特权小的用户冒充成为特权大的用户的目的。黑客大多是采用假冒进行攻击 |
| 旁路控制         | 攻击者利用系统的安全缺陷或安全性上的脆弱之处获得非授权的权利或特权。例如，攻击者通过各种攻击手段发现原本应保密，但是却又暴露出来的一些系统“特性”。利用这些“特性”，攻击者可以绕过防线守卫者侵入系统的内部 |
| 授权侵犯         | 被授权以某一目的使用某一系统或资源的某个人，却将此权限用于其它非授权的目的，也称作“内部攻击” |
| 特洛伊木马       | 软件中含有一个察觉不出的或者无害的程序段，当它被执行时，会破坏用户的安全 |
| 陷阱门           | 在某个系统或某个部件中设置了“机关”，使得当提供特定的输入数据时允许违反安全策略 |
| 抵赖             | 这是一种来自用户的共计，比如：否认自己曾经发布过的某条消息、伪造一份对方来信等 |

## 防火墙技术

![image.png](/static/img/8faa599ecdb8763f46a2be30d8e4c012.image.png)

软件设计师05-系统安全分析与设计

## OSI七层模型

![image.png](/static/img/b7fc5a69a76e103c5ba77cccc32f02bb.image.png)



跨越了网络层，往往就不属于同一个局域网，就不能通过了

![image.png](/static/img/9e6ff6698d149d35342c4a84978be897.image.png)

## 网络技术标准与协议

![image.png](/static/img/b22bf96995834154c077eb99b6c5f405.image.png)

TCP：可靠协议，UDP：不可靠协议

ARP：将IP转换为MAC的协议

### TCP

![image.png](/static/img/307962231ab8b4fb64e362fe8925308a.image.png)

### DHCP

![image.png](/static/img/7861902f0951c6e4ecfe590627d8981b.image.png)

`169.254.*.*`（Windows）、`0.0.0.0`（Linux）：分配没有成功，可能是DHCP服务器故障或客户机没有与服务器联系上

### DNS

![image.png](/static/img/1066bfdc9a30a19403be18ad4064643d.image.png)

![image.png](/static/img/c9f0b0ba723d879305a1c3ff2af5d5be.image.png)

![image.png](/static/img/392093eda627cf935ba9c88ccfe30976.image.png)

SNMP：简单网络管理协议

Samba、CIFS：NFS：文件共享协议

## 网络类型与拓扑结构

![image.png](/static/img/b12e6a358418b4179a290f0476a30e8e.image.png)

星型存在单点故障问题，环型在可靠性上占有优势

办公室里的组网往往走的是星型结构

## 网络规划与设计

![image.png](/static/img/a0a6b4971c0bacf0a822133f7636f03f.image.png)

先进性原则：在考虑实用性和开放性的基础上采用更为先进的设备，而不是始终采用新型设备

逻辑网络设计：

- 逻辑网络设计图
- IP地址方案
- 安全方案
- 具体的软硬件、广域网连接设备和基本服务
- 招聘和培训网络员工的具体说明
- 对软硬件、服务、员工和培训的费用初步估计

物理网络设计：

- 网络物理结构图和布线方案
- 设备和部件的详细列表清单
- 软硬件和安装费用的估算
- 安装日程表，详细说明服务的时间以及期限
- 安装后的测试计划
- 用户的培训计划

分层设计：

- 接入层：向本地网段提供用户接入
- 汇聚层：网络访问策略控制、数据包处理、过滤、寻址
- 核心层：数据交换、转发，要求设备性能较高，可靠性较高，经常进行冗余设计

![image.png](/static/img/194916f83b5846f2e25105dc754b5a1a.image.png)

## IP地址与子网划分

![image.png](/static/img/3b8a5c99a1a414aaa50053e193a07cfa.image.png)

A类地址规定第一段是网络号，后三段是主机号，一个A类网络里包含的网络地址数量是$2^{24}-2$个，减掉的2是全0的地址和全1的地址

B类地址规定前两段是网络号，后两段是主机号，容纳的主机数是$2^{16}-2$个

C类地址规定前三段是网络号，第四段是主机号，容纳的主机数是$2^8-2$个



第一阶段：直接划分IP地址

第二阶段：子网划分阶段

第三阶段：打破原来的地址分类概念，形成无分类网络概念，无类域间路由

`172.18.129.0/24`，`/24`代表的是ip地址转成二进制后，前面的24个bit位是网络号，这意味着后8个位是主机号，所以能容纳的主机数是254台

`/20`代表的是ip地址转成二进制后，前面的20个bit位是网络号，这意味着后12个位是主机号，所以能容纳的主机数是$2^{12}-2$台

考试时，常考的是给出一个场景，来做网络划分或超网（把多个网络汇聚起来形成一个更大的网络）



子网划分：

- 子网掩码（区分一个ip地址哪些部分是网络号，哪些部分是主机号）
- 将一个网络划分成多个子网（取部分主机号当子网号）
- 将多个网络合并成一个大的网络（取部分网络号当主机号）

取k个bit位会得到N个子网，$2^k=N$（主机位同理），以前的旧设备不支持把全0和全1的地址识别出来用，则是$2^k-2=N$

![image.png](/static/img/c2727b632245afb2ef4d54641856a266.image.png)

![image.png](/static/img/6322ba8a4fc9f6f1c01614f3f046b1a7.image.png)

无分类编址：

![image.png](/static/img/46e190ff2c6de955a67ced64b22eea4b.image.png)

![image.png](/static/img/c34426dcd2a7b58ef07cd4242fa959af.image.png)

前20位是网络号，后12位是主机号，C类子网前24位是网络号，后8位是主机号，还可以从主机号拿出4个位来作子网号，也就是$2^4=16$个C类子网

## 特殊含义IP地址

![image.png](/static/img/b131a68f164ad4d2c59cc2d020b7d8c1.image.png)

## HTML

超文本标记语言

![image.png](/static/img/bb2c31c32610050082483af8e06d898f.image.png)

## 无线网

![image.png](/static/img/9865dde781663df4e8c026b950ae4dfb.image.png)

## 网络接入技术

![image.png](/static/img/e3617c0f31ba03224cc93590243bee44.image.png)

## IPv6

用于替代现行版本IP协议（IPv4）的下一代IP协议

![image.png](/static/img/a3390bc7d6135f88c52cb5147c8fda03.image.png)

- 单播地址（Unicast）：用于单个接口的标识符
- 任播地址（Anycast）：泛播地址。一组接口的标识符，IPv4广播地址
- 组播地址（Multicast）：IPv6中的组播在功能上与IPv4中的组播类似

软件设计师04-计算机网络

## 数据库模式

三级模式 - 两级映射

![image.png](/static/img/26e039bc980bf696c117176f3ca9288b.image.png)



## 数据库设计

### 数据库设计过程

![image.png](/static/img/b83c9abec9de77bcfc5818fc65b2c89d.image.png)

### E-R模型

![image.png](/static/img/119fabf434ef4ef36086f4b7dda74c14.image.png)

集成的方法：

- 多个局部E-R图一次集成
- 逐步集成，用累加的方式一次集成两个局部E-R图

集成产生的冲突及解决办法：

- 属性冲突：包括属性域冲突和属性取值冲突
- 命名冲突：包括同名异义和异名同义
- 结构冲突：包括同一对象在不同应用中具有不同的抽象，以及同一实体在不同局部E-R图中所包含的属性个数和属性排列次序不完全相同

E-R模型转关系模式：

- 一个实体型转换为一个关系模式
  - 一对一、一对多：联系可以转成一个关系模式，也可以合并进多
  - 多对多：联系必须转成一个关系模式
- 三个以上实体间的一个多元联系

![image.png](/static/img/f73dc1edbe7f7b05615785358619aade.image.png)

### 关系代数

- 并
- 交
- 差
- 笛卡尔积
- 投影
- 选择
- 联接

### 规范化理论

#### 函数依赖

设R(U)是属性U上的一个关系模式，X和Y是U的子集，r为R的任一关系，如果对于r中的任意两个元组u，v，只要有u[X]=v[X]，就有u[Y]=v[Y]，则称X函数决定Y，或称Y函数依赖于X，记为X→Y

![image.png](/static/img/e69d2ab0f90f9cf4f9b18d83a6611516.image.png)

#### 价值与用途

非规范化的关系模式，可能存在数据冗余、更新异常、插入异常、删除异常等问题

#### 键

![image.png](/static/img/c1c50971bad49f4ce52e66a478ad771f.image.png)

例：学号能确定性别，学号和姓名的组合键也能确定性别，则学号和姓名的组合键为超键，但不是候选键，消除多余属性后，学号为候选键

候选键可以有多个，主键只有一个

**求候选键**

![image.png](/static/img/bbf4ef6dedac814e57f84e773ecdb5da.image.png)

![image.png](/static/img/1b648b7a2759f83583aaf9cf7458b5b7.image.png)

#### 范式（必考）

结合函数依赖和候选键的求解学习

![image.png](/static/img/346fade43d1b067a0d331c8e0affcbb3.image.png)

规范化程度越高，数据密度越小

第一范式：所有域只包含原子值，即每个分量都是不可再分数据项

![image.png](/static/img/fa643db7782c1a1bd805c0f778ae7e9b.image.png)

第二范式：第一范式，且每一个非主属性完全依赖主键（不存在部份依赖），带来的问题：数据冗余、更新异常、插入异常、删除异常，解决方法：把部份依赖提取出来，形成新的关系模式

![image.png](/static/img/c69690bc22ff5284f455a9da0003173f.image.png)

主属性：SNO，CNO，非主属性：GRADE，CREDIT

第三范式：第一范式，且没有非主属性传递依赖

![image.png](/static/img/d7b5e91ea9827fb88a9ce8608f280a08.image.png)

BC范式：设R是一个关系模式，F是它的依赖集，R属于BCNF当且仅当其F中每个依赖的决定因素必定包含R的某个候选码

![image.png](/static/img/d49df49459cc4c7b01cae905ff8ae5d3.image.png)

存在函数依赖：SJ→T，T→J，SJ是候选键，但T不是候选键，所以该关系模式没有达到BC范式的要求


> 例题
>
> ![image.png](/static/img/f1148eea80d9514ca9c2f2d87ce097e1.image.png)

#### 模式分解

![image.png](/static/img/fbfabe1f2a6ce80f0882ee1a97d9507a.image.png)

![image.png](/static/img/04aeba40426f3f44cdfa7b9ca126eb66.image.png)

表格法：

![image.png](/static/img/de6374cb762acab1d0227c618f742820.image.png)

![image.png](/static/img/fc071da9915cbe727b56b4f7c7104bd5.image.png)

公式法（局限性较强，只适合于一分为二的情况）进行集合运算：

![image.png](/static/img/c3d25432148e01844fa5b0526ba56cdd.image.png)

## 数据库并发控制

![image.png](/static/img/41fad04bcc5a675655a92c11bf4847a7.image.png)

![image.png](/static/img/a4b64b9cb9584a22925accee721c0217.image.png)

- 一级封锁协议：事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放，**可防止丢失修改**
- 二级封锁协议：一级封锁协议加上事务T在读取数据R之前先对其加S锁，读完后即可释放S锁，**可防止丢失修改，可防止读“脏”数据**
- 三级封锁协议：一级封锁协议加上事务T在读取数据R之前先对其加S锁，直到事务结束才释放。**可防止丢失修改、读“脏”数据和数据重复读**
- 两段锁协议：可串行化的，可能发生死锁

## 数据库完整性约束

- 实体完整性约束（主键）
- 参照完整性约束（外键）
- 用户自定义完整性约束

提高数据可靠性的一种机制，只能应对简单情况

应对复杂情况：触发器，可以编写脚本

## 数据库安全

| 措施           | 说明                                                         |
| -------------- | ------------------------------------------------------------ |
| 用户标识和鉴定 | 最外层的安全保护措施，可以使用用户账户、口令及随机数检验等方式 |
| 存取控制       | 对用户进行授权，包括操作类型（如查找、插入、删除、修改等动作）和数据对象（主要是数据范围）的权限 |
| 密码存储和传输 | 对远程终端信息用密码传输                                     |
| 视图的保护     | 对视图进行授权                                               |
| 审计           | 使用一个专用文件或数据库，自动将用户对数据库的所有操作记录下来 |

## 数据备份与恢复

- 冷备份：静态备份，将数据库正常关闭，在停止状态下将数据库文件全部备份（复制）下来（操作较简单）
- 热备份：动态备份，利用备份软件在数据库正常运行的状态下将数据库中的数据文件备份出来（灵活度高一些，较复杂，容错率低）

![image.png](/static/img/6dcdc496a875d89fd4e18be7705d88a5.image.png)

- 完全备份：备份所有数据
- 差量备份：**仅备份上一次完全备份之后变化的数据**
- 增量备份：备份上一次备份之后变化的数据

![image.png](/static/img/c0b2b12eccefb621a695ceee928a42a9.image.png)

![image.png](/static/img/9f3944e5abc0fa20afcca0a88380a76d.image.png)

## 数据仓库与数据挖掘

![image.png](/static/img/e158cae4bcae9744a65b26b67aade688.image.png)

![image.png](/static/img/465d94f9ca4c5aa686e1dd46d477ea68.image.png)

## 反规范化技术

![image.png](/static/img/ba31e73d35c544fc8a6a4b5fa3ebb1ae.image.png)

## 大数据

![image.png](/static/img/e256780e6c71f6fb927ee57f54f897b9.image.png)

![image.png](/static/img/f7d9c173757619bbb7fbdbd324b75d7e.image.png)

数组类型	存储地址计算
一维数组`a[n]`	`a[i]`的存储地址为：`a + i * len`
二维数组`a[m][n]`	`a[i][j]`的存储地址（按行存储）：`a + (i * n + j) * len` `a[i][j]`的存储地址（按列存储）：`a + (j * m + i) * len`