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

一、算法设计题

1． 辅助地址表的排序是不改变结点物理位置的排序。辅助地址表实际上是一组指针，用它来指出结点排序后的逻辑顺序地址。设

用

表示辅助地址表。初始时

减序) 算法的语句序列。

【答案】算法如下:

一趟排序无交换发生，结束

表示n 个结点的值，用

，在排序中，凡需对结点交换就用它的地址

来进行。例如当n=3时，对K(31，11，19) 则有T(2，3，1) 。试编写实现辅助地址表排序(按非递

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

【答案】算法如下:

在后半部分继续进行划分

在前半部分继续进行划分

) 小元素。

3． 已知深度为h 的二叉树，以一维数组应的算法。

【答案】算法如下:

作为其存储结构，试编写一算法，求该二叉

树中叶结点的个数，为简单起见，设二叉树中元素结点为非负整数，要求写出算法基本思想及相

计算深度为h 、以一维数组BT 作为其存储结构的二叉树的叶结点数，n 为数组长度

记叶结点数

若结点无孩子，则

是叶子

存储在数组后一半的元素是叶结点

4． 请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink —rlink 法存储。

【答案】算法如下:

判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag 得出结论

中序遍历左子树

中序遍历的第一个结点不必判断

前驱指针指向当前结点

不是完全二叉树

中序遍历右子树

算法结束

判断二叉树t 是否是二叉排序树，若是，返回true ，否则，返回

false

若左右子树均为二叉

排序树

左子树中的最大值和右子树中

的最小值

不是二叉排序树

结束

求二叉树左子树的最大值

返回机器最小整数

求二叉树右子树的最小值

返回机器最大整数

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

。

【答案】算法如下:

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

n 为偶数时

r 最小值

("最大值) ；

二、应用题

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

【答案】设置5个信号量

empty :表示缓冲区是否为空, 初值为1000 full :表示缓冲区是否为满, 初值为0 mutex1:生产者之间的互斥信号, 初值为1 mutex2:消费者之间的互斥信号, 初值为1 available :当前消费者能否访问缓冲区, 初值为1