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

一、算法设计题

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

【答案】算法如下:

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

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

【答案】定义队列:

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

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

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

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

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

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

//队满

.

//计算插入元素位置

//将元素x 入队列

//修改队列长度

第 2 页，共 37 页

时队列空，当 时队列满。

//算法结束

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

//队空

；//出队元素位置

//修改队列长度

//返回队头元素

//算法结束

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

【答案】算法如下:

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

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

//交换A[i]与

A[j]

//算法Arrange 结束

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

【答案】算法如下:

第 3 页，共 37 页

(4)队列的删除:

5． 按图的宽度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点到顶点的路径

。

设有向图有n 个顶点

判断以邻接矩阵方式存储的有向图中是否存在由顶点到顶点的路径

是队列，容量足够大，元素是顶点编号

人队

到顶点

不存在路径

【答案】算法如下:

二、应用题

6． 文件存储结构的基本形式有哪些? 一个文件采用何种存储结构应考虑哪些因素？

【答案】文件的基本组织方式有顺序组织、索引组织、散列组织和链组织，常用的结构有顺序结构、索引结构、散列结构。

(1)顺序结构，相应文件为顺序文件，其记录按存入文件的先后次序顺序存放。顺序文传本质上就是顺序表。若逻辑上相邻的两个记录在存储位置上相邻，则为连续文件；若记录之间以指针相链接，则称为串联文件。顺序文件只能顺序存取，要更新某个记录，必须复制整个文件。顺序文件连续存取的速度快，主要适用于顺序存取，批量修改的情况。

(2)带索引的结构，相应文件为索引文件。索引文件包括索引表和数据表，索引表中的索引项包括数据表中数据的关键字和相应地址，索引表有序，其物理顺序体现了文件的逻辑次序，实现了文件的线性结构。索引文件只能是磁盘文件，既能顺序存取，又能随机存取。

(3)散列结构，也称计算寻址结构，相应文件称为散列文件，其记录是根据关键字值经哈希函数计算确定其地址，存取速度快，不需索引，节省存储空间。不能顺序存取，只能随机存取。

文件采用何种存储结构应综合考虑各种因素，如:存储介质类型、记录的类型、大小和关键字的数目以及对文件作何种操作。

第 4 页，共 37 页