计算题历年真题/教材经典例题汇总
1 计算机组成与体系结构
1.1 流水线
流水线执行时间(设有条
级操作的指令,操作执行时间分别为
):
- 流水线周期:
- 理论公式:
- 实践公式:
吞吐率(设有条
级操作的指令,流水线周期为
,使用实践公式):
- 基本公式:
- 最大吞吐率:
加速比:
- 基本公式:
【例1】(2017下半年)某计算机系统采用5级流水线结构执行指令,设每条指令的执行由取指令(
)、分析指令(
)、取操作数(
)、运算(
)和写回结果(
)组成, 并分别用5个子部件完成,该流水线的最大吞吐率为( );若连续向流水线输入10条指令,则该流水线的加速比为( )。
流水线周期:
理论流水线执行时间:
【第1问】
最大吞吐率:
【第2问】
10条指令使用流水线的执行时间:
10条指令不使用流水线的执行时间:
加速比:
【例2】(教材例题1.3.1)某计算机系统一条指令的执行需要经历取指(2ms)、分析(4ms)、执行(1ms)三个阶段,现要执行100条指令,利用流水线技术需要多长时间?
流水线周期:
理论流水线执行时间:
实际流水线执行时间:
1.2 主存编址、进制转换
主存容量、芯片数计算:
存储单元个数 = 最大地址 - 最小地址 + 1
总容量 = 存储单元个数 × 编址内容
,其中编址内容为1个字(4B或8B)或1B(8bit)芯片总数 = 总容量 / 每片的容量
进制转换:
- R进制转十进制(按权展开法):
数码 × 位权
的和 - 十进制转R进制(除基取余法):短除法,余数即为从低位到高位上的数码
- 二进制转八进制与十六进制:从低位起,3位(八进制)或4位(十六进制)一组,每组根据
421
(八进制)或8421
(十六进制)计算“1”所在位的加和,最后排列即得。
【例】内存按字节编址,地址从
90000H
到CFFFFH
,若用存储容量为16K × 8bit器芯片构成该内存,至少需要( )片。
CFFFFH - 90000H + 1 = 3FFFFH + 1 = 40000H
法1——十六进制转十进制:40000H
转成十进制为256K,由于内存按字节编址(8bit),故存储容量为256K / 16K = 16
法2——十进制转十六进制:16K转成十六进制为4000H
,则有40000H / 4000H = 10
,转成十进制为16。
1.3 磁盘管理
数据读取时间:
- 存取时间(Access Time,不含读取):寻道时间(磁头移动到磁道所需的时间) + 等待时间(等待读写的扇区转到磁头下⽅所⽤的时间)
- 读取磁盘数据的时间:寻道时间、旋转延迟时间(找块/扇区的时间)、传输时间
- 先来先服务(FCFS):访问序号即为申请序号
- 最短寻道时间优先(SSTF):被访问的下一个磁道为距离当前磁道最近(柱面号 → 磁道号(非磁头号) → 扇区号)的待访问磁道
缓冲区:略///
2 操作系统
2.1 PV操作
前P
后V
,易解。
2.2 ⻚式存储管理
页号查表 + 页内地址:
- 逻辑/物理页地址:
页号/页帧号 页内地址
- 技巧:将页面大小化为
,可得页内地址的二进制位数为
,对应十六进制的后
位
页面淘汰算法:
- 淘汰状态位为1(在内存中)的页面
- 淘汰访问位为0(未访问过)的页面
- 淘汰修改位为0(未修改过)的页面
【例1】(2013下半年)某操作系统采用分页存储管理方式,下图给出了进程A和进程B的页表结构。如果物理页的大小为512字节,那么进程A逻辑地址为
(十进制)的变量存放在( )号物理内存页中。假设进程A的逻辑页4与进程B的逻辑页5要共享物理页8,那么应该在进程A页表的逻辑页4和进程B页表的逻辑页5对应的物理页处分别填( )。
【第1问】
十进制数转成二进制为
。物理页的大小为512字节,
,则页内地址为9个二进制位。故该变量的页号为
,即十进制数2,对应的物理页为4。
【第2问】
共享物理页8说明均对应物理页8,故均应填8
【例2】(2012下半年)进程P有6个页面,页号分别为0~5,页面大小为4K,页面变换表如下所示。表中状态位等于1和0分别表示页面在内存和不在内存。假设系统给进程P分配了4个存储块,进程P要访问的逻辑地址为十六进制1165H,那么该地址经过变换后,其物理地址应为十六进制( );如果进程P要访问的页面4不在内存,那么应淘汰页号为( )的页面。
【第1问】
页面大小为4K,,则页内地址的位数为12位,对应十六进制的后3位
165H
。查表可得页号1对应的物理块号(页帧号)为3,故物理地址为3165H
。
【第2问】
根据页面淘汰算法易知,应淘汰5。
2.2 文件系统
- 直接索引范围:
索引块数量 * 索引块大小
n
级间接索引范围:物理块数量^n * 索引块大小
物理块数量 = 数据块大小 / 地址项大小
- 一般情况下,
索引块大小 = 数据块大小
位示图:
物理块数 = 磁盘容量 / 物理块大小
位示图的大小 = 物理块数 / 机器字长 = 磁盘容量 / 物理块大小 / 机器字长
3 数据库系统
数据库关系模式、函数依赖
4 项目管理
成本计算、进度管理相关计算题型:
5 数学与经济管理
简单运筹学、数学建模:
图论: