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

一、应用题

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

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

（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

2． 某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，故总线带宽为

第 2 页，共 35 页

（2）因为Cache 块大小为32B , 因此Cache 缺失时需要一个读突发传送总线事务读取一个贮存块。

（3）—次读突发传送总线事务包括一次地址传送和32B 数据传送:用1个总线时钟周期传输地址;

每隔，第一个体读数据花费40ns ，之后数据启动一个体工作（各进行1次存取）

存取与数据传输重叠；用8个总线时钟周期传输数据。读突发传送总线事务时间

：

s

BP 的CPU 执行时间包括Cache 命中时的指令执行时间和Cache 缺失时带来的额外开销。（4）

即执行时间=指令条数

间

：

3． 外排序中为何采用k 一路

么？

【答案】外排序用路归并是因为k 越小，归并趟数越多，读写外存次数越多，时间效率越低，故一般应大于最少的2-路归并。若将k-路归并的败者树思想单纯用于内排序，因其由胜者树改进而来，且辅助空间大，完全可由堆排序取代，故将其用于内排序效率并不高。

4． 证明：置换选择排序法产生的初始归并段的长度至少为m （m 是所用缓冲区的长度）。

【答案】证明：由置换选择排序思想，第一个归并段中第一个元素是缓冲区中最小的元素，

，缓以后每选一个元素都不应小于前一个选出的元素，故当产生第一个归并段时（即初始归并段）

冲区中m 个元素中除最小元素之外，其他m-1个元素均大于第一个选出的元素，即当以后读入元素均小于输出元素时，初始归并段中也至少能有原有的m 个元素。证毕。

5． 在二叉树的Llink-Rlink 存储表示中，引入“线索”的好处是什么？

【答案】在二叉链表表示的二叉树中，引入线索的目的主要是便于査找结点的前驱和后继，因为若知道各结点的后继，二叉树的遍历就非常简单。利用二叉链表结构查结点的左右子女非常方便. 但其前驱和后继是在遍历中形成的。为了将非线性结构二叉树的结点排成线性序列，利用结点的空链域，左链为空时作为前驱指针，右链为空时作为后继指针。再引入左右标记ltag 和rtag ，规定：当ltag=0时，lchild 指向左子树，当ltag=1时，lchild 指向前驱：当rtag=0时，rchild 指向右子树，当rtag=l时，rctiild 指向后继。这样，在线索二叉树（特别是中序线索二叉树）上遍历就消除了递归，也不使用栈（利用后序线索二叉树査后扔继续要栈）。

6． 在树和树中查找关键字时，有什么不同？

【答案】在树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。树的非终端结点是索引部分，其查找从根开始，从根往下查到关键

. 树还可以在最下层从最小关字后，要继续查到最下层结点，得到查找成功与否的结论。另外，

键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。

第 3 页，共 35 页 时钟周期*命中率+访存次数*缺失率*缺失损失。命中时的指令执行时指令执行过程中的CPU 执行时间

：Cache 缺失时的额外开

销 合并而不用2—路合并? 这种技术用于内排序有意义吗? 为什

7． 已知有5个顶点的图G 如下图所示

请回答下列问题

（1）写出图G 的邻接矩阵A （行、列下标从0开始）。

（2）求什么？

【答案】（1）邻接矩阵为

矩阵中位于0行3列元素值的含义是什么？ 非零元素的含义是（3）若已知具有n （n>=2）个顶点的邻接矩阵为B ，则

（2）

为：

0行3列的元素的含义是顶点0到顶点3间是相通的，并且路径长度为2的路径有2条。 （3）中非零元素的含义是：假设此顶点位于i 行j 列，表示从i 结点到j 结点路径长度为m 的路径的条数。

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

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

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

（2）带索引的结构，相应文件为索引文件。索引文件包括索引表和数据表，索引表中的索引

第 4 页，共 35 页