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

一、应用题

1． 解答问题。设有数据逻辑结构为：

（1）画出这个逻辑结构的图示。

（2）相对于关系R ，指出所有的开始结点和终端结点。

（3）分别对关系R 中的开始结点，举出一个拓扑序列的例子。

（4）分别画出该逻辑结构的正向邻接表和逆向邻接表。

【答案】

⑴如图1所示：

图1

（2）开始结点（入度为0）:

（3）拓扑序列：

规则：开始结点为

或之后，若遇多个入度为0的顶点，按顶点编号顺序选择。

（4）正向邻接表如图2所示，逆向邻接表如图3所示：

终端结点（出度为0）:

图2 正向邻接表

图3 逆邻接表

2． 画出同时满足下列两个条件的两棵不同的二叉树。

（1）按前序遍历二叉树的顺序为ABCDE 。

（2）高度为5其对应的树（森林）的高度最大为4。

【答案】（1）满足条件的二叉树如图1所示：

图1

（2）满足条件的二叉树如图2所示：

图2

3． 某计算机的主存地址空间大小为256MB ，按字节编址，指令Cache 和数据Cache 分离，均有8个Cache 行，每个Cache 行大小为64B , 数据Cache 采用直接映射方式。现有两个功能相同的程序A 和B , 其伪代码如下所本：程序A :程序B :

假定int 类型数据用32位补码表示，程序编译时i , j , sum 均分配在寄存器中，数组a 按行优先方式存放，首地址320（十进制数）。请回答下列问题，要求说明理由或给出计算过程。

（1）若不考虑用于Cache —致性维护和替换算法的控制位，则数据Cache 的总容量为多少？ （2）数组数据号从0开始）？

（3）程序A 和B 的数据访问命中率各是多少? 哪个程序的执行时间更短？

【答案】（1）每个Cache 行对应一个标记项，标记项包括有效位、脏位、替换控制位以及标记位。由主存空间大小为256M 可知地址总长度为28位，其中块内地址为log264=6位，Cache 块号为log28=3位，不考虑一致性维护和替换算法的控制位，则Tag 的位数为28-6-3=19位，还需一位有效位，数据Cache 共有8行，故Cache 的总容量为

（2）数组a 在主存的存放位置及其与Cache 之间的映射关系如下图所示：

和各自所在的主存块对应的Cache 行号分别是多少（Cache 行

图

数组按行优先方式存放，首地址为320, 数组元素占4个字节。

Cache 行号

为

（3）数组a 的大小为逐行访问数

组a ，共需访问的次数为次，每个字块的第一个数未面中，因此未面中次数为

所在的主存块对应的所在的主存块对应的Cache 行号

为占用个主存块，按行优先存放，程序A 次，程序