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

一、应用题

1． 阅读下列算法，指出算法A 的功能和时间复杂性。

【答案】功能：将原单循环链表分解成两个单循环链表：其一包括结点h 到结点g 的前驱结点；另一个包括结点g 到结点h 的前驱结点。

时间复杂度：0（n ）。

2． 对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。

【答案】快速排序的思想如下：首先将待排序记录序列中的所有记录作为当前待排序区域，，凡其关键字不大干枢轴的记录均移动至该记录之前，以第一个记录的关键字作为枢轴（或支点）

凡关键字不小于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序割成两部分：

和

和

且

将分

然后再递归地将

进行快速排序。快速排序在记录有序时蜕变为起泡排序，可用“三者取中”法

改善其性能，避免最坏情况的出现。本题解答如下：

初始序列：[28]，07，39，10，65，14，61，17，50，21 21移动：21，07，39，10，65，14，61，17，50，[] 39移动：21，07，[]，10，65，14，61，17，50，39 17移动：21，07，17，10，65，14，61，[]，50，39 65移动：21，07，17，10，[]，14，61，65，50，39 14移动：21，07，17，10，14，[28]，61，65，50，39

3． 设中。

（1）将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少； （2）线性探测再散列法解决冲突。写出上述各关键字在表中位置。

第 2 页，共 37 页

五个字符的编码分别为1，2，3，4，5，并设标识符依以下次序出现

：

要求用哈希（Hash ）方法将它们存入具有10个位置的表

【答案】（1）构造的哈希函数为：哈希函数（2）关键字在表中的位置如表所示：

（关键字各字符编码之和）

表 关键字在表中的位置

4． 如果输入序列为123456, 试问能否通过栈结构得到以下两个序列：435612和135426; 请说明为什么不能或如何才能得到。

【答案】输入序列为123456, 不能得出435612, 其理由是，输出序列最后两元素是12, 前面4个元素（4356）得到后，栈中元素剩12, 且2在栈顶，栈底元素1不可能在栈顶元素2之前出栈。得到135426的过程如下：1入栈并出栈，得到部分输出序列1; 然后2和3入找，3出栈，部分输出序列变为13; 接着4和5入栈，5、4和2依次出栈，部分输出序列变为13542; 最后6入栈并出栈，得到最终结果135426。 5． 系统中有多个生产者进程和消费者进程，，共享用一个可以存1000个产品的缓冲区（初始为空）当缓冲区为未满时，生产者进程可以放入一件其生产的产品，否则等待；当缓冲区为未空时，消费者进程可以取走一件产品，否则等待。要求一个消费者进程从缓冲区连续取出10件产品后，其他消费者进程才可以取产品，请用信号量

求写出完整的过程；并指出所用信号量的含义和初值

【答案】设置5个信号量

empty :表示缓冲区是否为空，初值为1000 full ：

表示缓冲区是否为满，初值为0

mutex 1：生产者之间的互斥信号，初值为1 mutex2：消费者之间的互斥信号，初值为1 available :当前消费者能否访问缓冲区，初值为1

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

生产者进程：

生产一个产品；

产品送入buffer （in ）;

第 3 页，共 37 页

操作实现进程间的互斥和同步，要

消费者进程

取出产品buffer （out ）;

6． 在模试匹配KMP 算法中所用失败函数的定义中，为何要求真子串？且为最大真子串？

【答案】失败函数（即next ）的值只取决于模式串自身，若第j 个字符与主串第i 个字符失配时，假定主串不回溯，模式串用第k （即next[j]个字符与第i 个相比，有

为了

不因模式串右移与主串第i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个k 值，应取其中最大的一个。这样，因j-k 最小，即模式串向右滑动的位数最小，避免因右移造成可能匹配的丢失。

7． 从概念上讲，树、森林和二叉树是三种不同的数据结构，将树、森林转化为二叉树的基本目的是什么？ 并指出树和二叉树的主要区別。

【答案】（1）基本目的

树的孩子兄弟链表表示法和二叉树的二叉链表表示法本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。

（2）主要区别

一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分支的情况下，也必须指出是左子树还是右子树，树无此限制：三是二叉树允许为空，树一般不允许为空（有些书上考虑到与二叉树的转换，允许树为空）。

8． 假设计算机系统采用CSCAN （循环扫描）磁盘调度策略。使用2KB 的内存空间记录16384个磁盘块的空闲状态。

（1）请说明在上述条件下如何进行磁盘空闲状态的管理。

（2）设某单面磁盘旋转速度为每分钟6000转，每个磁道有100个扇区，相邻磁道间的平均移动时间为lms 。若在某时刻，磁头位于100号磁道处，并沿着磁道号增大的方向移动（如下图

第 4 页，共 37 页

两头匹配的