408

DS

矩阵

• 对称矩阵、三角矩阵、三对角矩阵、稀疏矩阵
• 按行、列优先

栈&队列

• 卡特兰数：$\frac{1}{n+1} C_{2n}^{n}$ n个不同元素进栈，出栈元素不同排序个数为（n个元素能构成多少种不同的二叉树）

二叉树

• 存储、先中后遍历、森林

二叉排序树

搜索

• 深&广搜、拓扑

MST

• KE、PV

关键路径

排序

堆排序、直接插入、简单选择

B树

OS

进程

多进程读写、父子进程

磁盘存储空间分配方式

索引、链接、连续、动态分区

中断操作与OS

多级反馈队列

银行家算法

安全序列

请求分页系统

设备独立性

CO

概述

计算机的四代变化

• 电子管时代->晶体管时代->中小规模集成电路时代->超大规模集成电路时代

摩尔定律

• 价格不变时，集成电路上可容纳的晶体管数目，约每隔18个月便会增加一倍，性能也将提升一倍。

冯·诺依曼机

• 运算器、控制器、存储器、输入设备、输出设备
• 指令和数据同等地位存储

“存储程序”的工作方式

• 根据PC取指令 -> 指令译码，PC=PC+”1” -> 取操作数并执行 -> 送结果

从源程序到可执行文件

• hello.c（源程序）—–预处理器cpp—-> hello.i（修改了的源程序）—–编译器ccl—–> hello.s （汇编语言源程序）—–汇编器as—–> hello.o （可重定位目标代码文件）—–链接器ld—–> hello（可执行文件）

指令执行过程的描述

1. 取指令：PC->MAR->M->MDR->IR
2. 分析指令：OP(IR)->CU, PC=PC+”1”
3. 执行指令：Ad(IR)->MAR->M->MDR->ACC

数据

带标志加法器

• OF：有符号数，是否溢出
• SF：有符号数，结果的正负
• ZF：有&无，结果是否为0
• CF：无，进位/借位，判断是否溢出

浮点数的表示格式

• 32位：0符号位S，1-7阶码E（偏置值64），8-31尾数
• 负上溢->可表示->负下溢->正下溢->可表示->正上溢
• （正负）上溢->中断运算操作，溢出处理，（正负）下溢->当作机器零

大小端

• 机器数01234567H
• 大端01234567H
• 小端67452301H

边界对齐

• RISC通常采用边界对齐方式，因为取指令时间相同，因此能适应指令流水。

无符号整数的溢出

• 保留低n位

存储系统

RAM&ROM

• RAM主要用作主存或高速缓冲存储器
• ROM与RAM共同作为主存的一部分，统一构成主存的地址域
• 由ROM派生出的存储器也包含可反复重写的类型
• ROM和RAM的存取方式均为随机存取

存储器的性能指标

1. 存储容量=存储字数*字长（1M*8位）
2. 单位成本=总成本/总容量
3. 存储速度：数据传输速率（每秒传送信息的位数）=数据的宽度/周期
   ①存取时间：分为读出时间和写入时间
   ②存取周期：大于存取时间（读/写后需要复原时间）
   ③主存带宽：也称数据传输速率，表示每秒从主存进出信息的最大数量。

cache

CN