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

一、算法设计题

1． 编程:假设以数组Q[m]存放循环队列中的元素，同时以rear 和length 分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件，并写出相应的初始化(initqueue)，插入(enqueue)和删除(dequeue)元素的操作。

【答案】定义队列:

//循环队列占m 个存储单元

//rear指向队尾元素，length 为元素个数

(1)设cq 是seQueue 类型变量，则当(2)队列的初始化:

//cq为循环队列，本算法进行队列初始化

//算法结束 (3)队列的插入:

//cq是已如上定义的循环队列，本算法将元素x 入队

//队满

.

//计算插入元素位置

//将元素x 入队列

//修改队列长度

//算法结束

//cq是已如上定义的循环队列，本算法是出队算法，且返回出队元素

//队空

；//出队元素位置

//修改队列长度

时队列空，当 时队列满。

(4)队列的删除:

//返回队头元素

//算法结束

2． 写出一趟快速排序算法。

【答案】算法如下:

一趟快速排序算法，枢轴记录到位，并返回其所在位置

3． 试将下列递归过程改写为非递归过程。

【答案】算法如下:

4． 设计算法将一个带头结点的单链表A 分解为两个具有相同结构的链表B 、C , 其中B 表的结点为A 表中值小于零的结点，而C 表的结点为A 表中值大于零的结点(链表A 的元素类型为整型，要求B 、C 表利用A 表的结点) 。

【答案】算法如下:

//本算法将带头结点的单链表A 分解成数据域值小于零和大于零的两个单链表B 和

C

//为C 申请结点空间

//C初始化为空表

//P为工作指针

//B表初始化

//暂存P 的后继

//小于0的放入B 表

//将小于0的结点链人B 表

//P指向新的待处理结点

//算法结束

5． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为

。

【答案】算法如下:

用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值

n 为偶数时

r 最小值

("最大值) ；

二、应用题

6． 若森林共有n 个结点和b 条边(b

【答案】森林的n 个结点开始可看作是n 个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入b 条边将减少b 个连通分量，因而n 个结点b 条边的森林有n －b 棵树。

7． 某文件系统为一级目录结构, 文件的数据一次性写入磁盘, 已写入的文件不可修改, 但可多次创建新文件。请回答如下问题。

(1)在连续、链式、索引三种文件的数据块组织方式中, 哪种更合适? 要求说明理由。为定位文件数据块。需要在FCB 中设计哪些相关描述字段？