资讯详情

2021计算机考研408计算机学科专业基础综合冲刺复习提纲

背景

我从2020年8月中旬开始复习。考试快的时候整理出来的文档，本来是为了帮我冲刺复习。另外，我是计算机科学技术专业的，所以平时用的知识很多，所以对我来说，我需要知道的东西会少很多。我觉得需要注意以下内容。我把原文档放在里面GitHub上:408冲刺复习提纲.md，大家如果有补充可以提PR，最好帮助有需要的人。复习不容易，大家加油。

数据结构

  • KMP算法，next数组：

排序

  • 排序算法关键词的比较次数与原始序列无关：简单选择排序，插入两分排序
  • 不稳定排序算法：快速排序、希尔排序、选择排序、堆排序
  • 多路归并排序
    • 置换-排序
    • 最佳归并树
    • 败者树
  • 基数排序
    • 最高优先级：逐级排序
    • 最低优先：，

图论

查找

计算机组成原理

基本概念

  • 计算机性能

    • IPC
    • CPI
  • 机器字长 存储字长 指令字长
    CPU一次能处理的最多位数据长度，通常与CPU的通用寄存器位数有关 存储器中一个存储单元(存储地址)所存储的二进制代码的位数，即存储器中的MDR的位数 计算机指令字的位数

  • 2 15 = 32768 , 2 16 = 65536 2^{15}=32768,2^{16}=65536 215=32768,216=65536

  • FLOPS，K->M->G->T->P->E->Z

数据表示与运算

  • 原码，补码，移码比较

  • IEEE754浮点数格式， float，double，浮点数范围，浮点数表示

    • float 8 位阶码，double 11 位阶码

    • 1. m ∗ 2 M − 127 , M ∈ [ 0 , 255 ] 1.m*2^{M-127},M\in[0, 255] 1.m∗2M−127,M∈[0,255]

    • 阶码全0表示无穷小()，全1表示无穷大()，因此阶码范围[-126, 127]

    • 绝对值最小规约数 ± 1.0 ∗ 2 − 126 \pm 1.0*2^{-126} ±1.0∗2−126

    • 绝对值最大规约数

    ± ( 2 − 2 − 23 ) ∗ 2 127 \pm (2-2^{-23})*2^{127} ±(2−2−23)∗2127

    • NaN：指数全一，尾数非全零

  • 浮点数加法

    1. 对阶，small -> big
    2. 尾数相加
    3. 尾数规格化
      • 左归，阶码减少，不可能溢出
      • 右归，阶码增加，有可能溢出
    4. 舍入
    5. 溢出判断
      • 上溢，异常，中断
      • 下溢，机器零处理

  • 两个无符号数相加OF可能为1（溢出），相减CF可能为1（小-大，借位）

  • 定点补码溢出判断（机器级判断）

    • 单符号：操作数符号相同，结果符号与操作数符号不同
    • 双符号：双符号位符号不同表示溢出，且最高符号位表示最终运算结果符号

  • 乘法就是加法和移位共同作用，比如

存储系统

  • SRAM，DRAM，ROM，随机，只读

  • 主存与CPU的连接，特别是DRAM片选时，行列地址线复用

  • 双端RAM：可同时读，不可同时写，不可同时读写

  • 交叉存储器连续读区n个字的时间 t = T + ( n − 1 ) τ t=T+(n-1)\tau t=T+(n−1)τ

  • DRAM的刷新

    • 集中刷新：存在死时间
    • 分散刷新：不存在死时间
    • 异步刷新：死时间只是一个读写周期

  • Cache替换策略LRU算法需要加额外的位 l o g 2 n log_2n log2​n

  • Cache相关计算 h 命 中 率 t c 命 中 时 间 t c 访 问 主 存 时 间 t a 平 均 访 问 时 间 = h ∗ t c + ( 1 − h ) ∗ t m e 访 问 效 率 = t c t a h命中率\\t_c命中时间\\t_c访问主存时间\\t_a平均访问时间=h*t_c+(1-h)*t_m\\e访问效率=\frac{t_c}{t_a} h命中率tc​命中时间tc​访问主存时间ta​平均访问时间=h∗tc​+(1−h)∗tm​e访问效率=ta​tc​​

