2017年陕西科技大学902数据结构考研复试核心题库
● 摘要
一、应用题
1． 假定某计算机的CPU 主频为80MHz , CPI为4, 并且平均每条指令访存1.5次，主存与Cache 之间交换的块大小为168, Cache的命中率为
存储器总线宽度为32位。请回答下列问题。
（1）该计算机的MIPS 数是多少? 平均每秒Cache 缺失的次数是多少? 在不考虑DMA 传送的情况下，主存带宽至少达到多少才能满足CPU 的访存要求？
（2）假定在Cache 缺失的情况下访问主存时，存在期挪用方式，磁盘
接口的数据缓冲寄存器为32位，则磁盘
的缺页率，则CPU 平均每秒产
接口平均每秒发出的DMA
生多少次缺页异常? 若页面大小为4KB ，每次缺页都需要访问磁盘，访问磁盘时DMA 传送采用周请求次数至少是多少？
（3）CPU 和DMA 控制器同时要求使用存储器总线时，哪个优先级更高? 为什么？ （4）为了提高性能，主存采用4体交叉存储模式，工作时每每个体的存储周期为50ns ，则该主存能提供的最大带宽是多少？
【答案】
（1）平均每秒CPU 执行的指令数为：平均每秒Cache 缺失的次数为：为
：
足CPU 的访存要求。
（2）平均每秒钟“缺页”异常次数为：故平均每秒磁盘DMA 请求的次数至少为：请求得不到及时响应，
传输数据可能会丢失。
个最小元素，你所学过的排序方法中哪个最小元素，应使用快速排序方法。其基本
因为存储器总线宽度为32位，所以，每传送32位数据，磁盘控制器发出一次DMA 请求，CPU 和DMA 控制器同时要求使用存储器总线时，DMA 请求优先级更高；因为若DMA （3）
（4）4体交叉存储模式能提供的最大带宽为：
2． 如果只要找出一个具有n 个元素的集合的第种最适合? 给出实现的思想。
【答案】在具有n 个元素的集合中找第
思想如下：设n 个元素的集合用一维数组表示，其第一个元素的下标为1，最后一个元素下标为n 。以第一个元素为“枢轴”，经过快速排序的一次划分，找到“枢轴”的位置i ，若i=k，则该位置的元素即为所求；若
则在1至i-1间继续进行快速排序的划分；若
则在i+1至n 间继续进
个最小元
行快速排序的划分。这种划分一直进行到i=k为止，第i 位置上的元素就是第
第 2 页，共 39 页
个存储周期启动一个体。若
故MIPS 数为20; =300000;
才能满
当Cache 缺失时，CPU 访问主存，主存与Cache 之间以块为单位传送数据，此时，主存带宽
在不考虑DMA 传输的情况下，主存带宽至少达到
素。
3． 外排序中为何采用k 一路么？
【答案】外排序用路归并
合并而不用2—路合并? 这种技术用于内排序有意义吗? 为什是因为k 越小，归并趟数越多，读写外存次数越多，时间效
率越低，故一般应大于最少的2-路归并。若将k-路归并的败者树思想单纯用于内排序，因其由胜者树改进而来，且辅助空间大，完全可由堆排序取代，故将其用于内排序效率并不高。
4． 在多关键字排序时，LSD 和MSD 两种方法的特点是什么？
【答案】（1）最高位优先（MSD ）法
先对最高位关键字进行排序，将序列分成若干子序列，
每个子序列中的记录都具有相同的值，然后，分别就每个子序列对关键字列。
（2）最低位优先先对最低位关键字位关键字
序列参加排序，
但对
法
进行排序，然后对高一级关键字
进行排序，依次重复，直至对最高
进行排序，按值不同再分成若干更小的子序列，依
次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序
排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个
排序时，只能用稳定的排序方法。另一方面，按LSD 进行排序
时，可以不通过关键字比较实现排序，而是通过若干次“分配”和“收集”来实现排序。
5．
某局域网采用协议实现介质访问控制，
数据传输率为主机甲和主机乙之间的距离为2km ，信号传播速度是200000km/S。请回答下列问题，要求说明理由或写出计算过程。
（1）若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测到冲突时刻止，最短需经过多长时间? 最长需经过多长时间？（假设主机甲和主机乙发送数据过程中，其他主机不发送数据）
（2）若网络不存在任何冲突与差错，主机甲总是以标准的最长以太网数据帧（1518字节）向主机乙发送数据，主机乙每成功收到一个数据帧后立即向主机甲发送一个64字节的确认帧，主机甲收到确认帧后方可发送下一个数据帧，此时主机甲的有效数据传输速率是多少？（不考虑以太网帧的前导码）
【答案】（1）当甲乙两台主机同时向对方发送数据时，两台主机均检测到冲突的时间最短
：
=
（lkm/200000km/s）×2=10j×s ; 当一台主机发送的数据就要到达另一台主机时，另一台主机才发送数据，两台主机均检测到冲突的时间最长：
=1500B=1500×8bit=12000bit; 发送1518B 的发送时间=1518×8/10Mbps=间=2km/200000km/s
第 3 页，共 39 页
数据帧的传播时
（2）有效数据传输速率=发送的有效数据/发送有效数据所用的总时间。发送的有效数据
=确认帧的发送时间=64×
8/10Mbps=; 确认帧的传播时间
=2km/200000km/s=;
发送1518B
所用的总时间为1285.6μs=9.33Mbps。
6． 设目标为
主机甲的有效数据传输率为12000bit ／
模式为
（1）计算模式p 的nextval 函数值；
（2）不写出算法，只画出利用KMP 算法进行模式匹配时每一趟的匹配过程。 【答案】（1）P 的nextval 函数值为0110132（P 的next 函数值为0111232）。 （2）利用KMP （改进的nextval ）算法，每趟匹配过程如下： 第一趟匹配：abcab （i=5, j=5） 第二趟匹配：abc （i=7，j=3） 第三趟匹配：a （i=7，j=l） 第四趟匹配：
（成功）abcabaa （i=15，j=8）
7． 设某文件经内排序后得到100个初始归并段（初始顺串），若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？
【答案】设归并路数为k ，归并趟数为s ，则
因
且k 为整数，故k=5，即
最少5-路归并完成排序。
8． 某计算机的CPU 主频为500MHz ，CPI 为5（即执行每条指令平均需要5个时钟周期）。假定某外设的数据传输率为0.5MB/S，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。
（1）在中断方式下，CPU 用于该外设I/O的时间占整个CPU 时间的百分比是多少？ （2）当该外设的数据传输率达到5MB/s时，改用DMA 方式传送数据。假定每次DMA 传送块大小为5000B , 且DMA 预处理和后处理的总开销为500个时钟周期，则CPU 用于该外设I/0时间占整个CTU 时间的百分比是多少？（假设DMA 与CPU 之间没有访存冲突）
【答案】（1）已知主频为500MHz ，则时钟周期=l÷500MHz=2ns，因为CPI=5, 所以每条指令，数据传输率为0.5MB/S, 所以传送时间平均5×2=10ns。又已知每中断一次传送32位（4个字节）=4÷0.5MB/s=
CPU 用于该外设I/0共需20条指令（中断服务程序包括18条指令+其他开销折
，花费时间=20×l0=200ns。CPU 用于该外设I/0的时间占整个CPU 时间的百分比合2条指令）
第 4 页，共 39 页
相关内容
相关标签