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

一、算法设计题

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

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

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

(2)非递归算法如下:

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

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

沿右分支向下

去左分支

算法结束

2． 给定一个整数数组求出b 中最长平台的长度。

【答案】算法如下:

//求具有N 个元素的整型数组b 中最长平台的长度。

//局部最长平台

//新平台起点

第 2 页，共 36 页

b 中连续的相等元素构成的子序列称为平台。试设计算法，

(“最长平台长度

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

【答案】算法如下:

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

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

false

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

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

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

2

//结点值间的关

系符合题目要求

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

//未查到表尾就结束了

//成功返回

//算法结束

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

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

//失败

//成功

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

【答案】算法如下:

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

第 3 页，共 36 页

在b 数组中起始下标为”，1，

k)

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

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

//元素后移

//将元素x 插人

算法结束

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

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

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

【答案】算法如下:

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

树

在调用时，

T=null

f 是P 的双亲

申请结点空间

根结点

左子女

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

结点的值

算法结束

中，试写出依次取A 中各值构造一棵二叉排序

二、应用题

6． 快速排序的最大递归深度是多少? 最小递归深度是多少？

【答案】设待排序记录的个数为n ，则快速排序的最小递归深度为n 。

第 4 页，共 36 页

，最大递归深度