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

一、应用题

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． 设输入序列为2, 3, 4, 5, 6, 利用一个栈能得到序列2, 5, 3, 4, 6吗? 栈可以用单链表实现吗？

【答案】不能得到序列2, 5, 3, 4, 6。因为根据输入序列，2进栈之后，2出找，3, 4, 5依次进

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

销

栈。5出栈，此时栈中剩下3, 4。因为4在栈顶，所以4应该比3先出栈，不能得到提供的序列。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点。

4． 已知图的邻接矩阵为：

当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出：

（1）以顶点V1为出发点的唯一的深度优先遍历序列；

（2）以顶点V1为出发点的唯一的广度优先遍历序列；

（3）该图唯一的拓扑有序序列。

1）V1，V4，V9, V10，V7, V6, V8，V3，V2, V5 【答案】（

（2） V1, V4, V3, V2, V9, V7, V6, Y5, V10, V8

（3） V1, V2, V5, V3, V4, V6, V8, V7, V9, VIO

5． 设有正文AADBAACACCDACACAAD ，字符集为A , B , C , D , 设计一套二进制编码，使得上述正文的编码最短。

A :1, B :000，C :01，D :001。 【答案】字符A , B , C , D 出现的次数为9, 1, 5, 3。其哈夫曼编码如下：

6． 如果两个串含有相等的字符，能否说它们相等？

【答案】仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同（即两串串值相等）。

7． 文件存储结构的基本形式有哪些? 一个文件采用何种存储结构应考虑哪些因素？

【答案】文件的基本组织方式有顺序组织、索引组织、散列组织和链组织，常用的结构有顺序结构、索引结构、散列结构。

（1）顺序结构，相应文件为顺序文件，其记录按存入文件的先后次序顺序存放。顺序文传本质上就是顺序表。若逻辑上相邻的两个记录在存储位置上相邻，则为连续文件；若记录之间以指针相链接，则称为串联文件。顺序文件只能顺序存取，要更新某个记录，必须复制整个文件。顺序文件连续存取的速度快，主要适用于顺序存取，批量修改的情况。

（2）带索引的结构，相应文件为索引文件。索引文件包括索引表和数据表，索引表中的索引项包括数据表中数据的关键字和相应地址，索引表有序，其物理顺序体现了文件的逻辑次序，实

第 3 页，共 17 页

现了文件的线性结构。索引文件只能是磁盘文件，既能顺序存取，又能随机存取。

（3）散列结构，也称计算寻址结构，相应文件称为散列文件，其记录是根据关键字值经哈希函数计算确定其地址，存取速度快，不需索引，节省存储空间。不能顺序存取，只能随机存取。

文件采用何种存储结构应综合考虑各种因素，如：存储介质类型、记录的类型、大小和关键字的数目以及对文件作何种操作。

8． 证明：具有n 个顶点和多于n-1条边的无向连通图G —定不是树。

【答案】具有n 个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形 成回路的连通图不再是树。

二、算法设计题

9． 设T 是一棵满二叉树，写一个把T 的后序遍历序列转换为前序遍历序列的递归算法。

【答案】算法如下：

//将满二叉树的后序序列转为前序序列，11、hl 、12、h2是序列初始和最后结点的下标。

//根结点

//左子树或右子树的结点数

//将左子树前序序列转为

后序序列

后序序列

10．当一棵有n （n ≤100）个结点的二叉树按顺序存储方式存储在bt[l..n]中时，试写一个算法. 求出二叉树中结点值分別为x 和y 的两个结点的最近祖先结点的值。

【答案】算法如下:

void Ancestor（ElemType bt[], x , y , int n）

//二叉树顺序存储在数组bt[1..n]中，本算法求结点i 和j 的最近公共祖先结点的值

{int i, j ;

while （i!=j）

if （i>j） i=i/2; //下标为i 的结点的双亲结点的下标

else j=j/2; //下标为j 的结点的双亲结点的下标

printfr （“所查结点的最近公共祖先的下标是%d，值是%d”, i , A[i]）; //设元素类型为整型}//Ancestor

第 4 页，共 17 页 //将右子树前序序列转为