指令系统

  • 寻址方式，

    • 立即寻址（操作数），直接寻址（地址）
    • 寄存器间接寻址，存储器间接寻址
    • 基址寻址（程序段），变址寻址（数组）
    • 相对寻址，注意取指后PC会+1，偏移位置的计算
    • 堆栈寻址，参数传递

  • 指定地址码可能的情况

    • 寄存器编号
    • 设备端口地址
    • 主存地址
    • 数值

  • 不定长操作码指令格式：注意前缀一定不能相同（同哈夫曼编码）

  • 区别 CISC RISC
    指令系统 复杂 简单
    指令数目 多 少
    指令字长 不固定 固定
    控制方式 微程序 组合逻辑电路
    通用寄存器数量 少 多
    目标代码 难以编译优化 可以编译优化，效率高
    各指令执行时间 相差较大 有指令流水线，多在一个时钟周期内

CPU

  • 运算器构成元素

    • ALU
    • 累加寄存器
    • 通用寄存器
    • PSW
    • 暂存寄存器

  • 控制器构成元素

    • PC
    • IR
    • MAR
    • MDR
    • 指令译码器

  • 用户可见寄存器

    • 通用寄存器
    • PC
    • ACC
    • PSW

  • CPU控制方式

    • 同步控制
      • 统一节拍（统一的时序信号）
      • 不统一节拍（通过增加冗余节拍来达到统一节拍）
      • 中央控制和局部控制相结合的方法（乘、除和浮点运算）
    • 异步控制（采用应答机制，一般用于高速主机和低速设备中，如I/O）

  • 包含若干，机器周期包含若干

  • 控制存储器（ROM）

  • 微指令的编码方式

    • ，长度长n
    • ：互斥指令归一类，长度短log (n + 1)，需要译码
    • 字段间接编码

  • 微指令序列地址形成

    • 断定方式
    • 译码方式，根据操作码
    • 增量计数器，(CMAR) + q -> CMAR
    • 分支转移，根据转移
    • 硬件直接产生
  • 区别 水平微指令 垂直微指令
    并行性 好 不好

| 需要的微指令条数 | 少 | 多 | | 和机器指令的相似程度 | 差别大 | 相似 | | 备注 | 用较短的微程序结构换较长的微指令结构 | 用较长的微程序结构换较短的微指令结构 |

  • 指令流水线

    • 超标量流水线
    • 超极流水线
    • 超长指令字

  • 流水线阻塞因素

    • 结构相关：竞争同一资源导致，解决：
      • 指令和数据分离
      • 延后时钟周期
    • 数据相关：同步问题，解决：
      • 延后时钟周期
      • 数据旁路
    • 控制相关：跳转指令，解决：
      • 分支预测
      • 指令预取

  • 流水线性能分析

    • 吞吐率

    • 加速比 k = 不 使 用 流 水 线 的 时 间 使 用 流 水 线 的 时 间 k=\frac{不使用流水线的时间}{使用流水线的时间} k=使用流水线的时间不使用流水线的时间​

    • 流水线效率 E = n 个 任 务 总 面 积 实 际 面 积 E=\frac{n个任务总面积}{实际面积} E=实际面积n个任务总面积​

总线

  • 总线分类（按功能划分）
    • 片内总线：CPU内部
    • 系统总线：计算机系统内
    • 通信总线：计算机之间
  • 总线两种定时方式
    • 同步通信：统一时钟信号管理
    • 异步通信：”握手“，”应答“。常用于通信双方速度差异较大的设备之间
      • 不互锁：啥也不管
      • 半互锁：半双工
      • 全互锁：三次握手
  • 总线性能指标
    • 总线时钟周期：机器时钟周期
    • 总线时钟频率：总线时钟周期的倒数
    • 总线工作周期：一次总线操作需要多少个总线时钟周期
    • 总线工作频率：总线工作周期的倒数
  • 总线复用：地址/信号线复用
  • 总线标准（趋势：串行总线代替并行总线）
    • 系统总线，FBS，QPI（串行总线，Intel提出）
    • 局部总线，PCI（并行总线），PCI-E（串行总线）
    • 设备总线
      • 并行总线：SCSI，IDE
      • 串行总线：USB，SATA

