当前位置：问答库＞考研试题

一、应用题

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． 若森林共有n 个结点和b 条边（b

【答案】森林的n 个结点开始可看做是n 个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入b 条边将减少b 个连通分量，因而n 个结点b 条边的森林有n-b 棵树。

3． 设G=（V , E）以邻接表存储，如图所示，试画出图1的深度优先生成树和广度优先生成树。

第 2 页，共 21 页 （2）因为Cache 块大小为32B , 因此Cache 缺失时需要一个读突发传送总线事务读取一个贮Cache 缺失时的额外开

销

图1

【答案】设从顶点1开始遍历，则深度优先生成树如图2所示，广度优先生成树如图3所示：

图2 图3

4． 某计算机的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条指令）

=200/8000×100%=0.025×100%=2.5%。

（2）改用DMA 方式传送数据，数据传输率为5MB/S，传送5000B 的时间=5000B÷5MB/s=lms。预处理和后处理的总开销时间=500×2ns=CPU 用于该外设I/0时间占整个CPU 时间的百分比=预处理和后处理的总开销时间÷传送数据的时间=l/1000×l00%=0.001×100%=0.1%。

5． 我们知道，对于n 个元素组成的线性表进行快速排序时，所需进行的比较次数与这n 个元素的初始排序有关。问：

（1）当n=7时，在最好情况下需进行多少次比较? 请说明理由。

（2）当n=7时，给出一个最好情况的初始排序的实例。

（3）当n=7时，在最坏情况下需进行多少次比较? 请说明理由。

第 3 页，共 21 页

（4）当n=7时，给出一个最坏情况的初始排序的实例。

【答案】（1）在最好情况下，每次划分能得到两个长度相等的子文件。假设文件的长度那么第一趟划分得到两个长度均为

以此类推，

总共进行

需2次，共10次即可。

（2）在最好情况下快速排序的原始序列实例：4，1，3，2，6，5，7。

（3）在最坏情况下，若每次用来划分的记录的关键字具有最大（或最小）值，那么只能得到左（或右）子文件，其长度比原长度少1。因此，若原文件中的记录按关键字递减次序排列，而要求排序后按递増次序排列时，快速排序的效率与起泡排序相同，其时间复杂度为

n=7时，最坏情况下的比较次数为21次。

（4）在最坏情况下快速排序的初始序列实例：7，6，5，4，3，2，1，要求按递増排序。

6． 阅读下面的算法，说明算法实现的功能。

【答案】本算法功能是将两个无头结点的循环链表合并为一个循环链表。Head1最后一个结点的链域指向head2, head2最后一个结点的链域指向headl ，headl 为结果循环链表的指针。

7． 对于后序线索二叉树，怎样査找任意结点的直接后继? 对于中序线索二叉树，怎样査找任意结点的直接前驱？

【答案】（1）后序线索树中结点的后继的方法如下：根结点无后继：当结点的rtag=1时，其右线索指向后继；当结点的rtag=0且是其双亲的右孩子，或是双亲的左孩于且双亲无右孩时，其双亲是该结点的后继；当结点是其双亲的左孩子且双亲有右孩子时，其双亲结点右子树种最左下的叶结点是其后继。

（2）对中序线索二叉树的某结点，若其左标记等于1，则左孩子为线索，指向直接前驱；否则其前驱是其左子树上按中序遍历的最后一个结点。

8． 已知一个带有表头结点的单链表，结点结构为datalink , 假设该链表只给出了头指针list 。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k 个位置上的结点（k 为正整数）。若查找成功，算法输出该结点的data 域的值，并返回1; 否则，只返回0。要求：

（1）描述算法的基本设计思想；

第 4 页，共 21 页 的子文件，第二趟划分得到4个长度均为的子文件，趟划分，各子文件的长度均为1，排序完毕。当n=7时，k=3，在最好情况下，第一趟需比较6次，第二趟分别对两个子文件（长度均为3，k=2）进行排序，各所以当