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

一、应用题

1． （1）对于有向无环图，叙述求拓扑有序序列的步骤；

（2）对于图1，写出它的四个不同的拓扑有序序列。

图1

【答案】（1）对有向图，求拓扑序列步骤为：

1）在有向图中选一个没有前驱（即入度为0）的顶点并输出。

2）在图中删除该顶点及所有以它为尾的弧。

3）重复1）和2）, 直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。

（2）拓扑有序序列如图2:

图2 拓扑有序序列

2． 设内存中可利用空间已连成一个单链表，对用户的存储空间需求，一般有哪三种分配策略？

【答案】（1）首次适配法

从链表头指针开始查找，找到第一个大于等于所需空间的结点即分配。首次适配法适合事先

不知道请求分配和释放信息的情况，分配时需查询，释放时插在表头。

（2）最佳适配法

链表结点大小增序排列，找到第一个大于等于所需空间的结点即分配。最佳适配法适用于请求分配内存大小范围较宽的系统，释放时容易产生存储量很小难以利用的内存碎片，同时保留那些很大的内存块以备将来可能发生的大内存量的需求，分配与回收均需查询。

（3）最差适配法

链表结点大小逆序排列，总从第一个结点开始分配，将分配后结点所剩空间插入到链表适当位置。最差适配法适合请求分配内存大小范围较窄的系统，分配时不查询，回收时查询，以便插入适当位置。

3． 设二叉树BT 的存储结构如表：

表 二叉树BT 的存储结构

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

（1）画出二叉树BT 逻辑结构；

（2）写出按前序、中序、后序遍历该二叉树所得到的结点序列：

（3）画出二叉树的后序线索树。

【答案】（1）二叉树的逻辑结构如图1所示：

图1

（2）前序序列：ABCEDFHGIJ

中序序列：ECBHFDJIGA

后序序列：ECHFJIGDBA

（3）:二叉树的后续线索树如图2所示：

图2

4． 试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。

【答案】线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为O （n ）; 而在链式存储方式下，插入和删除时间复杂度都是0（1）。

5． 某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为16MB , 主存（物理）地址空间大小为1MB , 页面大小为4KB ; Cache 采用直接映射方式，共8行；主存与Cache 之间交换的块大小为32B ，系 统运行到某一时刻时，页表的部分内容和Cache 的部分内容分别如题a 图、题b 所示：图中页框号及标记字段的内容为十六进制形式。

图

a

图b

请回答下列问题。

（1）虚拟地址共有几位，哪几位表示虚页号? 物理地址共有几位，哪几位表示页框号（物理