2018年东北电力大学信息工程学院852数据结构考研基础五套测试题
● 摘要
一、综合题
1． 假定某计算机的CPU 主频为80MHz , CPI 为4, 并且平均每条指令访存
之间交换的块大小为168, Cache 的命中率为次, 主存与Cache , 存储器总线宽度为32位。请回答下列问题。
(1)该计算机的MIPS 数是多少? 平均每秒Cache 缺失的次数是多少? 在不考虑DMA 传送的情况下, 主存带宽至少达到多少才能满足CPU 的访存要求？
(2)假定在Cache 缺失的情况下访问主存时, 存在
式, 磁盘
少是多少？
(3)CPU和DMA 控制器同时要求使用存储器总线时, 哪个优先级更高? 为什么？
(4)为了提高性能, 主存采用4体交叉存储模式, 工作时每1/4个存储周期启动一个体。若每个体的存储周期为50ns , 则该主存能提供的最大带宽是多少？
【答案】(1)平均每秒CPU 执行的指令数为:
平均每秒Cache 缺失的次数为:
为
:。
在不考虑DMA 传输的情况下, 主存带宽至少达到
(2)平均每秒钟“缺页”异常次数为:
均每秒磁盘DMA 请求的次数至少为:
得不到及时响应, 传输数据可能会丢失。
。 次; 。 才能满足CPU 的访存要求。 , 故MIPS 数为20; 接口的数据缓冲寄存器为32位, 则磁盘的缺页率, 则CPU 平均每秒产生多少接口平均每秒发出的DMA 请求次数至次缺页异常? 若页面大小为4KB , 每次缺页都需要访问磁盘, 访问磁盘时DMA 传送采用周期挪用方当Cache 缺失时, CPU 访问主存, 主存与Cache 之间以块为单位传送数据, 此时, 主存带宽因为存储器总线宽度为32位, 所以, 每传送32位数据, 磁盘控制器发出一次DMA 请求, 故平(3)CPU和DMA 控制器同时要求使用存储器总线时, DMA 请求优先级更高; 因为若DMA 请求(4)4体交叉存储模式能提供的最大带宽为:
2． 设有正文AADBAACACCDACACAAD , 字符集为A , B , C , D , 设计一套二进制编码，使得上述正文的编码最短。
【答案】字符A ，B ，C ，D 出现的次数为9，1，5，3。其哈夫曼编码如下:A :1，B :000，C :01，D :001。
3．
设与记录
对应的关键字分别是。如果存在
和使得j 且 成立，试证明经过一趟起泡后，一定有记录与进行交换。 【答案】起泡排序思想是相邻两个记录的关键字比较，若反序则交换，一趟排序完成得到极值。由题假设知在，又因之前且，则，故，即说明和是反序；设对于和之前全部记录:(其中包括) 中关键字最大为，故经过起泡排序前i-2次比较后， 必定交换。 的关键字一定为和Rf 为反序，由此可知 4． 对于具有n 个叶结点且所有非叶结点都有左、右孩子的二叉树。 (1)试问这种二叉树的结点总数是多少？ (2)试证明。其中:表示第i 个叶结点所在的层号(设根结点所在层号为1) 。 【答案】(1)根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n 个叶结点且非叶子结点均有左子树的二叉树的结点数是2n －1。 (2)当i=1时，，公式成立。设当i=n－1时公式成立，证明当i=n时公式仍成立。 设某叶结点的层号为t ，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1，对于公式的变化，是减少了一个原来的叶结点，增加了两个新叶结点，反映到公 ，所以结果不变，这就证明当i=n时公式仍成立。 式中，因为 5． 设哈希(Hash)表的地址范围为0〜17，哈希函数为:H(K)=KMOD16，K 为关键字，用线性探测再散列法处理冲突，输入关键字序列:(10，24，32，17，31，30，46，47，40，63，49) 造出哈希表，试回答下列问题: (1)画出哈希表示意图； (2)若查找关键字63，需要依次与哪些关键字比较？ (3)若查找关键字60，需要依次与哪些关键字比较？ (4)假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 【答案】(1)哈希表不意图如表所示: 表 哈希示意图 (2)查找关键字63时，由于 比较。 (3)查找关键字60时，由于 (4) 哈希地址12内为空，查找失败。 所以需要依次与31，46，47，32，17，63 6． 三维数组 7]的存储首地址。 的每个元素的长度为4个字节，试问该数组要占多少个字节0，的存储空间? 如果数组元素以行优先的顺序存储，设第一个元素的首地址是100，试求元素A[5， 【答案】数组占的存储字节数＝10*9*7*4＝2520；A[5，0，7]的存储地址＝100＋[4*9*7＋2*7＋5]*4＝1184 7． 某32位计算机, CPU 主频为800MHz , Cache 命中时的CPI 为4, Cache 块大小为32字节; 主存采用8体交叉存储方式, 每个体的存储字长为32位、存储周期为40ns ; 存储器总线宽度为32位, 总线时钟频率为200MHz , 支持突发传送总线事务。每次读突发传送总线事务的过程包括:送首地址和命令、存储器准备数据、传送数据。每次突发传送32字节, 传送地址或32位数据均需要一个总线时钟周期。请回答下列问题, 要求给出理由或计算过程。 (1)CPU和总线的时钟周期各为多少？总线的带宽(即最大数据传输率) 为多少？ (2)Cache缺失时, 需要用几个读突发传送总线事务来完成一个主存块的读取？ (3)存储器总线完成一次读突发传送总线事务所需的时间是多少？ (4)若程序BP 执行过程中, 共执行了100条指令, 平均每条指令需进行 为, 不考虑替换等开销, 则BP 的CPU 执行时间是多少？ 【答案】(1)因为CPU 主频为800MHz , 故CPU 的时钟周期为: 总线时钟频率为200MHz , 故总线的时钟周期为: 总线宽度为 块。 (3)—次读突发传送总线事务包括一次地址传送和32B 数据传送:用1个总线时钟周期传输地址; 每隔=5tis启动一个体工作(各进行1次存取) , 第一个体读数据花费40ns , 之后数据存取与数 。 (4)BP的CPU 执行时间包括Cache 命中时的指令执行时间和Cache 缺失时带来的额外开销。即执行时间=指令条数*CPI*时钟周期*命中率+访存次数*缺失率*缺失损失。命中时的指令执行时 间: 指令执行过程中Cache 缺失时的额外开销 。 BP 的CPU 执行时间: =1010ns。 8． 简述广义表属于线性结构的理由。 【答案】广义表中的元素，可以是原子，也可以是子表，即广义表是原子或子表的有限序列，满足线性结构的特性:在非空线性结构中，只有一个称为“第一个”的元素，只有一个称为“最后一个” 次访存, Cache 缺失率。 。 。 , 故总线带宽为(2)因为Cache 块大小为32B , 因此Cache 缺失时需要一个读突发传送总线事务读取一个贮存据传输重叠; 用8个总线时钟周期传输数据。读突发传送总线事务时间: 500ns 。