---

---

• 持续更新～
• 欢迎评论区留言指正
• 如果你是Obsidian用户，可以导入自己的笔记库中，效果最佳
• ⚠️如需转载，请标明出处！

---

DS 数据结构

算法题

一、快速排序

1、快排代码

①递归—>乱序数组

②关键思想：划分—>参数(数组指针、范围)

// Partitation 划分
int huafen(int A[], int L, int R) {int mid = A[L];				// 刚开始 枢轴元素的值 为 数组最左边的值while (L < R) {while (A[R] >= mid) R --;A[L] = A[R];while (A[L] <= mid)L ++;A[R] = A[L];}A[L] = mid;return L;					// 返回 L 以便于 递归地进行划分
}// 快速排序
void QuickSort(int A[], int L, int R) {if (L >= R) return;			// 递归结束int M = huafen(A, L, R);	// 定义一个 M 记录 上一层递归的枢轴元素QuickSort(A, L, M - 1);		// 左半部分 划分QuickSort(A, M + 1, R);		// 右边部分 划分
}

2、快排实战

2011-42、2013-41、2018-41、2016-43

3、运用快排的"划分"思想

例：使用"划分"函数找到数组中第k小的元素

int func(int A[], int n, int k) {int L = 0, R = n - 1, M = 0;while (1) {M = huafen (A, L, R);if (M = k - 1)break;else if (M > k - 1)R = M - 1; 			// 下标为 k - 1 的元素只能出现在左半部分else if (M < k - 1)L = M + 1;			// 下标为 k - 1 的元素只能出现在右半部分}return A[k - 1];			// 返回下标 k - 1 对应元素的值
}

⚠️复杂度：
$$\begin{gathered} 每一轮划分的时间复杂度：n+\frac{n}{2}+\frac{n}{4}+\cdot \cdot \cdot +\frac{n}{n} \\ 令n=2^x, \\ \Rightarrow 2^x+2^{x-1}+2^{x-2}+\cdot \cdot \cdot +1 \\ =\frac{1-2^{x+1}}{1-2}=2^{x+1}-1=2n-1 \\ \Rightarrow 总体时间复杂度O(2n+1)=O(n) \\ 空间复杂度O(1) \end{gathered}$$

实战：8.3.3 大题 2

2016-43

二、二路归并排序

0、回顾

1、二路归并 VS 快速排序

2、二归实战

①基本功

②2011-42

三、链表(2.3课后习题)

0、大观

1、基本功训练

①按位序查找

(1)代码

(2)实战

②按关键字条件查找+删除

③按关键字条件查找+插入

④头插法(原地逆置)

⑤尾插法(保持原序)

四、二叉树

0、大观

处理二叉树时常用的代码思路

1、基本功训练

①前/中/后序遍历(递归方法)

// 链式存储的二叉树节点定义
typedef struct BiTNode {int data;							// 数据域struct BiTNode *lchild, *rchild;	// 左右孩子指针
}BiTNode, *BiTree// 前序遍历
void PreOrder(BiTree root) {if (root == null)return;							// 根节点为空 递归结束visit(root);PreOrder(root->left);PreOrder(root->right);
}// 中序遍历
void InOrder(BiTree root) {if (root == null)return;InOrder(root->left);visit(root);InOrder(root->right);
}// 后序遍历
void PostOrder(BiTree root) {if (root == null)return;PostOrder(root->left);PostOrder(root->right);visit(root);
}

②层序遍历

// 初始化队列
void InitQueue(Queue &Q);
// 判空
bool IsEmpty(Queue &Q);
// 入队
void EnQueue(Queue &Q, BiTree T);
// 出队
void DeQueue(Queue &Q, BiTree T);// 层序遍历
void LevelOrder(BiTree T) {Queue Q;InitQueue(Q);					// 初始化队列BiTree p;							EnQueue(Q, T);					// 根节点入队while(!IsEmpty(Q)) {			// 队列非空DeQueue(Q, p);				// 队头节点出队visit(p);					// 先出队再访问if (p->lchild != null)EnQueue(Q, p->lchild);	// 左孩子入队if (p->rchild != null)EnQueue(Q, p->rchild);	// 右孩子入队}
}

③

④

⑤

⑥

⑦

⑧

2、实战

2014-41、2017-41

五、图

0、大观

1、代码

①图的数据机构定义——邻接矩阵

# define MAXV 6						// 顶点数目的最大值// 图的邻接矩阵
typedef struct {int numVertices, numEdges;		// 图的实际顶点数和边数char VerticesList[MAXV];		// 顶点表int Edge[MAXV][MAXV];			// 边表
}MGraph;MGraph * G = (MGraph *) malloc (sizeof(MGraph));
for (int i = 0; i < MAXV; i ++)for (int j = 0; j < MAXV; j ++)G->Edge[i][j] = 0;			// 408中，权值0表顶点之间没有边G->numVertices = 4;
G->numEdges = 5;
// 初始化各顶点数据
G->VerticesList[0] = 'a';
G->VerticesList[1] = 'b';
G->VerticesList[2] = 'c';
G->VerticesList[3] = 'd';
// 初始化各边数据
G->Edge[0][1] = 1;
G->Edge[0][3] = 1;
G->Edge[1][2] = 1;
G->Edge[1][3] = 1;
G->Edge[2][3] = 1;

②图的数据结构定义——邻接表

// 定义邻接表
# define MAXV 6						// 顶点数目的最大值typedef struct EdgeNode {			// 边表节点int index;						// 这条边所指向的顶点的位置struct EdgeNode *next;			// 指向下一条边的指针int weight;						// 权值(若是无权图，可删)
}EdgeNode;typedef struct VertexNode {			// 顶点表节点char data;						// 节点信息EdgeNode * first;				// 指向第一条依附该顶点的边的指针
}VertexNode, VertexList[MAXV];typedef struct {VertexList list;				// 邻接表int num Vertex, numEdge;		// 图的顶点数和边数
}ALGraph;							// ALGraph 是以邻接表存储的图// 初始化无权有向图
ALGraph * G = (ALGraph *) malloc(sizeof(ALGraph));
for (int i = 0; i < MAXV; i ++)G->List[i].first == NULL;G->numVertex = 4;
G->numEdge = 5;
G->list[0].data = 'a';
G->list[1].data = 'b';
G->list[2].data = 'c';
G->list[3].data = 'd';AddEdge(G, 0, 1, 1);
AddEdge(G, 0, 3, 1);
AddEdge(G, 1, 2, 1);
AddEdge(G, 1, 3, 1);
AddEdge(G, 2, 3, 1);// 在节点<i, j> 之间增加一条边； 边的权值为weight
void AddEdge(ALGraph * G, int i, int j, int weight) {EdgeNode * p = (EdgeNode *) malloc (sizeof(EdgeNode));p->weight = weight;p->index = j;					// 指向顶点jp->next = G.list[i].first;		// 单链表的头插法G->list[i].first = p;
}

