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

一、算法设计题

1． 编写递归算法，从大到小输出给定二叉排序树中所有关踺字不小于X 的数据元素。要求你的算法的时间复杂度为

【答案】算法如下:

从大到小输出二叉排序树bst 中所有关键字不小于x 的数据元素

，其中，2为排序树中所含结点数，m 为输出的关键字个数。

2． 串以静态存储结构存储，结构如下所述，试实现串操作equal 算法。

串被确认的最大长度

【答案】算法如下:

//本算法判断字符串S 和字符串t 是否相等，如相等返回1，否则返回

//在类C 中，一维数组下标从零开始

//两串相等

//算法结束

3． 已知关键字序列(

试写出一算法将(

利用(1)的算法写一个建大根堆的算法。 【答案】(1)算法如下:

''

假设

是大堆，本算法把

调成大堆

) 是大根堆。

) 调整为大根堆；

(2)

4． 已知一具有n

个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组

和

中(设该二叉树各结点的数据值均不相同) 。请写一建立该二叉树的二叉链表结构的非递

归算法。该二叉链表的链结点结构为(lchild, data , rchild) ，其中data 为数据域，lchild 与rhild 分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用nil 表示) 。

【答案】算法如下:

由二叉树的中序序列IN[ ]和后序序列POST[ ]建立二叉树

和

为栈，容量足够大

分別是中序序列和后序序列第一和最后元素的下标，初始调用时

，

初始化

取出栈顶数据

在中序序列中査等于

.

根结点的值

无左子树

将建立左子树的数据入栈

无右子树

的结点

右子树数据入

结束

:

5． 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT 中，写出计算该算术表达式值的算法。

【答案】算法如下:

以后序遍历算法求以二叉树表示的算术表达式的

值

.

求左子树表示的子表达式的值

求右子树表示的子表达式的值

二、应用题

6． 设散列表为函数分别为:

»

注:

％是求佘数运算

中，函数REV(X)表示颠倒十进制数x 的各位，如码序列为(2，8，31，20，19，18，53，27) 。

(1)试画出插入这8个关键码后的哈希表； (2)计算搜索成功的平均搜索长度ASL 。

【答案】(1)插入这8个关键码后的哈希表如表所示:

表 插入关键字后的哈希表

(2)

其

等。若插入的关键

，即表的大小为m=13。现采用双散列法解决冲突。散列函数和再哈希

7． 在二叉树的Llink-Rlink 存储表示中，引入“线索”的好处是什么？

【答案】在二叉链表表示的二叉树中，引入线索的目的主要是便于查找结点的前驱和后继。因为若知道各结点的后继，二叉树的遍历就非常简单。利用二叉链表结构查结点的左右子女非常方便，但其前驱和后继是在遍历中形成的。为了将非线性结构二叉树的结点排成线性序列，利用结点的空链域，左链为空时作为前驱指针，右链为空时作为后继指针。再引入左右标记ltag 和rtag ，规定:当当

时，lchild 指向左子树，当

时，Ichild 指向前驱；当

时，rchild 指向右子树，

时，rchild 指向后继。这样，在线索二叉树(特别是中序线索二叉树) 上遍历就消除了递归，

也不使用栈(利用后序线索二叉树查后继仍需要栈) 。