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

一、算法设计题

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

【答案】算法如下:

（ ）

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

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

//从左到右读入字符串

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

//是数字字符

//数初始化

//拼数

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

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

("共有

个整数，它们是:

)

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

//算法结束

2． 串以静态存储结构存储，结构如下所述，试实现串操作equal 算法。

串被确认的最大长度

【答案】算法如下:

//本算法判断字符串S 和字符串t 是否相等，如相等返回1，否则返回

//在类C 中，一维数组下标从零开始

//两串相等

//算法结束

3． 当一棵有n(

) 个结点的二叉树按顺序存储方式存储在

中时，试写一个算法，求

出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。

【答案】算法如下:

二叉树顺序存储在数组

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

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

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

所査结点的最近公共祖先的下标是

，值是

设元素类型为

整型

4． 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key 的记录。设此组记录存放于数组

【答案】算法如下:

本句的有无不影响査找结果

5． 以顺序存储结构表示串，设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。

【答案】算法如下:

中。若查找成功，则输出该记录在r 数组中的位置及其值，否则显示“not

find ”信息。请编写出算法并简要说明算法思想。

//串用一维数组s 存储，本算法求最长重复子串，返回其长度

//index记最长的串在s 串中的开始位置，max

记其长度

//length记局部重复子串长度，i 为字符数组下标

//上一个重复子串结束

//当前重复子串长

度大，则更新

max

//初始化下一重复子串的起始位置和长度

(”最长重复子串的长度为

.//算法结束

，在串中的位置

，max ，index) ；

时间复杂度:算法的时间复杂度为O(n)，每个字符与其后继比较一次。

二、应用题

6． 设输入序列为2，3，4，5，6，利用一个栈能得到序列2，5，3，4，6吗? 栈可以用单链表实现吗？

【答案】不能得到序列2，5，3，4，6。因为根据输入序列，2进桟之后，2出栈，3，4，5依次进栈。5出栈，此时栈中剩下3，4。因为4在栈顶，所以4应该比3先出栈，不能得到提供的序列。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点。

7． 解答问题。设有数据逻辑结构为:

(1)画出这个逻辑结构的图示。

(2)相对于关系R ，指出所有的开始结点和终端结点。 (3)分别对关系R 中的开始结点，举出一个拓扑序列的例子。 (4)分别画出该逻辑结构的正向邻接表和逆向邻接表。 【答案】(1)如图1所示:

图1