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

一、应用题

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

【答案】（1）顺序文件只能顺序查找，优点是批量检索速度快，不适于单个记录的检索。顺序文件不能像顺序表那样插入、删除和修改，因文件中的记录不能象向量空间中的元素那样“移动”，只能通过复制整个文件实现上述操作。

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

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

2． 某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号 机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：

请添加必要的信号量和P 、V （或wait （ ）、signal （ ））操作，实现上述过程中的

互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。

【答案】（1）互斥资源：取机号，故设一个互斥信号量mutex 。

（2）同步问题：顾客需要获得空座位等待叫号，当营业员空闲时，将选取一位顾客为其服务。空座位的有、 无影响等待顾客数量，顾客的有、无决定两营业员是否能开始服务。另外，顾客获得空座位后，需要等待叫号和被服务，顾客与营业员就服务何时开始有同步关系。设信号量teller ，customer 和mutex 初值分别为0，0和1，设waiting 为整型量，表示排队的储户数量，其初始为0, 表示顾客初始时为0, 最大不超过10 （10把座椅），各进程的具体实现如下所示：

//座椅数，也是最多排队的储户数

//定义信号量

//储户进程

//先获得排队机

//若还有座椅则取号

//取号，占用座椅等待叫号

//告知系统储户加1

//释放排队机

//若没有座椅了，则不取号

//不取号，释放排队机

//离开

//并发调度无限循环

//等待储户的柜员资源

//排队等待服务的储户数量

//对排队机操作的互斥量

//在座椅上休息等待的储户数

//等待柜员叫号

//进入窗口被服务

//叫号

//需要获得排队机的控制权

//将等候的顾客数减1

//提供柜员服务

//释放排队机

//为储户服务

3． 设度为m 的树采用多重链表存储，毎个结点有m+1个域，其中有1个数据域，m 个指向孩子的指针。 则空指针的数目是多少？说明这种存储方式的利弊。

【答案】（1）空指针数目：n （n>0）个结点的m 度树共有nm 个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有nm-（n-1）=n（m-l ）+1个。

（2）利弊：这种存储结构统一，便于处理但空链域造成存储效率低。

4． 我们知道，对于n 个元素组成的线性表进行快速排序时，所需进行的比较次数与这n 个元素的初始排序有关。问：

（1）当n=7时，在最好情况下需进行多少次比较? 请说明理由。

（2）当n=7时，给出一个最好情况的初始排序的实例。

（3）当n=7时，在最坏情况下需进行多少次比较? 请说明理由。

（4）当n=7时，给出一个最坏情况的初始排序的实例。

【答案】（1）在最好情况下，每次划分能得到两个长度相等的子文件。假设文件的长度那么第一趟划分得到两个长度均为

以此类推，

总共进行

需2次，共10次即可。

（2）在最好情况下快速排序的原始序列实例：4，1，3，2，6，5，7。

（3）在最坏情况下，若每次用来划分的记录的关键字具有最大（或最小）值，那么只能得到左（或右）子文件，其长度比原长度少1。因此，若原文件中的记录按关键字递减次序排列，而要求排序后按递増次序排列时，快速排序的效率与起泡排序相同，其时间复杂度为

n=7时，最坏情况下的比较次数为21次。

（4）在最坏情况下快速排序的初始序列实例：7，6，5，4，3，2，1，要求按递増排序。

5． 在模试匹配KMP 算法中所用失败函数的定义中，为何要求

真子串？且为最大真子串？

【答案】失败函数（即next ）的值只取决于模式串自身，若第j 个字符与主串第i 个字符失配时，假定主串不回溯，模式串用第k （即next[j]个字符与第i 个相比，有为了不因模式串右移与主串第i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个k 值，应取其中最大的一个。这样，因j-k 最小，即模式串向右滑动的位数最小，避免因右移造成可能匹配的丢失。

6． 设输入序列为2, 3, 4, 5, 6, 利用一个栈能得到序列2, 5, 3, 4, 6吗? 栈可以用单链表实现吗？

【答案】不能得到序列2, 5, 3, 4, 6。因为根据输入序列，2进栈之后，2出找，3, 4, 5依次进栈。5出栈，此时栈中剩下3, 4。因为4在栈顶，所以4应该比3先出栈，不能得到提供的序列。

的子文件，第二趟划分得到4个长度均为的子文件，趟划分，各子文件的长度均为1，排序完毕。当n=7时，k=3，在最好情况下，第一趟需比较6次，第二趟分别对两个子文件（长度均为3，k=2）进行排序，各所以当两头匹配的