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

一、算法设计题

1． 已知一棵高度为K 具有n 个结点的二叉树，按顺序方式存储。

(1)编写用前序遍历树中每个结点的非递归算法；

(2)编写将树中最大序号叶结点的祖先结点全部打印输出的算法。 【答案】(1)算法如下:

全局变量

递妇遍历以顺序方式存储的二叉树bt ，i 是根结点下标(初始调用时为

1)

是桟s 的栈顶指针，栈容量足够大

访问根结点，设虚结点

以0表示

右子女的下标位置入

栈

沿左子女向下

取出栈顶元素

结束

(2)算法如下:

打印最大序号叶结点的全部袓先

找最大序号叶结点，该结点存储时在最后

的双亲结点

f

从结点c 的双亲结点直到根结点，

路径上所有结点均为祖先结点

逆序输出，最老的祖先最后输出

结束

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

【答案】算法如下:

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

r

//需要使用静态变量

//

规定

是字符串输入结束标志

//字符串逆序存储

//字符串结尾标记

//结束算法InvertStore

3． 若x 和y 是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。

【答案】算法如下:

//本算法判断两个顺序存储的串x 和y 是否相等，相等返回1，否则返回

//对应字符相等，指针后移

4． 辅助地址表的排序是不改变结点物理位置的排序。辅助地址表实际上是一组指针，用它来指出结点排序后的逻辑顺序地址。设

用

表示辅助地址表。初始时

减序) 算法的语句序列。

【答案】算法如下:

一趟排序无交换发生，结束

表示n 个结点的值，用

，在排序中，凡需对结点交换就用它的地址

来进行。例如当n=3时，对K(31，11，19) 则有T(2，3，1) 。试编写实现辅助地址表排序(按非递

5． 给定nxm 矩阵

并设

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

为O(m＋n) 。

【答案】算法如下:

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

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

//假定x 为整型

(“矩阵A 中无

算法search 结束。

元素\n"，x) ；

二、应用题

6． 将下列由三棵树组成的森林转换为二叉树(只要求给出转换结果) 。

【答案】森林转换为二叉树分以下三步: (1)连线(将兄弟结点相连，各树的根看作兄弟) 。

(2)切线(保留最左边子女为独生子女，将其他子女分支切掉) 。 (3)旋转(以最左边树的根为轴，顺时针向下旋转45度) 。 所以由上面三棵树转换得到的二叉树如图所示:

图