408笔记完整考点篇

数据结构

时间复杂度

线性表：

具有随机存储特性，查找时间复杂度为O(1)

单链表-尾插法?

栈及其应用

根据限定条件判断合法性；最小容量；表达式求值；中缀表达式转化为后缀表达式过程

应用：数制转换、括号匹配、表达式求值（中缀表达式、后缀表达式）、递归调用等

循环队列（两种情况

输入/输出受限的双端队列?

特殊矩阵的压缩存储*

树

树的高度：log2(n)+1

节点数等于所有节点度加一 >> 节点为n，度数和为n-1;
度为m的树中，第i层之多有m^(i-1)个节点
高度为h的m叉树至多有(m^h-1)(m-1)个节点
具有n个节点的m叉树最小高度为[logm( n(m-1)+1 )]上取整

二叉树特性

n0=n2+1
k层至多有2^(k-1)个结点
高度为h，至多有2^h - 1个结点
具有n个结点的完全二叉树高度为log2n + 1

二叉树的遍历、编码

先序、中序、后序遍历

层次遍历：利用队列实现

线索二叉树：若无左子树，令左孩子指向前驱节点；若无右子树，令右孩子指向后继节点

数的存储结构

双亲表示法：表格形式

孩子表示法：表格链表形式

孩子兄弟表示法：二叉链表进行存储

二叉排序树：从左到右大小排序

查找

插入（构造

平衡二叉树

在这里插入图片描述

树与森林

相互转换：根节点当做兄弟节点，再用孩子兄弟表示法

树的应用：并查集?

线索二叉树（空地放前后端点链接

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

在这里插入图片描述

哈夫曼编码：使用不等长编码，减少信息存储量；0转向左孩子，1转向右孩子

在这里插入图片描述

图

( , )无向图，< , >有向图

图的存储

1.邻接矩阵法：适合稠密图

2.邻接表法

3.邻接多重表、十字链表

图的遍历

深度优先搜索

在这里插入图片描述

广度优先搜索

在这里插入图片描述

图的应用

最小(代价)生成树

最小生成树不唯一，最小生成树代价唯一

kruskal 算法

按照权值递增顺序依次构造边

prim 算法（基于贪心算法

在这里插入图片描述

最短路径

迪杰斯特拉算法解决单元最短路径问题

? 创建定点的距离表，根据不同深度不断更新距离表

在这里插入图片描述

Floyd算法解决各顶点之间最短路径问题

拓扑排序

不存在回路就能构造

原理：找一个没有前驱的节点输出，并删去该节点

AOV网：数据在顶点（面向对象

在这里插入图片描述

关键路径

e(i)=max{}; l(i)=min{};

AOE网：数据在边上（面向过程

只有关键路径上的活动时间同时减少时，才能缩短工期

关键活动：最迟开始时间 l(i) - 最早开始时间 e(i) = 0

查找

顺序查找

分块查找（索引顺序查找

折半查找

high=mid-1； low=mid+1；仅适用于有序的顺序表

int Binary_Search(SeqList L,ElemType key,int n){
	int low=0,high=n-1,mid; 
               while(low<=high){
                              mid=(low+high)/2; 		
		if(L.elem[mid]==key)            
			return  mid;		
		else if(L.elem[mid]>key)       
			high=mid-1;		
		else      low=mid+1;	
	}
	return  -1;
}

二叉排序树

BiTNode *BST_Search(BiTNode *t,ElemType key){
		if(t==NULL)return NULL;
    	else{
            if(t->key=key)return t;
            else if(key < t->key)return BST_Search(t->t->lchild,key);
            else return BST_Search(t->rchild,key);
        }
}

B树、B+树

B+树有两种查找方式，一种从上往下，一种从根节点开始的依次查找

B-树?

查找

插入

删除

散列表：散列函数是关键

除留余数法 、数字分析法、平方取中法

处理冲突：开放定址法、拉链法?

在这里插入图片描述

模式匹配?

KMP

next值计算

nextval计算

排序

对大多数内部排序仅适用于顺序存储结构

插入排序

直接插入排序

折半插入排序

希尔排序

切割子表，对每个子表进行插入排序；通过对原始数组预处理使得数组大体有序，使得最终的插入排序变得简单

在这里插入图片描述

交换排序

冒泡排序

快速排序：双指针（最好的内部排序

内部排序中平均性能最优

在这里插入图片描述

选择排序

选择最小的放前面、不稳定，可能会导致相同元素的相对位置发生变化

堆排序

删除节点时，将最后一个元素放在顶部，再逐步下沉

大根堆：从第一个非叶子节点开始构造

在这里插入图片描述

二路归并排序

在这里插入图片描述

