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

一、算法设计题

1． 设T 是一棵满二叉树，写一个把T 的后序遍历序列转换为前序遍历序列的递归算法。

【答案】算法如下:

将满二叉树的后序序列转为前序序列，

标。

根结点

左子树或右子树的结点数

将左子树前序序列转

为后序序列

将右子树前序序列转为

后序序列

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

例如:

第一个数组为:4，12，28 第二个数组为:1，7，9，29，45 输出结果为:

第一个数组

第二个数组

【答案】算法如下:

//A和B 是各有m 个和n 个整数的非降序数组，本算法将B 数组元素逐个插入到A 中 //使A 中各元素均不大于B 中各元素，且两数组仍保持非降序排列

.

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

第 2 页，共 38 页

是序列初始和最后结点的下

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

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

算法结束

3． 用邻接多重表存储结构，编写FERST-ADJ(G，V) 函数，函数返回值为第一个邻接点，若V 没有邻接点，返回零。

【答案】算法如下:

在邻接多重表g 中，求v 的第一邻接点, 若存在，返回第一邻接点，否则返回

确定顶点v 在邻接多重表向量中的下标, 不考虑不存在v 的情

况

返回第一邻接点，

和

中必有一个等于

i

取第一个边结点

4． 当一棵有n(

) 个结点的二叉树按顺序存储方式存储在中时，试写一个算法，求

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

【答案】算法如下:

二叉树顺序存储在数组

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

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

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

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

，值是

设元素类型为

整型

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

【答案】算法如下:

（ ）

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

第 3 页，共 38 页

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

//从左到右读入字符串

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

//是数字字符

//数初始化

//拼数

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

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

("共有

个整数，它们是:

)

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

//算法结束

二、应用题

6． 在模试匹配KMP 算法中所用失败函数的定义中，为何要求P 1P 2......P j 为P 1P 2......P j 两头匹配的真子串？且为最大真子串？

【答案】失败函数(即next) 的值只取决于模式串自身，若第j 个字符与主串第i 个字符失配时，假定主串不回溯，模式串用第k(即next[j])个字符与第i 个相比，有

为了不因

模式串右移与主串第i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个k 值，应取其中最大的一个。这样，因j ﹣k 最小，即模式串向右滑动的位数最小，避免因右移造成可能匹配的丢失。

第 4 页，共 38 页