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

一、应用题

1． S 是字符数组

，中存放的是该字符串的有效长度，

假设中字符串的内容为

说明下列程序的功能及执行结果。

【答案】本程序的功能是求字符串的nextval 函数，程序执行结果是0110132。

2． 某文件系统空间的最大容量为4TB 以磁盘块为基本分配单位，磁盘块大小为1KB 。文件控制块（FCB ）包含一个512B 的索引表区。请回答下列问题。

（1）假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节? 可支持的单个文件最大长度是多少字节？

（2）假设索引表区采用如下结构：第0〜7字节采用<起始块号，块数>格式表示文件创建时预分配的连续存储空间，其中起始块号占6B ，块数占2B ; 剩余504字节采用直接索引结构，一个索引项占6B ，则可支持的单个文件最大长度是多少字节? 为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理 值并说明理由。

【答案】

（1）文件系统存储空间共有块数可存放

（2） 为表示个块号，索引表项占512B 个索引项，每个索引项对应一个磁盘块，故最大文件长度：块号占6字节，块数占2字节的情形下，最大文件长度

：

理由：合理的起始块号和块数所占字节数分别为

块数占4B 或以上，就可表示4TB 大小的文件长度，达到文件系统的空间上限。

3． 以归并算法为例，比较内部排序和外部排序的不同，说明外部排序如何提高操作效率。

【答案】（1）内部排序中的归并排序是在内存中进行的归并排序，辅助空间为

外部归

并排序是将外存中的多个有序子文件合并成一个有序子文件，将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。外部排序的效率主要取决于读写外存的次数，即归并的趟数。

（2）因为归并的趟数其中，m 是归并段个数，k 是归并路数。增大k 和减少m 都可减少归并趟数。应用中通过败者树进行多（k ）路平衡归并和置换一选择排序减少m ，来提高外部排序的效率。

4． 设有6个有序表A 、B 、C 、D 、E 、F , 分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。

（1）给出完整的合并过程，并求出最坏情况下比较的总次数。

（2）根据你的合并过程，描述

n

【答案】

（1）6个表的合并顺序如下图所示。

个不等长升序表的合并策略，并说明理由。

对应于合并过程的哈夫曼树

根据上图中的哈夫曼树，6个序列的合并过程为：

第1次合并：表A 与表B 合并，生成含45个元素的表AB ;

第2次合并：表AB 与表C 合并，生成含85个元素的表ABC ;

第3次合并：表D 与表E 合并，生成含110个元素的表DE ;

第4次合并：表ABC 与表DE 合并，生成含195个元素的表ABCDE ;

第5次合并：表ABCDE 与表F 合并，生成含395个元素的最终表。

由于合并两个长度分别为m 和n 的有序表，最坏情况下需要比较m+n-1次，故最坏情况下比较的总次数计算如下：

第1次合并：最多比较次数= 10+35-1=44;

第2次合并：最多比较次数=45+40-1 = 84;

第3次合并：最多比较次数=50+60-1 = 109;

第4次合并：最多比较次数=85+110-1 = 194;

第5次合并：最多比较次数= 195+200-1 = 394; 比较的总次数最多为：44+84+109+194+394 = 825。

（2）各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，

可以获得最坏情况下最佳的合并效率。

5． 请回答下列关于图（Graph ）的一些问题：

（1）有n 个顶点的有向强连通图最多有多少条边? 最少有多少条边？

（2）表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素? 是否稀疏矩阵？

（3）对于一个有向图，不用拓扑排序，如何判断图中是否存在环？

【答案】⑴最多有n （n-l ）条边；最少有n 条边。

（2） 有有个矩阵元素；不一定是稀疏矩阵（稀疏矩阵的定义是非零元素个数远小于该矩阵元素个数，且分 布无规律）。

（3）使用深度优先遍历，按退出DFS 过程的先后顺序记录下的顶点是逆向拓扑有序序列。如果在执行DFS （V ） 未退出前，出现顶点u 到v 的回边，则说明存在包含顶点v 和顶点u 的环。

6． 某计算机字长16位，采用16位定长指令字结构，部分数据通路结构如下图所示，图中所有控制信号为1时表示有效，为0时表示无效，例如控制信号MDRinE 为1表示允许数据从DB 打入MDR ，MDRin 为1表示允许数据从内总线打入MDR 。假设MAR 的输出一直处于使能状态。加法指令“ADD （Rl ）, R0”的功能为（R0）+（（R1））－（R1）, 即将R0中的数据与R1的内容所指主存单元的数据相加，并将结果送入R1的内容所指主存单元中保存。

图

下表给出了上述指令取指和译码阶段每个节拍（时钟周期）的功能和有效控制信号，请按表中描述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号。

表