I/O系统

  • RAID
    • RAID：内容分开存
    • RAID：内容冗余存
    • RAID：海明码校验纠错
    • RAID：奇偶校验
  • I/O接口，设备中断码传递通过数据总线，CPU检测中断信号通过控制总线，I/O接口有很多I/O端口
  • I/O接口中的控制寄存器和状态寄存器可以复用
  • 中断处理过程
    • 中断向量，中断向量地址，硬件产生向量地址，由向量地址找到向量
    • 中断隐指令
      • 关中断
      • 保存断点（PC，PSW）
      • 找到中断服务程序
    • 保存现场*（和 PSW（多重中断））*
    • 中断服务程序
    • 关中断（多重中断）
    • 恢复现场*（和 PSW（多重中断））*
    • 开中断
    • 中断最后一条指令为返回指令
  • 中断到来顺序和中断响应顺序没有关系，中断响应顺序根据硬件排队器和中断屏蔽字实现
  • 中断检查发生在每条指令执行末端，也就是中断周期内检查。所以外中断有延时，而异常没有延时
  • DMA
    • 一次DMA请求对应与总线的使用权争夺，一次DMA请求传送一个字的数据，一次DMA传送操作中对应多次DMA请求
    • DMA的优先级比程序中断的优先级高

操作系统

操作系统发展历程

  • 体系结构
    • 微内核，代表Windows
    • 宏内核，代表Linux
  • 核心态转向用户态由一条指令实现，这条指令是特权指令，一般是中断返回指令

进程管理

  • 进程状态转换

    • 进程创建就通过完成，大小和内存容量决定进程创建数量，PCB是进程存在唯一标志
    • 进程阻塞是主动行为，进程唤醒是被动行为

  • 处理机调度

    • 高级调度：作业调度
    • 中级调度：内存调度（挂起，激活）
    • 低级调度：进程调度

  • 调度指标

    • 周转时间：作业完成时间-作业提交时间
    • 平均周转时间
    • 带权周转时间：作业周转时间/作业实际运行时间
    • 平均带权周转时间
    • 等待时间
    • 响应时间：从用户提交作业到首次响应的时间

  • 进程调度优先级

    • 系统高于用户
    • 前台高于后台
    • I/O高于CPU

  • 作业调度算法

  • 算法 备注 特点
    先来先服务 利于长作业和CPU繁忙型作业
    短优先 不利于长作业；平均等待时间，平均周转时间最小
    高响应比 响应比 = (等待时间 + 要求服务时间) / 要求服务时间 利于短作业；等待时间越长，优先级越高；好算法
    时间片轮转 时间片大小选择要适中
    多级反馈队列调度 设置多个就绪队列，时间片大小递增；抢占算法 好算法

  • 进程同步互斥原则

    • 空闲让进
    • 忙则等待
    • 有限等待
    • 让权等待

  • 互斥软件实现方法

    • 单标志法，特点：确保进程互斥访问临界区；两个进程必须交替进入临界区
    • 双标志先检查法，特点：进程不必交替进入，但是不能保证互斥访问
    • 双标志后检查法，特点：确保进程互斥访问临界区，但是会发生饥饿现象
    • 皮特森算法，特点：单标志法和双标志后检查法的结合，其中（谦让），特点：效果好，互斥且不饥饿

  • 生产者-消费者问题：生产者和消费者是互斥关系，生产者和生产者或消费者和消费者是同步关系

  • 读写问题，写写和读写互斥，读读不互斥

    • 设置读进程数count变量，同时还要设置mutex保护count
    • 为写互斥单独设置mutex
    • 写饥饿的处理：设置写优先互斥变量

  • 哲学家进餐问题

    • 用lock同时锁左右（AND型信号量）
    • 用互斥量同时锁左右

  • 死锁条件

    • 互斥
    • 不剥夺
    • 请求保持
    • 循环等待

  • 死锁解决

    • 预防死锁：破坏死锁条件
    • 避免死锁：防止系统进入
    • 死锁检测和解除，允许死锁发生，不过可以检查出来且可以解除

  • 管道通信，半双工通信

  • 临界区：访问临界资源的代码

  • 管程：语法层面，组成如下

    • 管程名称
    • 数据结构的说明
    • 函数（过程）
    • 初始化语句

