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

一、算法设计题

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

【答案】算法如下:

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

r

//需要使用静态变量

//

规定

是字符串输入结束标志

//字符串逆序存储

//字符串结尾标记

//结束算法InvertStore

2． 给定nxm 矩阵

并设

设计一算法判定x 的值是否在A 中，要求时间复杂度

为O(m＋n) 。

【答案】算法如下:

//n*m矩阵A ，行下标从a 到b ，列下标从c 到d ，本算法査找x 是否在矩阵A 中

//flag是成功査到x 的标志

//假定x 为整型

(“矩阵A 中无

算法search 结束。

元素\n"，x) ；

3． 已知二叉树T ，试写出复制该二叉树的算法(t→T) 。

【答案】算法如下:

复制二叉树t 的非递归算法

是二叉树的结点指针的队列，容量足够大

结束本题

4． 已知一个单链表中每个结点存放一个整数，并且结点数不少于2, 请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回ture ，否则返回false 。

【答案】算法如下:

//la是结点的元素为整数的单链表。本算法判断从第二结点开始

//毎个元素值是否等干其序号的平方减去其前驱的值，如是返回true ；否则，返回

false

//P是工作指针，初始指向链表的第二项

//pre是p 所指结点的前驱指针

//i是la 链表中结点的序号，初始值为

2

//结点值间的关

系符合题目要求

//当前结点的值不等于其序号的平方减去前驱的值

//未查到表尾就结束了

//成功返回

//算法结束

//假设无头结点，初始P 指向第一元素结点

//初始p ﹣＞next 指向第二项

//失败

//成功

5． 元素集合已存入整型数组树T 的非递归算法:CSBT(r，A)

【答案】算法如下:

以存储在数组K 中的n 个关键字，建立一棵初始为空的二叉排序

树

在调用时，

T=null

f 是P 的双亲

申请结点空间

根结点

左子女

右子树根结点的值大于等于根

结点的值

算法结束

中，试写出依次取A 中各值

构造一棵二叉排序

二、应用题

6． 二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和, 给定一棵二叉树T , 采用二叉链表存储, 节点结构为:

其中叶节点的weight 域保存该结点的非负权值。设root 为指向T 的根节点的指针, 设计求T 的WPL 的算法。要求:

(1)给出算法的基本设计思想; (2)使用C 或

语言, 给出二叉树结点的数据类型定义;

语言描述算法, 关键之处给出注释。

(3)根据设计思想, 采用C 或

【答案】(1)算法的基本思路是利用利用递归的思想来求解二叉树的带权路径长度, 如果当前节点不是叶子节点, 那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之和, 对于此函数要传入一个当前节点的树高的形参, 那么递归调用孩子节点时只需要将这个形参加一即可。

(2)typedef struct BiNode