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

一、综合题

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

(1)(A(B(D，E) ，C(F)))

(2)(A(B(D，E) ，C))

(3)(A)

(4)(A(B(C，D(E))))

(5)（ ）

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

2． 对于后序线索二叉树，怎样查找任意结点的直接后继? 对于中序线索二叉树，怎样查找任意结点的直接前驱？

【答案】(1)后序线索树中结点的后继的方法如下:根结点无后继；当结点的rtag=1时，其右线索指向后继；当结点的rtag=0且是其双亲的右孩子，或是双亲的左孩子且双亲无右孩子时，其双亲是该结点的后继；当结点是其双亲的左孩子且双亲有右孩子时，其双亲结点右子树中最左下的叶结点是其后继。

(2)对中序线索二叉树的某结点，若其左标记等于1，则左孩子为线索，指向直接前驱；否则，其前驱是其左子树上按中序遍历的最后一个结点。

3． 只要找出一个具有n 个元素的集合的第

最适合? 给出实现的思想。

【答案】在具有n 个元素的集合中找第个最小元素，应使用快速排序方法。其基本思想如下:设n 元素的集合用一维数组表示，其第一个元素的下标为1，最后一个元素下标为n 。以第一个元素为“枢轴”，经过快速排序的一次划分，找到“枢轴”的位置i ，若i=k，则该位置的元素即为所求；若说，则在1至i －1间继续进行快速排序的划分；若i

小元素。

个最个最小元素，你所学过的排序方法中哪种

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

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

(1)若不考虑用于Cache 一致性维护和替换算法的控制位，则数据Cache 的总容量为多少？

(2)数组数据a[0][31]和a[l][1]各自所在的主存块对应的Cache 行号分别是多少(Cache行号从0开始）？

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

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

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

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

a[0][31]所在的主存块对应的Cache 行号为(320＋31*4)/64＝6;

a[1][1]所在的主存块对应的Cache 行号为

(3)数组a 的大小为256*256*4B＝218B ，占用218/64＝212个主存块，按行优先存放，程序A

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

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

5． 设二叉树BT 的存储结构如表:

表 二叉树BT 的存储结构

其中BT 为树根结点的指针，其值为6, Lchild 、Rchild 分别为结点的左、右孩子指针域data 为结点的数据域。试完成下列各题:

(1)画出二叉树BT 逻辑结构；

(2)写出按前序、中序、后序遍历该二叉树所得到的结点序列；

(3)画出二叉树的后序线索树。

【答案】(1)二叉树的逻辑结构如图1所示:

图1

(2)前序序列:ABCEDFHGIJ

中序序列:ECBHFDJIGA

后序序列:ECHFJIGDBA

(3)二叉树的后序线索树如图2所示: