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

一、综合题

1． 试比较顺序文件、索引非顺序文件、索引顺序文件、哈希文件的存储代价，检索、插入、删除记录时的优点和缺点。

【答案】(1)顺序文件只能顺序查找，优点是批量检索速度快，不适于单个记录的检索。顺序

，文件不能像顺序表那样插入、删除和修改，因文件中的记录不能象向量空间中的元素那样“移动”

只能通过复制整个文件实现上述操作。

(2)索引非顺序文件适合随机存取，不适合顺序存取，因主关键字未排序，若顺序存取会引起磁头频繁移动。索引顺序文件是最常用的文件组织，因主文件有序，既可顺序存取也可随机存取。索引非顺序文件是稠密索引，可以“预查找”，索引顺序文件是稀疏索引，不能“预查找”，但由于索引占空间较少，管理要求低，提高了索引的查找速度。

(3)散列文件也称直接存取文件，根据关键字的哈希函数值和处理冲突的方法，将记录散列到外存上。这种文件组织只适用于像磁盘那样的直接存取设备，其优点是文件随机存放，记录不必排序，插入、删除方便，存取速度快，无需索引区，节省存储空间。缺点是散列文件不能顺序存取，且只限于简单查询。经多次插入、删除后，文件结构不合理，需重组文件，这很费时。

2． 系统中有多个生产者进程和消费者进程, 共享用一个可以存1000个产品的缓冲区(初始为空) , 当缓冲区为未满时, 生产者进程可以放入一件其生产的产品, 否则等待; 当缓冲区为未空时, 消费者进程可以取走一件产品, 否则等待。要求一个消费者进程从缓冲区连续取出10件产品后, 其他消费者进程才可以取产品, 请用信号量P , V(wait, signed) 操作实现进程间的互斥和同步, 要求写出完整的过程; 并指出所用信号量的含义和初值

【答案】设置5个信号量

empty :表示缓冲区是否为空, 初值为1000

full :表示缓冲区是否为满, 初值为0

mutex1:生产者之间的互斥信号, 初值为1

mutex2:消费者之间的互斥信号, 初值为1

available :当前消费者能否访问缓冲区, 初值为1

定义变量in , out 分别为生产者和消费者进程所要使用的指针, 指向下一个可用的缓冲区单元, MaxNum=1000为缓冲区的大小, count 标志当前消费者已经取的产品的数量, 初值为0

生产者进程:

生产一个产品;

产品送入buffer(in);

消费者进程

取出产品buffer(out);

3． 对一个有 t 个非零元素的矩阵，用的数组来表示，其中第0行的三个元素分别为m ，n ，t ，从第一行开始到最后一行，每行表示一个非零元素；第一列为矩阵元素的行号，第二列为其列号，第三列为其值。对这样的表示法，如果需要经常进行该操作-确定任意一个元素A[i][j]在B 中的位置并修改其值，应如何设计算法可以使时间得到改善？

【答案】题中矩阵非零元素用三元组表存储，查找某非零元素时，按常规要从第一个元素开始查找，属于顺序查找，时间复杂度为0(n)。若使查找时间得到改善，可以建立索引，将各行行号及各行第一个非零元素在数组B 中的位置(下标) 放入一向量C 中。若查找非零元素，可先在数组C 中用折半查找到该非零元素的行号，并取出该行第一个非零元素在B 中的位置，再到B 中顺序(或折半) 查找该元素，这时时间复杂度为0(logn)。

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

【答案】(1)内部排序中的归并排序是在内存中进行的归并排序，辅助空间为O(n)。外部归并排序是将外存中的多个有序子文件合并成一个有序子文件，将每个子文件中记录读入内存后的排

序方法可采用多种内排序方法。外部排序的效率主要取决于读写外存的次数，即归并的趟数。

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

5． 某请求分页系统的局部页面置换策略如下:系统从0时刻开始扫描, 每隔5个时间单位扫描一轮驻留集(扫描时间忽略不计) , 本轮没有被访问过的页框将被系统回收, 并放入到空闲页框链尾, 其中内容在下一次被分配之前不被清空。当发生缺页时, 如果该页曾被使用过且还在空闲页框链表中, 则重新放回进程的驻留集中; 否则, 从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销, 初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程P 依次访问的<虚拟页号, 访问时刻>是:

。

请回答下列问题。

(1)访问<0, 4>时, 对应的页框号是什么？

(2)访问<1, 11>时, 对应的页框号是什么? 说明理由。

(3)访问<2, 14>时, 对应的页框号是什么? 说明理由。

(4)该策略是否适合于时间局部性好的程序? 说明理由。

【答案】(1)页框号为21。因为起始驻留集为空, 而0页对应的页框为空闲链表中的第三个空闲页框, 其对应的页框号为21。

(2)页框号为32。理由:因11>10故发生第三轮扫描, 页号为1、3的页框32、15在第二轮已处于空闲页框链表中, 此刻1页又被重新访问, 因此应被重新放回到驻留集中。其页框号为32。

(3)页框号为41。理由:因为第2页从来没有被访问过, 它不在驻留集中, 因此从空闲页框链表中取出链表头的页框41, 页框号为41。

(4)适合。理由:如果程序的时间局部性越好, 从空闲页框链表中重新取回的机会越大, 该策略的优势越明显。

6． 外排序中为何采用k 一路(k>2)合并而不用2—路合并? 这种技术用于内排序有意义吗? 为什么？

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