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

一、算法设计题

1． 输入一个字符串，内有数字和非数字字符，如:akl23x4561796073029ef4563。将其中连续的数字作为一个整体，依次存放到一数组a 中，例如123放入a[0]，456放入a[l]，...... 。编程统计其共有多少个整数，并输出这些数。

【答案】算法如下:

（ ）

//从键盘输入字符串，连续的数字字符算作一个整数，统计其中整数的个数

//整数存储到数组a ，i 记整数个数

//从左到右读入字符串

//'#'是字符串结束标记

//是数字字符

//数初始化

//拼数

//若拼数中输入了’#’，则不再输入

//输入非数字且非#时，继续输入字符

("共有个整数，它们是:

)

//每10个数输出在一行上

//算法结束

2． 设有顺序放置的n 个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后。重新安排时，对每粒砾石的颜色只能察看一次，并且只允许交换操作来调整砾石的位置。

【答案】算法如下:

r 为含有n 个元素的线性表，元素是具有红、白和蓝色的砾石，用顺序存储结构存储

本算法对其排序，使所有红色栎石在前，白色居中，蓝色在最后

当前元素是红色

当前元素是白色

当前元素是蓝色

3． 已知一具有n

个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组

和

中(设该二叉树各结点的数据值均不相同) 。请写一建立该二叉树的二叉链表结构的非递

归算法。该二叉链表的链结点结构为(lchild, data , rchild) ，其中data 为数据域，lchild 与rhild 分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用nil 表示) 。

【答案】算法如下:

由二叉树的中序序列IN[ ]和后序序列POST[ ]建立二叉树

和

为栈，容量足够大

初始化

取出栈顶数据

在中序序列中査等于

. 根结点的值

无左子树

将建立左子树的数据入栈

无右子树

右子树数据入

结束

:

的结点 分別是中序序列和后序序列第一和最后元素的下标，初始调用时

，

4． 假设以I 和0分别表示入栈和出栈操作。栈的初态和终态均为空，入桟和出找的操作序列可表示为仅由I 和0组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

(1)下面所示的序列中哪些是合法的？

A.

B.

C.

D.

(2)通过对(1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true ，否则返回false(假定被判定的操作序列已存入一维数组中) 。

【答案】(1)A和D 是合法序列，B 和C 是非法序列。

(2)设被判定的操作序列已存入一维数组A 中，算法如下:

//判断字符数组A 中的输入输出序列是否是合法序列。

//i为下标

//j和k 分别为I 和字母O 的个数

//入栈次数增

1

//不论A[i]是’I'或’〇' ，指针i 均后移

//算法结束

5． 试编写在带头结点的单链表中删除(一个) 最小值结点的(高效) 算法。delete(Linklist&L)

【答案】算法如下:

//L是带头结点的单链表，本算法删除其最小值结点

//P为工作指针。指向恃处理的结点。假定链表非空

//pre指向最小值结点的前驱

//q指向最小值结点，初始假定第一元素结点是最小值结点

//查最小值结点

//指针后移

//从链表上刪除最小值结点

//释放最小值结点空间

//结束算法Delete