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

一、应用题

1． 下列广义表，可以唯一对应一棵二叉树的有？并归纳出唯一对应的条件。

【答案】唯一对应一棵二叉树的有（2）、（3）和（5）。唯一对应的条件：空表、只有一个元素的表、每个子表个数是零或是2的表。

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

图1

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

图2 图3

3． 设中。

（1）将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少； （2）线性探测再散列法解决冲突。写出上述各关键字在表中位置。 【答案】（1）构造的哈希函数为：哈希函数（2）关键字在表中的位置如表所示：

表 关键字在表中的位置

（关键字各字符编码之和）

五个字符的编码分别为1，2，3，4，5，并设标识符依以下次序出现

：

要求用哈希（Hash ）方法将它们存入具有10个位置的表

4． 设散列表为数分别为

：

注：％是求余数运算中，函数码序列为

（2）计算搜索成功的平均搜索长度

表示颠倒十进制数x 的各位，如

即表的大小为

，现采用双散列法解决冲突。散列函数和再哈希函

其

等。若插入的关键

（1）试画出插入这8个关键码后的哈希表；

【答案】（1）插入这8个关键码后的哈希表如表所示：

表 插入关键字后的哈希表

（2）

5． 将算术表达式（（a+b）+c*（d+e）+f）*（g+h）转化为二叉树。

【答案】该算术表达式转化的二叉树如图所示。

图

6． 某计算机的主存地址空间大小为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 ，共需访问的次数为A 的数据访问命中率为

次，每个字块的第一个数未面中，因此未面中次数为

Cache 总容量为

次，程序数组a —行的大

占用

个主存块，按行优先存放，程序A

所在的主存块对应的

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

为

小为1KB 正好是Cache 容量的2倍，可知不同行的同一列数组元素使用的是同一个Cache 单元，而程序B 逐列访问数组a 的数据时，都会将之前的字块置换出，也即每次访问都不会面中，故程序B 的数据访问命中率是0, 因此程序A 的执行过程更短。