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

一、算法设计题

1． 设整数序列ai ，a2，a3，…，an ，给出求解最大值的递归程序。

【答案】算法如下:

//设整数序列存于数组a 中，共有n 个，本算法求解其最大值

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

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

【答案】算法如下:

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

初始化

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

素

初始假定第一个元素有序

前驱

第一个元素

査找第i 个元素的序号

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

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

【答案】算法如下:

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

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

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

记叶结点数

若结点无孩子，则

是叶子

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

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

用

表示辅助地址表。初始时

减序) 算法的语句序列。

【答案】算法如下:

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

表示n 个结点的值，用

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

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

5． 写出一个递归算法来实现字符串逆序存储。

【答案】算法如下:

//字符串逆序存储的递归算法

r

//需要使用静态变量

//

规定

是字符串输入结束标志

//字符串逆序存储

//字符串结尾标记

//结束算法InvertStore

二、应用题

6． 某博物馆最多可容纳500人同时参观, 有一个出入口, 该出入口一次仅允许个通过。参观者的活动描述如下:

Cobegin

参观者进程i : {

进门;

参观;

出门; } coend

请添加必要的信号量和P 、V(或wait （ ）、signal （ ）) 操作, 以实现上述操作过程中的互斥与同步。要求写出完整的过程, 说明信号量含义并赋初值。

【答案】定义两个信号量

博物馆可以容纳的最多人数

用于出入口资源的控制

7． 某文件系统空间的最大容量为

, 以磁盘块为基本分配单位, 磁盘块大小为1KB 。

文件控制块(FCB)包含一个512B 的索引表区。请回答下列问题。

(1)假设索引表区仅采用直接索引结构, 索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节? 可支持的单个文件最大长度是多少字节？

(2)假设索引表区采用如下结构:第0〜7字节采用<起始块号, 块数>格式表示文件创建时预分配的连续存储空间, 其中起始块号占6B , 块数占2B ; 剩余504字节采用直接索引结构, 一个索引项