基数排序

MSD: 最高为优先；LSD：最低位优先

内部排序比较

外部排序*(新增考点

归并排序

在这里插入图片描述

多路平衡树与败者树

? 胜者树与败者树：败者树可以加快合并序列，减小归并路数k增大的影响

在这里插入图片描述

置换-选择排序

? 生成初始归并段

在这里插入图片描述

最佳归并树

? 组织初始归并段：哈夫曼树的思想，得到好的归并顺序，使得 I/o 次数最少

当初始归并段不足以构成严格k叉树时，需添加长度为0的虚段

在这里插入图片描述

设度为0的个数有n0个：

在这里插入图片描述

操作系统

概述

开机后操作系统加载到 RAM 中

批处理交互性差

现代OS两个最基本特征：并发与共享，互为存在的条件。(虚拟异步)

不属于多道程序设计的基本特征：顺序性(为单道程序设计特征，多道竞争)

内核态用户态

管态与目态

在这里插入图片描述

中断、异常

主程序调用子程序完全是软件处理过程；PSW：程序状态字寄存器

在这里插入图片描述

访管中断：需要特权指令引起的中断(自愿中断事件)，本身不是特权指令，使得用户程序能够访问管态

计算机通过硬件、中断机制完成用户态到核心态的转换，不是中断处理程序

用户态下常见指令：命令解释程序；访管指令

核心态下常见指令：进程切换；置时钟指令；广义指令(系统调用指令)；输入输出；关中断指令

进程管理

进程线程

在这里插入图片描述

进程状态和进程控制

处理机调度

在这里插入图片描述

进程同步与互斥

在这里插入图片描述

经典同步问题

死锁

内存管理

概念

连续分配管理方式

非连续分配

虚拟页式存储管理

抖动

文件管理

目录结构

文件共享与文件保护

文件的操作

文件实现

磁盘组织与管理

设备管理

IO软件的层次结构

IO调度与缓冲区

设备分配与回收

、、、、、、、、、

计算机组成原理

计算机系统层次结构

计算机性能指标

数据

数据的表示

数据的存储

定点数的表示与运算

IEEE 754标准

各种精度数据的转换

浮点数运算

存储器层次结构

半导体随机存取存储器

主存与CPU的连接

低交叉位存储器

高速缓冲存储器（CACHE

虚拟存储器

指令系统

格式

寻址方式

CISC与RISC

中央处理器

CPU功能结构

指令执行过程

数据通路功能和结构

控制器功能与原理

指令流水线

总线

总线分布

总线性能指标

总线标准

输入输出系统

外部设备

磁盘与RAID

IO接口

程序查询方式

程序中断方式

DMA方式

、、、、、、、、、、

计算机网络

1.基本概念（分层结构）

逻辑功能上可划分为：资源子网和通信子网；其中通信子网对应物理层、数据链路层、网络层
物理组成上：硬件、软件、协议
广域网、局域网区别：覆盖范围不同；协议和网络技术不同，广~采用点对点技术，局域网采用广播技术

MTU：最大传输单元，物理接口提供给上层最大传输数据大小
MSS：TCP给IP层最大分段的大小

2.物理层传输介质

? 双绞线：胶合目的：减少两根导线的电磁干扰

IEEE802.3 规定采用同轴电缆作为介质，无中继情况下，介质最大传输长度不能超过500m。

3.ISO与TCP/IP模型区别

ISO：应用层、表示层、会话层、传输层、网络层、数据链路层、物理层

TCP/IP: 应用层、传输层、网际层、网络接口层

网际层仅支持无连接，网络层支持无连接和面向连接
传输层支持无连接，ISO传输层仅支持面向连接

4.曼彻斯特编码：跃变为1

在这里插入图片描述

4B/5B Encoding

目标：如何在解决基线漂移和时钟漂移的同时，使编码效率尽量高一些
思想：在比特流中插入额外的比特而打破一连串的 0 或 1 方法：用 5 个比特来编码 4 个比特的数据，然后再传给接收方
5 比特代码由以下方式选定：每个代码最多有一个前导 0，并且末尾最多有 2 个 0 这样在连续传送时，在传输过程中任何一段 5 比特代码，连续的 0 最多有 3 个. 最后使用 NRZI 编码进行传输，就解决了问题
4B/5B 编码的效率为 80%

5.奈奎斯特定理、香农定理:

有关传输速率上限的两个定理（注：带宽——频率范围）
Nyquist 定理： D(比特率) = 2 f(带宽) log2 N(电压种数) 无噪音情况下的最大传输速率
Shannon 定理： C(比特率) = B log2 (1 + S(信号) / N(噪声)) 引入信噪比 = 10 * lg (S/N)