408-组成原理

运算方法和整数运算

部件

运算器主要——ALU，移位器，PSW和通用寄存器；ALU主要——带标志加法器，CLA，ACC，MX，X等

PSW(FR)

OF——有符号溢出，ZF——0，CF——无符号溢出，SF——符号

移位

1. 逻辑移位：无符号的常规补0移位，高位出去1算溢出

2. 算数移位：后加0，前加符号，符号变化算溢出

3. LOOP：带CF的加一位循环

加减

原码：需要减法器，根绝对值大的同号

补码

1. 溢出判断：最高和次高异或；二符号位；++必得+，–必得-

2. 无符号数：减法-加法器signal=1，CF判断

乘法

原码

符号位单独算，剩下的绝对值

补码

MX多一个辅助位，根据辅助-最低位决定加的数，最后再不移位加一个

除法

按位减

原码

符号绝对值分开

小数必须被除数小于除数

1. 回头法：默认1，减，得到负数加回来，改0

2. 不回头：直接减，正为1，继续减；负为0，直接移位，再加

补码

两位符号带着算

两数同号，减，商1；异号，加，商0

最后一位必为1

408-组成原理

数据表示

十转二

整数——求余数，小数——乘2求整数部分

8421(BCD)

用四位表示十进制数

进位如果错误需要加6

真值，机器数

真值——带符号，机器数——有符号位

C语言的数据类型

1. char——8，short——16，int——32，long——计算机位数

2. 除了char，不指定默认有符号

3. 所有整数都以补码存储

4. 强制转换不改变数字，只改变解释方式

5. 有符号+无符号按照无符号

6. 长+短先补齐短

7. 大变小直接不要高位

TIPS

1. 用补码表示整数，用移码表示浮点数阶数，用原码表示浮点数尾数

2. 补码，移码多一个最小数，只有一个0

数学-高数

极限

求极限的常用方法

1. 有理运算法则——极限的拆分合并

2. 基本的极限代换(加减代换要求等阶不相等)

3. 洛必达法则

4. 泰勒公式

5. 定积分——提可爱因子

6. 夹逼准则

7. 单调有界——先证明存在再直接计算

常见题型

1. 0/0——洛必达，泰勒，代换

2. 无穷/无穷——洛必达，同除以无穷

3. 无穷-无穷——通分，有理化，提无限

4. 0*无穷——化为分式

5. 1的无穷次——化为ln，化为(1+0)无穷次=e，**(1+ax)的bx次，ax=0，bx无穷，等于e的axbx次方**

6. 无穷的0次和0的0次——ln

数列极限

1. 不定式——不能直接洛必达，换成函数，正常求解

2. n项求和——夹逼定理，定积分，级数(次量级夹逼，同量级积分)

3. n项乘积——夹逼定理，取对数n项和

4. 递推关系——先证单调在求极限，先极限再证明结果正确(关键是递推xn-a)

极限参数

求极限结果或过程中得到参数

无穷小量比较

1. 直接两两比较

2. 求各自的阶数

3. 求各自导数

4. 等价代换

5. 在变上限积分，内部m阶，上限n阶，总共n(m+1)阶

连续

定义

这一点的极限等于这一点

左右极限都要相等

间断点

第一类——两个都存在

1. 可去间断点——两个相等

2. 跳跃间断点——两个不相等

第二类——至少一个不存在

1. 无穷间断点——无穷

2. 震荡间断点——sin 1/x

基本性质

1. 连续函数复合仍然连续

2. 初等函数连续

3. 闭区间连续存在有界性，最值性，介值性，零点定理

常见题型

1. 讨论间断点——分母，根号，ln

2. 定理证明

408-组成原理

计算机系统概述

发展历程

电子管——晶体管——中小规模集成电路——超大规模集成电路

计算机组成

用运算器，存储器，控制器，输入，输出设备组成

冯诺依曼机以运算器中心，当代以存储器为中心

各部件

1. 存储器：内存外存，包含MDR，MAR

2. 运算器：包含ALU，ACC，MQ，X等，还有PSW程序状态寄存器

