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

一、算法设计题

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

【答案】算法如下:

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

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

结束本题

2． 在输入数据无序的情况下，建立一个数据值为整型的递增有序的顺序存储线性表L ，且要求当输入相同数据值时，线性表中不能存在数据值相同的数据元素，试写出其算法。

顺序存储结构的线性表描述为:

线性表可能达到的最大长度}；

【答案】算法如下:

//在顺序表a 中査找值为x 的元素，査找成功返回0值，否则返回查找失败时的较大下标值

//当査找失败时，low ＝high ＋

1

//结束对分査找函数

//本过程生成顺序表

L

//顺序表L 初始化

//设x ＝9999时退出输入

//去查找x 元素

//不同元素才插入

//插入元素x ，线性表长度增

1

//结束过程creat

3． 设记录

的关键字为

。

，树结点

的败者树，要求除

指向败者记录，

和1

为全胜以外，只

记录下标。写一算法产生对应上述用O(1)辅助空间。

【答案】算法如下:

选得最小关键字记录后，沿从叶结点R[s]到根结点T[0]的路径调整败者树

是

指示新的胜者

到:_

小数

设置T 中" 败者" 的初值

依次从

出发调整败者

为完全二叉树T 的叶结点，本算法建立败者树

是与题中要求的关键字类型相同的机器最

的双亲结点

4． 给定(已生成) 一个带表头结点的单链表，设head 为头指针，结点的结构为(data，next) ，data 为整型元素，next 为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求:不允许使用数组作辅助空间) 。

【答案】算法如下:

//head是带头结点的单链表的头指针

//本算法按递增顺序输出单链表各结点的值，并释放结点所占的存储空间

//循环到仅剩头结点

//pre为元素最小值结点的前驱结点的指针

//P为工作指针

//记住当前最小值结点的前驱

//输出元素最小值结点的数据

//删除元素值最小的结点，释放结点

空间

//释放头结点

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

【答案】算法如下:

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

将其

插入到二叉排序树中

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

双亲

无值为x 的结点，插入之