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

一、算法设计题

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

【答案】定义队列:

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

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

(1)设cq 是seQueue 类型变量，则当

(2)队列的初始化:

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

//算法结束

(3)队列的插入:

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

//队满

. //计算插入元素位置

//将元素x 入队列

//修改队列长度

//算法结束

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

//队空

；//出队元素位置

//修改队列长度

第 2 页，共 34 页 时队列空，当 时队列满。 (4)队列的删除:

//返回队头元素

//算法结束

2． 编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为A 〜Z 这26个字母和0〜9这10个数字) 。

【答案】算法如下:

（ ）

//统计输入字符串中数字字符和字母字符的个数

//初始化

//’#’表示输入字符串结束

'//数字字符

//字母字符

//输出数字字符的个数

("数字％d 的个数＝

//求出字母字符的个数

("字母字符％c 的个数＝

//算法结束。

3． 己知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序(非降序) 并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。

例如:

第一个数组为:4，12，28

第二个数组为:1，7，9，29，45

输出结果为:

第一个数组

第二个数组

【答案】算法如下:

//A和B 是各有m 个和n 个整数的非降序数组，本算法将B 数组元素逐个插入到A 中

//使A 中各元素均不大于B 中各元素，且两数组仍保持非降序排列

.

" 交换A[m﹣1]和B[0]

第 3 页，共 34 页

) ；

) ；

//寻找A[m﹣1]的插入位置

//寻找B[0]的插入位置

算法结束

4． 当一棵有n() 个结点的二叉树按顺序存储方式存储在中时，试写一个算法，求出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。

【答案】算法如下:

二叉树顺序存储在数组

中，本算法求结点i 和j 的最近公共祖先结点的值

下标为i 的结点的双亲结点的下标

下标为j 的结点的双亲结点的下标

所査结点的最近公共祖先的下标是，值是设元素类型为 整型

5． 己知字符串S1中存放一段英文，写出算法format(s1，s2，s3，n) ，将其按给定的长度n 格式化成两端对齐的字符串S2，其多余的字符送S3。

【答案】算法如下:

//将字符串si 拆分成字符串S2和字符串S3，要求字符串S2长度为n 且两端对齐

//滤掉s1左端空格

("字符串s1为空串或空格串\n")；exit(0)；

}

//字符串S1向字符串S2中

复制

(”字符串s1没有

//P指针也后退

//往后査找一个非空格字符作为串S2的尾字

符

("s1串没有个两端对齐的字符串exit(0)；} 个有效字符\n"，n) ；exit(0)；

} //若最后一个字符为空格，

则需向后找到第一个非空格字符

第 4 页，共 34 页