3. 控制器：IR，PC，CU

4. IO

计算机软件

分为系统软件和应用软件

语言级别

1. 机器语言——二进制

2. 汇编语言——助记符，一一对应

3. 高级语言

既可以硬件又可以软件执行的称为逻辑功能等价性

计算机层次结构

1. 微程序机器层M0——执行微指令

2. 传统机器语言层M1——由微程序解释机器指令系统

3. 操作系统层M2——机器指令+广义指令(操作系统定义+解释的软件指令)混合层

4. 汇编语言层M3

5. 高级语言层M4

0，1是硬件层，上面是抽象层虚拟机

ISA——指令集体系结构，规定了所有可执行指令

编译

预处理——编译——汇编——链接

程序执行

取指令——分析指令——执行

TIPS

1. 冯诺依曼机基本工作方式——控制流驱动

2. 相联存储器——可以按内容寻址

3. Cache-SRAM，内存——DRAM

4. 机器字长(字长)——一次整数运算的位数——一般等于CPU寄存器，ALU位数

5. 操作系统位数——可寻址的位数

6. 数据通路带宽——数据总线位数(外部)

7. CPU时钟周期——内部主时钟脉冲宽度——一般是相邻状态单元间，每个流水线段的最大延迟时间

8. 必须CPI，主频，指令条数均知道才可以比较，单纯IPS可能指令集不同

9. 存储-1024，时间-1000

10. 固件——程序固化在ROM

11. IR，MDR，MAR对所有人不可见

数学-高数

极限

概念

1. 极限值的存在与数列的前有限项无关

2. 数列的奇偶数项极限，函数的正负极限，必须相等，才能得到本身极限

3. 函数极限的几何定义为去心领域

性质

1. 局部有界性：函数极限存在，去心领域有界（不可反）

2. 保号性：带帽法有等号，脱帽法没等号

3. 极限值等于常数+无穷小量

存在准则

1. 夹逼准则：不等式两边极限相等，中间也相等

2. 单调有界准则：单增，有上界的数列有极限；单减，有下界的数列有极限

无穷大小量

1. 有限个无穷小量和，积为无穷小

2. 无界变量是存在，无穷大量是满足

408-操作系统

概述

操作系统特征

1. 并发：同一时间片段，并非并行

2. 共享：共享同一硬件资源，互斥指资源不可并发，同时可以并发

3. 虚拟：将物理资源虚拟为多个虚拟资源

4. 异步：进程走走停停

并发和共享互相依存，虚拟和异步依赖并发

功能

处理器管理，存储器管理，文件管理，IO管理

接口

命令接口

1. 联机命令接口：交互

2. 脱机命令接口：bat，批处理

程序接口

程序使用，即系统调用

发展历程

手工

单用户独占，手工操作

单道批处理

一批次作业输入磁带，依次进入内存，IO更快

多道批处理

作业在外存排成队列，相互穿插运行，宏观并行，通过中断实现，没有人机交互

分时操作系统

短时间轮流多用户，交互

实时操作系统

紧急任务处理，硬实时不可出错

网络和分布式

网络：资源共享和通信

分布：分布和并行

分布式需要多个计算机相互协同

运行模式

特权指令和非特权

特权指令必须在核心态运行，非特权指令均可

特权指令的类别

时钟管理，中断机制，原语，系统控制的数据结构和处理(系统调用)

中断和异常

中断

外中断，来自外部，包括时钟，IO等，每个时间段结束后检测

分为可屏蔽中断INTR，不可屏蔽NMI

异常

内中断，来自内部，当前执行，不能被屏蔽

分为陷入(事先安排，包括特权指令)，故障(指令引起，可修复)，终止(无法继续的硬件故障)

中断和终止属于硬件中断

TIPS

中断和子程序都要保存PC，中断要保存PSW，中断的保存硬件实现

硬件找到中断号

程序执行保存中断执行字，寄存器

系统调用

一些子功能，特殊的公共子程序，运行在内核态

过程:

