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

一、算法设计题

1． 设有一个数组中存放了一个无序的关键序列

【答案】算法如下:

2． 从键盘上输入一串正整数，最后输入-1作为结束标志。如:8，7，1，22，98，46，... ，75，-1。请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设ltag ，data ，rta9，right) 。该二叉排序树上的结点结构为(teft，其中:data 域为结点的数据场。那么left 域中存在的是该结点的左儿子结点的地址。序遍历次序的前驱结点的地址。

【答案】算法如下:

从键盘上输入一串正整数，建立一棵初始为空的二叉排序树，同时也是线索二叉树

申请结点空间

结点赋值，其线

索初始化

查找结点的插入位置

f 是P 的双亲

第 2 页，共 36 页

。现要求将K n 放在将元素排序后

的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n(注:用程序实现) 。

，

，那么left 域中存放的是该结点的按中

，那么right

域中存放的是该结点的右儿子结点的地址。

，那么right 域中存放的是该结点的按中序遍历次序的后继结点地址。

根结点

左子女

修改线索

右子树根结点的值大于等于根结点的值

修改线索

读入下个数

算法结束

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

【答案】算法如下:

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

//局部最长平台

//新平台起点

(“最长平台长度

4． 在一个循环链队中只有尾指针(记为rear ，结点结构为数据域data ，指针域next) ，请给出这种队列的入队和出队操作的实现过程。

【答案】算法如下:

//rear是带头循环链队列的尾指针，本算法将元素X 插入到队尾

//申请结点空间

//将s 结点链入队尾

//rear指向新队尾

第 3 页，共 36 页

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

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

k)

//rear是带头结点的循环链队列的尾指针

//本算法执行出队操作，成功输出队头元素；否则给出出错信息

//s指向队头元素

//队头元素出队

//空队列

5． 设表达式以字符形式己存入数组E 中，'#'为表达式的结束符，

试写出判断表达式中括号

是否配对的C 语言描述算法:EXYX(E)(注:算法中可调用栈操作的基本算法) 。 【答案】算法如下:

//E[ ]是有n 字符的字符数组，存放字符串表达式，以'#'结束。本算法判断表达式中圆括号是否匹配

//s是一维数组，容量足够大，是用于存放括号的栈

//top用作栈顶指针

//'#先入栈，用于和表达式结束符号'#'匹配

//字符数组E 的工作指针

//逐字符处理字符表达式的数组

//读人其他字符，不进行处理

二、应用题

6． 试比较顺序文件、索引非顺序文件、索引顺序文件、哈希文件的存储代价，检索、插入、删除记录时的优点和缺点。

【答案】(1)顺序文件只能顺序查找，优点是批量检索速度快，不适于单个记录的检索。顺序，文件不能像顺序表那样插入、删除和修改，因文件中的记录不能象向量空间中的元素那样“移动”只能通过复制整个文件实现上述操作。

(2)索引非顺序文件适合随机存取，不适合顺序存取，因主关键字未排序，若顺序存取会引起磁头频繁移动。索引顺序文件是最常用的文件组织，因主文件有序，既可顺序存取也可随机存取。

第 4 页，共 36 页