2017年新疆大学数据结构考研复试核心题库
● 摘要
一、应用题
1． 某32位计算机，CPU 主频为800MHz ，Cache 命中时的CPI 为4, Cache块大小为32字节；主存采用8体交叉存储方式，每个体的存储字长为32位、存储周期为40ns ; 存储器总线宽度为32位，总线时钟频率为200MHz , 支持突发传送总线事务。每次读突发传送总线事务的过程包括：送首地址和命令、存储器准备 数据、传送数据。每次突发传送32字节，传送地址或32位数据均需要一个总线时钟周期。请回答下列问题，要求给出理由或计算过程。
（1）CPU 和总线的时钟周期各为多少？总线的带宽（即最大数据传输率）为多少？
（2）Cache 缺失时，需要用几个读突发传送总线事务来完成一个主存块的读取？
（3）存储器总线完成一次读突发传送总线事务所需的时间是多少？
（4）若程序BP 执行过程中，共执行了100条指令，平均每条指令需进行1.2次访存，Cache 缺失率为5%, 不考虑替换等开销，则BP 的CPU 执行时间是多少？
【答案】
（1）因为CPU 主频为800MHz ，故CPU 的时钟周期为：
总线时钟频率为200MHz ，故总线的时钟周期为：
总线宽度为32bit=4B，故总线带宽为
存块。
（3）—次读突发传送总线事务包括一次地址传送和32B 数据传送:用1个总线时钟周期传输地址;
每隔，第一个体读数据花费40ns ，之后数据启动一个体工作（各进行1次存取）
存取与数据传输重叠；用8个总线时钟周期传输数据。读突发传送总线事务时间
：
s
BP 的CPU 执行时间包括Cache 命中时的指令执行时间和Cache 缺失时带来的额外开销。（4）
即执行时间=指令条数
间
：时钟周期*命中率+访存次数*缺失率*缺失损失。命中时的指令执行时指令执行过程中
的CPU 执行时间
：
2． 设哈希（Hash ）表的地址范围为0～17，哈希函数为：
造出哈希表，试回答下列问题：
（1）画出哈希表示意图；
（2）若查找关键字63，需要依次与哪些关键字比较？
（3）若查找关键字60，需要依次与哪些关键字比较？
（2）因为Cache 块大小为32B , 因此Cache 缺失时需要一个读突发传送总线事务读取一个贮Cache 缺失时的额外开
销 为关键字，用线性探测再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）
（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
【答案】（1）哈希表示意图如表所示：
表 哈希示意图
（2）查找关键字63时，由于
63比较。
（3）查找关键字60时，由于
（4）
3． 在树和 树中查找关键字时，有什么不同？
树的非终端结点是索引部分，其查找从根开始，从根往下查到关键
. 树还可以在最下层从最小关哈希地址12内为空，查找失败。 所以需要依次与31，46，47，32，17，【答案】在树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。字后，要继续查到最下层结点，得到查找成功与否的结论。另外，
键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。
4． 假设计算机系统采用CSCAN （循环扫描）磁盘调度策略。使用2KB 的内存空间记录16384个磁盘块的空闲状态。
（1）请说明在上述条件下如何进行磁盘空闲状态的管理。
（2）设某单面磁盘旋转速度为每分钟6000转，每个磁道有100个扇区，相邻磁道间的平均移动时间为lms 。若在某时刻，磁头位于100号磁道处，并沿着磁道号增大的方向移动（如下图
，所示）磁道号请求队列为50, 90, 30, 120, 对请求队列中的每个磁道需要读取1个随机分布的扇区，则读完这4个扇区总共需要多少时间? 要求给出计算过程。
图
SSD 等），（3）如果将磁盘替换为随机访问的FLash 半导体存储器（如U 盘、是否有比CSCAN
更高效的磁盘调度策略? 若有，给出磁盘调度策略的名称并说明理由；若无，说明理由。
【答案】（1）采用位示图法管理磁盘空闲块，每一位表示一个磁盘块的状态，共需要16384/32=512个字节即2KB 的空间，正好可放在系统提供的内存中。
（2）采用CSCAN 调度算法，访问磁道的顺序和移动的磁道数如下表所示：
故移动的磁道数为20+90+20+40=170, 所花的时间为170ms 。由于转速为
花的时间为0.4ms 。综上所述，读取磁道上所有扇区所花的总时间为则平均旋 转延迟为5ms ，总的旋转延迟时间为20ms ，读取一个扇区的平均时间为0.1ms , 故读取4个扇区所
（3）采用先来先服务（FCFS ）调度策略更高效，因为Flash 半导体存储器的物理结构不需要考虑寻道时间和旋转延迟，可直接按请求的先后顺序服务。
5． 为什么在倒排文件组织中，实际记录中的关键字域可删除以节约空间? 而在多重表结构中这样做为什么要牺牲性能？
【答案】因倒排文件组织中，倒排表有关键字值及同一关键字值的记录的所有物理记录号，可方便地查询具有同一关键字值的所有记录；而多重表文件中次关键字索引结构不同，删除关键字域后查询性能受到影响。
6． 某16位计算机中，带符号整数用补码表示，数据Cache 和指令Cache 分离。题表给出了指令系统中部分指令格式，其中Rs 和Rd 表示寄存器，mem 表示存储单元地址，（X ）表示寄存器X 或存储单元X 的内容。
表 指令系统中部分指令格式
该计算机采用5段流水方式执行指令，各流水段分别是取指（IF ）、译码/读寄存器（ID ）、执行/计算有效地址（EX ）、访问存储器（M ）和结果写回寄存器（WB ）, 流水线采用“按序发射，按序完成”方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题。
（1）若int 型变量x 的值为-513, 存放在寄存器R1中，则执行指令“SHR R1”后，R1的内容是多少？（用十六进制表示）
相关内容
相关标签