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

一、算法设计题

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

用

表示辅助地址表。初始时

减序) 算法的语句序列。

【答案】算法如下:

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

表示n 个结点的值，用

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

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

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

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

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

全局变量

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

1)

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

访问根结点，设虚结点

以0表示

右子女的下标位置入

栈

沿左子女向下

取出栈顶元素

结束

(2)算法如下:

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

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

的双亲结点

f

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

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

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

结束

3． 以三元组表存储的稀疏矩阵A ，B 非零元个数分别为m 和n 。试用类PASCAL 语言编写时间复杂度为0(m＋n) 的算法将矩阵B 加到矩阵A 上去。A 的空间足够大，不另加辅助空间。要求描述所用结构。

【答案】算法如下:

＝大于非零元素个数的某个常量

//本算法实现以三元组表存储的各有m 和n 个非零元素两个稀疏矩阵相加，结果放到A 中

//L，p 为A ，B 三元组表指针，k 为结果三元组表榫针(下标

)

//行号不等时，行号大者的三元组为结果三元组表中一项

//A中当前项为结

果项

//B中当前项为结果

当前项

//行号相等时，比较列号

//结束行号相等时的处理

//结束行号比较处理

//结果三元组表的指针前移(减

1)

//结束WHILE 循环。

//处理B 的剩余部

分

//处理A 的剩余部

分

//稀疏矩阵相应元素相加时，有和为零的元素，因而元素总数＜m ＋

n

//三元组前移，使第一个三元组的下标

为

1

//修改结果三元组表中非零元素个数

//结束addmatrix

4． 设整数序列ai ，a2，a3，…，an ，给出求解最大值的递归程序。

【答案】算法如下:

//设整数序列存于数组a 中，共有n 个，本算法求解其最大值

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

【答案】算法如下:

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

将其

插入到二叉排序树中

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

双亲