2、实战

2021-41、2023-41

2021改、2023改

应用题

OS 操作系统

第二章 进程与线程

零、大观

复习顺序：进程的同步与互斥——>虚拟分页存储管理——>文件目录、文件的物理结构

一、PV操作

生产者-消费者问题

六步骤(草稿纸上的分析步骤)

1、有几类进程？

2、每个进程分别对应了哪些动作？

​ a. 只做一次——不加while

​ b. 不断重复——加while(1)

3、分析每一动作之前，是否需要P什么(⚠️有P必有V)

⚠️可能存在隐含的互斥

如：对缓冲区访问需加P(mutex)，保证访问的互斥性

4、所有PV操作写完后，再定义信号量

5、检查多个P连续出现的地方是否产生死锁；调整(交换)P顺序

6、检查是否符合题意

单纯的同步问题(前v后p)

哲学家进餐问题

模板题

Semaphore Lock = 1; //互斥信号量int a = 9, b = 8, c = 5; // abc三类资源，定义3个int类型信号量Process() {while(1) {P(Lock);if(所有资源都够) {所有资源 int --;取xxx资源;V(Lock);break;}V(Lock);}做进程该做的事(如：哲学家就餐)P(Lock);归还所有资源，所有资源int ++;V(Lock);
} // END

理发师问题

代码框架(较复杂情况——没有顾客，服务员睡眠休息💤)

