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

一、算法设计题

1． 结点类型和存储结构如下:

试设计一个排序算法，要求不移动结点的存储位置，只在结点的count 字段记录结点在排序中的序号，并将排序结果按升序输出。

【答案】算法如下:

对存储在数组R 中的记录进行排序

初始化

设R[0]作监视哨，Max 是该类型最大元

素

初始假定第一个元素有序

前驱

第一个元素

査找第i 个元素的序号

将笫i 个元素链入静态链表

2． 请运用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第f(

【答案】算法如下:

第 2 页，共 36 页

) 小元素。

在后半部分继续进行划分

在前半部分继续进行划分

3． 给定一个整数数组求出b 中最长平台的长度。

【答案】算法如下:

//求具有N 个元素的整型数组b 中最长平台的长度。

//局部最长平台

//新平台起点

(“最长平台长度

4． 编写算法，求二叉树的宽度。

【答案】算法如下:

求二叉树bt 的最大宽度

空二叉树宽度为

Q 是队列，元素为二叉树结点指针，容量

足够大

front 为队头指针，rear 为队尾指针

last 为同层最右结点在队列中的位置

temp 记当前层宽度，maxw 记最大宽度

根结点入队

同层元素数加

1

左子女入队

右子女入队

一层结束

指向下层最右元素

更新当前最大宽度

第 3 页，共 36 页

b 中连续的相等元素构成的子序列称为平台。试设计算法，

在b 数组中起始下标为”，1，

k)

5． 设计将数组A[n]中所有的偶数移到奇数之前的算法。要求不增加存储空间，且时间复杂性为〇(n)。

【答案】算法如下:

//n个整数存于数组A 中，本算法将数组中所有偶数排在奇数之前

//用类C 语言编写，数组下标从0开始

//交换A[i]与

A[j]

//算法Arrange 结束

二、应用题

6． 系统中有多个生产者进程和消费者进程, 共享用一个可以存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);

第 4 页，共 36 页