1. 压入参数，执行陷入，转为内核态

2. 分析调用类型，进入子程序入口

3. 执行完恢复现场

系统结构

1. 分层式：一层层，便于调试，易于扩展，分层定义困难，效率低

2. 模块化：各模块可以通信，可扩展，可适应性好，比较混乱

3. 宏内核：常见模块+系统调用

4. 微内核：只保留基本功能(进程管理，低级存储器管理，中断和陷入处理)，客户服务器模式，功能服务器在用户态实现，机制与策略分离，扩展性，可靠安全，分布式，性能低下

5. 外核：内核态运行，为虚拟机直接分配资源，少了抽象层

系统引导

顺序

1. 激活CPU：读取ROM中的BOOT，开始BIOS

2. 硬件自检：创建中断向量表，检查硬件

3. 加载系统硬盘：BIOS读取CMOS中的顺序，到第一块硬盘

4. MBR：主引导程序，区分引导盘，包含硬盘分区表

5. 硬盘分区表：找到引导分区位置

6. PBR：寻找分区下的启动程序

7. 加载启动管理器

8. 加载系统

虚拟机

第一类虚拟机管理程序

运行在内核态，向上提供

支持虚拟化CPU：内核态指令，系统的有程序分配执行，程序的模拟执行

不支持虚拟化：全部模拟

第二类虚拟机管理程序

在宿主系统上的软件

数学-高数

函数

1. 函数要求定义域和对应法则

2. 复合函数：值域和定义域有交集

3. 反函数：存在唯一对应

4. 初等函数：有限次四则运算和复合，一个式子表示

5. 单调性：导数增->单调增 反向不成立

6. 奇偶性：连续奇函数的原函数必然偶函数，连续偶函数的原函数只有一个奇函数

7. 原函数：一个函数的0a变上限积分是原函数

8. 周期性：可导周期函数导数为周期函数，周期函数原函数周期的要求是周期积为0

9. 有界性：闭区间连续->有界；开区间连续，端点有极限->有界；导数有限区间有界->区间有界

408

数据结构 7 查找

B树

所有节点平衡因子均为0的多路平衡查找树

1. 所有节点都在同一层

2. 至少有m/2向上取整个子树

3. 插入 从底部向上插入，如有必要进行分裂

4. 分裂 中间数值向上，两边分裂

5. 删除 不在终端，找前驱后继；终端，足够直接删除，不够找兄弟借，其次合并兄弟和上方

B+树

关键字代表子树最大值的B树变形

1. 叶节点包含全部关键字，非叶节点仅索引

2. 叶节点穿成一线性链表

散列表Hash

通过散列函数确定

1. 冲突-函数分配，聚集-处理冲突不当

2. 构建方法：直接定值 - ax+b线性函数；除留余数 - x%a；数字分析 - 其中几位比较均匀；平方取中 - 不够均匀

3. 处理冲突-拉链法：同一位置的用链表相连

4. 处理冲突-开放定值：线性探测 - 直接123；平方探测 - 数平方加符号，4k+3的素数；双散列法 - 乘第二个表；伪随机 - 直接给出

5. 查找效率：散列函数，处理冲突方式和装填因子。装填因子为记录数/长度

数据结构 8 排序

稳定性指同数值的两个数在排序中是否改变位置

插入排序

前方一部分有序

直接插入

稳定，n2，适用链式和顺序

折半插入排序：插入时折半，只适用于顺序

希尔排序

缩小增量排序，按子表顺序缩小间隔，不稳定，只适用于顺序，时间复杂度未知

交换排序

将一个值交换到正确位置

冒泡排序

稳定，n2，适用链式和顺序

快速排序

分治法，选择一个数，将左右分为大小区域，不稳定，适用顺序

时空效率：空间，使用递归，从log n到n；时间效率n2，实践最好

选择排序

选择正确的顺序插入

简单选择排序

遍历选择再插入，不稳定，适用链式和顺序，始终n2

堆排序

构建堆并拿走根节点

堆：构建从下往上，删除后，将最后值提上，再向下调整