内存管理

  • 连续分配方式
    • 单一连续分配
    • 固定分区分配
    • 动态分区分配
  • 动态分区分配算法
    • 首次适应
    • 循环首次适应
    • 最优适应（碎片最多）
    • 最差适应（利用率低）
  • 虚拟存储器的容量取决于地址空间的大小
  • 页面分配策略
    • 固定
      • 局部
    • 可变
      • 全局
      • 局部
  • 同一进程中，段表只有一个，而页表可能多份

文件管理

  • 逻辑文件，有结构文件，顺序文件，索引文件，索引顺序文件
  • 物理结构，顺序存储，显式链式存储，隐式链式存储，索引存储（i节点）
  • 相对路径有利于加快检索速度
  • 文件控制块FCB：存放控制文件需要的各种信息的数据结构，FCB的有序集合就是目录，一个目录项就是一个FCB
  • 文件打开，需要路径，返回句柄，之后的所有读写删除都是利用这个句柄进行操作
  • 磁盘调度寻道算法
    • 先来先服务（公平算法）
    • 最短寻道优先
    • 电梯算法（扫描算法）
    • 循环扫描算法
    • 的电梯算法，循环扫描算法
  • 目录实现，具体实现方法的优劣根据题目具体分析
    • 线性列表
    • 哈希法
  • 空闲文件管理
    • 索引表法
    • 位示法（注意起始点是0还是1）
    • 成组链接法（UNIX超级块）
  • 系统对文件操作函数第一步就是要用名字open，得到一个句柄，之后的所有操作都是用句柄操作，而不使用名字

I/O管理

  • I/O层次

    • 用户层（库函数）
    • 设备独立层（系统调用，设备分配和回收）
    • 驱动（抽象转具体，型号上报）
    • 中断（进程上下文切换，中断信号源测试，读取设备状态）
    • 设备控制器（硬件）

  • DMA

  • 通道：专门负责输入/输出的处理机

    • 指令单一
    • 无自己的内存，与CPU共享内存
    • 所执行的通道程序也是放在内存中

  • 缓冲（充满缓冲区的时间T，充满用户区的时间M，CPU处理时间C）

    • 单缓冲 M + m a x { C , T } M+max\{C,T\} M+max{ C,T}

    • 双缓冲 m a x { C + M , T } max\{C+M,T\} max{ C+M,T}

  • 设备分配

    • 数据结构
      • 设备控制表DCT
      • 控制器控制表COCT
      • 通道控制表CHCT
      • 系统设备表SDT
    • 策略（设备分配，过三关）
      • 分配设备
      • 分配控制器
      • 分配通道
      • 分配过程中访问的数据结构顺序：SDT -> DCT -> COCT ->CHCT

计算机网络

前置知识

  • 协议模型，ISO，TCP/IP

    • 差异 ISO TCP/IP
      网络层 无连接+面向连接 无连接
      传输层 面向连接 无连接+面向连接

  • 码元：离散状态，波特率：码元速率

  • 公式

    • 奈奎斯特定理：无噪声极限速率 2 W l o g 2 M 2Wlog_2M 2Wlog2​M

    • 香农定理：有噪声极限上限速率 W l o g 2 ( 1 + S N ) d B = 10 l o g 10 S N Wlog_2(1 + \frac{S}{N}) \\ dB = 10log_{10}\frac{S}{N} Wlog2​(1+NS​)dB=10log10​NS​

    • 两公式都可用 m i n { 奈 奎 斯 特 ， 香 农 } min\{奈奎斯特，香农\} min{ 奈奎斯特，香农}

  • 编码，曼切斯特编码，差分曼切斯特编码（同1异0，与前一码元比较）

  • 编码过程（典型例子，PCM）

    • 采样
    • 量化
    • 编码

  • 调制

    • 调幅
    • 调频
    • 调相

  • 分组交换

    差异 数据报 虚电路
    连接的建立 需要 不需要
    分组顺序 不保证 保证

  • 物理接口特性

    • 机械特性
    • 电气特性：电压，电相关的东西
    • 功能特性：电平，信号线（数据线，控制线）用途
    • 过程特性：时序

数据链路层

  • 零

标签： 408电容

锐单商城拥有海量元器件数据手册、 IC替代型号，打造 电子元器件IC百科大全！

锐单商城 - 一站式电子元器件采购平台