// 初始化
int waiting = 0;
semaphore mutex = 1;			// 保证各进程对 waiting 的互斥访问
semaphore customer = 0;			// 这里 考虑 服务员 会休息
semaphore service = 0;			// 保证"被服务"与"提供服务"同步								    			// 先取号——确认有顾客——叫号——提供服务//	顾客
customer_i() {while(1) {P(mutex);				// 我们要使用 waiting 变量——需要互斥访问取号;waiting ++;V(mutex);				// 使用(修改)完 释放 mutexV(customer);			// 唤醒 服务员等待被叫号;P(service);				// 上锁之后再被提供服务——1对1——避免产生互斥被服务;}
}//	服务员
server_j() {while(1) {P(mutex);				// 需使用 waiting ——上锁if (waiting > 0) {		// 有顾客叫号;waiting --;V(mutex);V(service);提供服务;} else {V(mutex);			// 保证不存在顾客也能解锁P(customer);		// 没有顾客，服务员休息——上锁} // else_end} // while_end
}

读者-写者问题(OS结课考试会讲)

⚠️近几年从未考察，今年考察的概率很大

第三章 内存管理

一、内存管理大题

1、内存管理章节大题概念考察的很细，多听几遍OS骚图pro

2、CPU执行指令MOV[VA], 3

若

①VA = 0003 996H

②VA = FFFB 996H

③VA = 0007 996H

分别会发生什么(P2, 约1h49min28s左右)

①

②

③

CO 计算机组成原理

大致有五章(共七章)可能出现大题

大题的建议复习顺序：三—>二—>四—>五—>七

第三章 存储系统

一、Cache大题

二、TLB大题

第二章 数据的表示和运算

第四章 指令系统

一、一堆指令的执行

第五章

一、结构冒险、数据冒险和控制冒险的处理

1、结构冒险及其处理(又称结构冲突，资源冲突)

• 处理方法一：通过硬件阻塞来处理
• 处理方法二：指令Cache和数据Cache分离

2、数据冒险的分析及其处理

①分析

从某条指令开始，分析是否与其后相邻的3条指令发生写后读

②处理

• 硬件阻塞
• 转发技术(旁路)

3、控制冒险的分析及其处理

①分析

只有==转移类指令(尤指 条件转移)==的执行(阶段)才会引发控制冒险

②处理

• 硬件阻塞

  将转移类指令的后一条指令的IF段硬件阻塞3个时钟(访存阶段M会修改PC值)

  转移： IF ID EX M WB

  后一条： 阻 阻 阻 IF ID EX M WB

• 转发技术

二、五段式指令流水线

IF	ID	EX	M	WB
取指	译码/取数	执行/计算地址	访存	写回

指令按序发送，按序完成

三、一条指令的执行

1、指令执行过程

(I)取指(译码)阶段

所有指令在取指阶段的操作都相同

①根据PC从主存取指令到IR——数据流向：PC->MAR->M(MAR)->MDR->IR

②PC+"1"

• 由ALU、加法器、带"自增功能"的寄存器实现
• "1"与指令字长和编制方式(按字节编制/按字编制)有关

(II)执行阶段

学会根据指令类别思考

①数据传送类指令(如：mov、load、store)——关注数据从哪到哪？

数据只会来源于 寄存器、主存、立即数

寄—>寄

寄—>主

主—>寄

立—>寄

立—>主

寄—>暂存寄存器(某条指令的子步骤)

⚠️若有主存，则关注是 读/写主存

// 读
地址—>MAR;
M(MAR)—>MDR;	// 控制单元CU 给 主存发出读信号
MDR—>目的地;// 写
地址—>MAR;
数据—>MDR;
MDR—>M(MAR);	// CU 给 主存发出写信号

⚠️关注总线占用(总线是临界资源)，安排控制信号

②运算类指令

加、减

• ALU、加法器
• 带"自增自减"的寄存器(实现++/-- )

乘

• ALU、乘法器
• 带"移位功能"的寄存器(实现 $2^n$ 这种特殊乘法，亦可用ALU的移位功能平替)

除

• ALU、除法器
• 带"移位功能"的寄存器(实现 $2^n$ 这种特殊除法，亦可用ALU的移位功能平替)

移位

• ALU
• 带"移位功能"的寄存器

与、或、异或等双操作数逻辑运算

• ALU

非

• ALU——只需一端有输入
• 带"取反功能"的寄存器

短数—>长数

• 带"符号扩展功能"的寄存器
• 带"零扩展功能"的寄存器

③转移类指令(条件转移)——改变PC值

• 一般前置会有cmp指令(其本质是减法A-B，生成符号位CF、ZF、OF、SF)

• 原理：根据标志位判断是否转移(指令中会给出地址码)

⚠️若要转移

①注意指令寻址方式

• 相对寻址——PC+偏移量——其中偏移量可能以字/字节为单位
• 直接寻址(少见)

②注意PC的值

• 以字节为单位——CISC、RISC
• 以指令字为单位——RISC(精简指令集系统的计算机指令长度相同)

第七章 输入/输出系统

零、大观

考察年份

2010、2011、2012

2017、2018

2023(大题)、2024

一、深入理解I/O系统

PIC—可编程的中断控制器

1、从中断控制器的角度理解整个中断处理过程

2、

3、

二、Printf—从系统调用开始

1、中断隐指令与中断处理程序

中断隐指令(由硬件实现)

①保存断点和程序状态字

②将CPU模式从用户态切换为内核态

中断处理程序(由OS-软件实现)

①保存现场(保存通用寄存器中的内容)

②执行系统调用服务例程(一种特殊的中断处理程序)

sys_write可用三种I/O方式实现：程序查询、中断驱动和DMA

1、轮询(程序查询)方式下输出一个字符串

2、中断驱动方式下输出一个字符串

①中断服务程序(中断总控程序)与设备驱动程序的关系

若同时出现中断服务程序和设备驱动程序

则将中断服务程序理解为中断总控程序并与设备驱动程序区分开

3、DMA方式下输出一个字符串

三、Scanf的完整故事

sys_read用中断方式实现

1、中断驱动方式下输入一个字符串

计算机网络

二轮复习大观

1、详细描述访问WWW.xxx.com服务器资源(HTTP资源)所发生的过程

①DNS查询得到IP地址

②ARP查询得到MAC地址

​ 发送ARP请求的是一个广播；收到ARP响应的是一个单播(先发送广播再返回单播)

③主机与服务器建立TCP连接

④主机发送HTTP协议请求服务器响应请求