构建时间n，堆排序时间n log n，不稳定，适用顺序

归并排序

不断归并相邻组，时间n log n，空间n，稳定，适用链式和顺序

基数排序

对各位数字进行比较，稳定，适用链式和顺序，时间d(n+r)，d是次数，n数量，r类别

计数排序

累积出现次数，根据出现次数判断顺序，稳定，时间n+k，k辅助队列长度，适用顺序

内部排序比较

时间，空间，稳定性，适用性，过程特征综合考虑

数据数量，初始状态，关键字结构和分布，稳定性要求，存储结构和辅助空间考虑

外部排序

要和外存沟通的排序

基本法

归并处理，输入区+输出区，

先得到初始归并段，再归并

时间：内部排序时间 + IO + 归并时间

提高：初始归并段减少或增加归并路数

败者树

减少归并次数，完全二叉树，存储失败数，新数直接比较自己的路径叶子到根，log n

并非越大越好，会减少每路长度

置换选择排序

保存已经输出的最大值，将大于最大值的输入的不断输出，直到全部小于

最佳归并树

让记录少的先归并，哈夫曼树，IO=WPL*2

不满足严格K叉数(度为0或K)，加入0的段，k度的节点(n-1)/(k-1)

408

数据结构 7 查找

查找的基本概念

1. 查找表 用于查找的数据集合，静态为不删减，动态增加删除

2. 平均查找长度ASL 需要比较的平均次数

顺序查找

顺序表，链表都适用，正常查找 o(n)

优化 有序，减少失败ASL；将概率大的数据放前面

折半查找

二分查找 o(log2 n)

1. 失败条件 L指针大于H

2. 判定树 平衡树，向上向下取整决定左右子树的大小关系

   折半查找次数不超过树高，适合有序顺序存储

分块查找

块内无序，块间有序

1. ASL=索引ASL+块内ASL

2. 最小ASL，块数平方为字数

二叉排序树BST

左<中<右，中序遍历为顺序数列，可以是空，最差o(n)，最好o(log2 n)，适合动态查找

1. 插入 插入访问失败最后节点的孩子，不可相同

2. 删除 叶节点直接删除；只有一颗子树直接添加；两颗子树找前驱或后继

！平衡二叉树AVL

左右高度差不超过1，查找o(log2 n)

AVL插入

根据插入点后最小不平衡树

1. LL 右旋转

2. RR 左旋转

3. LR 左右

4. RL 右左

根据情况将子树迁移

构造时按照插入处理

AVL删除

删除操作先按照BST处理，再按照插入处理，再继续检查是否传递不平衡

红黑树RBT

左中右，根叶黒，无二红，黑数同，查找o(log2 n)

引入了NULL作为叶子，黒

L最大不超过L最小的二倍

RBT插入

只需要关注插入节点的叔节点

1. 叔节点黒 根据AVL插入处理，一次的父爷变换，两次的爷孙变换

2. 叔节点红 爷父叔变换，爷作为新节点检查

RBT删除

查找o(log2 n)，先按照BST处理，再进行变换

408

数据结构 6.4 图的应用

最小生成树

1. Prim算法 从一个点出发寻找权值小的下一点

   时间复杂度V^2

2. Kruskal算法 并查集寻找最短边的集合

   时间复杂度e log e

最短路径

1. BFS 无权图

2. Djikstra算法 单源有权图 动态规划 加入后比较最短边

   时间复杂度V^2 边上有负值不适用

3. Floyd算法 任意两点 顺序作为中间点比较

   时间复杂度V^3 负值环路不适用

有向无环图DAG

用来储存算术表达式，压缩空间

拓扑排序

1. AOV网 节点代表活动

2. 拓扑排序 先进行的活动必在前，无关系的点任意

   无环必有拓扑排序 起始有入度，时间复杂度 V+E或V^2 三角矩阵必存在拓扑排序

关键路径

1. AOE网 边代表活动

2. 关键路径 时间最长的路径

   先画出关键路径再计算最迟时间

This is my first blog in 2024Fall