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

一、算法设计题

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

【答案】算法如下:

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

标。

根结点

左子树或右子树的结点数

将左子树前序序列转

为后序序列

将右子树前序序列转为

后序序列

2． 设线性表存于A[l..size]的前mun 各分量中，且递增有序。请设计一个算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并在设计前说明设计思想，最后说明所设计算法的时间复杂度。

【答案】算法如下:

//A是Size 个元素空间但目前仅有num(num＜size}个元素的线性表 //本算法将元素x 插入到线性表中，并保持线性表的有序性

//题目要求下标从1开始

//对分査找元素x 的插入位置

//元素后移

//将元素x 插人

算法结束

第 2 页，共 37 页

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

设计思想:算法中当查找失败(即线性表中无元素X) 时，变量low 在变量high 的右面(low＝high ＋l) 。移动元素从位置low 开始，直到num 为止。

时间复杂度:查找的复杂度为O (logn)，插入的时间复杂度为O (n)，若用顺序查找，则查找的时间复杂度亦为O(n)。

3． 写出一个递归算法来实现字符串逆序存储。

【答案】算法如下:

//字符串逆序存储的递归算法

r

//需要使用静态变量

//

规定

是字符串输入结束标志

//字符串逆序存储

//字符串结尾标记

//结束算法InvertStore

4． 己知字符串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串没有

//字符串s2最后一个非空字符

第 3 页，共 37 页

个有效字符\n"，n) ；exit(0)；

}

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

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

个两端对齐的字符串exit(0)；

}

//置S2字符串结束标记

//将s1串其余部分送字符串

S3

//置串S3结束标记

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

【答案】算法如下:

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

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

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

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

//查最小值结点

//指针后移

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

//释放最小值结点空间

//结束算法Delete

二、应用题

6． s 是字符数组，s[0]中存放的是该字符串的有效长度，假设S[l..7]中字符串的内容为〃abcabaa" ，说明下列程序的功能及执行结果。

第 4 页，共 37 页