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

一、应用题

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 执行时间

：Cache 缺失时的额外开

销 （2）因为Cache 块大小为32B , 因此Cache 缺失时需要一个读突发传送总线事务读取一个贮

2． 以归并算法为例，比较内部排序和外部排序的不同，说明外部排序如何提高操作效率。

【答案】（1）内部排序中的归并排序是在内存中进行的归并排序，辅助空间为外部归并排序是将外存中的多个有序子文件合并成一个有序子文件，将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。外部排序的效率主要取决于读写外存的次数，即归并的趟数。

（2）因为归并的趟数其中，m 是归并段个数，k 是归并路数。增大k 和减少m 都

可减少归并趟数。应用中通过败者树进行多（k ）路平衡归并和置换一选择排序减少m ，来提高外部排序的效率。

3． 假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：

（1）画出描述折半查找过程的判定树；

（2）若查找元素54，需依次与哪些元素比较？

（3）若查找元素90，需依次与哪些元素比较？

（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。

【答案】（1）判定树如图所示：

图 判定树

（2）若查找元素54，需依次和元素30、63、42、54比较，查找成功。

（3）若查找元素90，需依次和元素30、63、87、95比较，查找失败。

（4）

4． 在树和树中查找关键字时，有什么不同？

树的非终端结点是索引部分，其查找从根开始，从根往下查到关键

. 树还可以在最下层从最小关 【答案】在树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。字后，要继续查到最下层结点，得到查找成功与否的结论。另外，

键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。

5． 设有6个有序表A 、B 、C 、D 、E 、F , 分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。

（1）给出完整的合并过程，并求出最坏情况下比较的总次数。

（2）根据你的合并过程，描述

n

【答案】

（1）6个表的合并顺序如下图所示。 个不等长升序表的合并策略，并说明理由。

对应于合并过程的哈夫曼树

根据上图中的哈夫曼树，6个序列的合并过程为：

第1次合并：表A 与表B 合并，生成含45个元素的表AB ;

第2次合并：表AB 与表C 合并，生成含85个元素的表ABC ;

第3次合并：表D 与表E 合并，生成含110个元素的表DE ;

第4次合并：表ABC 与表DE 合并，生成含195个元素的表ABCDE ;

第5次合并：表ABCDE 与表F 合并，生成含395个元素的最终表。

由于合并两个长度分别为m 和n 的有序表，最坏情况下需要比较m+n-1次，故最坏情况下比较的总次数计算如下：

第1次合并：最多比较次数= 10+35-1=44;

第2次合并：最多比较次数=45+40-1 = 84;

第3次合并：最多比较次数=50+60-1 = 109;

第4次合并：最多比较次数=85+110-1 = 194;

第5次合并：最多比较次数= 195+200-1 = 394; 比较的总次数最多为：44+84+109+194+394 = 825。

（2）各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。

6． 设LS 是一个线性表，若采用顺序存储结构，则在等概率的前提下，插

与

之间的概率

为入一个元素需要平均移动的元素个数是多少? 若元素插

在

【答案】需要分两种情况讨论：

，插入位置0..n ，则平均移动个数为（1）等概率（后插）

（2）若不等概率，则平均移动的元素个数为

则插入一个元素需要平均移动的元素个数又是多少？