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

一、算法设计题

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

【答案】算法如下:

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

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

false

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

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

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

2

//结点值间的关

系符合题目要求

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

//未查到表尾就结束了

//成功返回

//算法结束

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

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

//失败

//成功

2． 已知二叉树丁的结点形式为(llink，data ，count ，riink) ，在树中查找值为X 的结点，若找到， 则记数(count)加1; 否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。

【答案】算法如下:

在二叉排序树t 中査找值为x 的结点，若査到，则其结点的count 域值增1，否则，

将其

插入到二叉排序树中

f 指向当前结点的査找值为x 的结点，

双亲

无值为x 的结点，插入之

査询成功，值域为x 的结点的count 增

1

3． 试将下列递归过程改写为非递归过程。

【答案】算法如下:

4． 设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。

【答案】(1)递归算法如下:

递减序输出二叉排序树t 中所有左子树为空右子树非空的结点数据域的值

(2)非递归算法如下:

递减序输出二叉排序树t 中所有左子树为空、右子树非空的结点的数据域的值

S 是二叉排序树结点指针的栈，容量足够大

沿右分支向下

去左分支

算法结束

5． 在二叉排序树的结构中，有些数据元素值可能是相同的，设计一个算法实现按递增有序打印结点的数据域，要求相同的数据元素仅输出一个，算法还应能报出最后被滤掉而未输出的数据元素个数，对如图所示的二叉排序树，输出为:10，12，13，15，18，21，27，35，42。滤掉3个元素。

图

【答案】算法如下:

递增序输出二叉排序树中结点的值，滤去重复元素

中序遍历左子树

是当前访问结点的前驱，调用本算法时初值为

null

记重复元素，调用

本算法时初值为

前驱后移