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

一、算法设计题

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

【答案】算法如下:

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

将其

插入到二叉排序树中

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

双亲

无值为x 的结点，插入之

査询成功，值域为x 的结点的count 增

1

2． 设有一个数组中存放了一个无序的关键序列

【答案】算法如下:

第 2 页，共 33 页

。现要求将K n 放在将元素排序后

的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n(注:用程序实现) 。

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

【答案】算法如下:

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

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

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

//元素后移

//将元素x 插人

算法结束

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

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

4． 设二叉树用二指针结构存储(可以是动态存储结构) ，元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。

【答案】算法如下:

在二叉树t 中査找结点值等于x 的结

点

结束

统计以t 为根结点的子树的叶结点数

n0

. 叶结点

输出并计数

第 3 页，共 33 页

结束

:

) 区分在遍

5． 假设在二叉链表的结点中增设两个域:parent 域指示其双亲结点:flag 域(取值为历的递推形式的算法。

【答案】算法如下:

在增加双亲指针

和标志域

的二叉树中，不用栈后序遍历二叉树

历过程中到达该结点时应继续向左、向右或访问该结点。试以此存储结构编写不用栈进行后序遍

向左

向右

访问根结点

找被访问结点的双亲

结束

二、应用题

6． 某程序中有如下循环代码段

P 起始地址为0804 8100H, 对应的汇编代码和机器代码如下表所示

。假设编译时变量sum 和i

分别分配在寄存器R1和R2中。常量N 在寄存器R6中, 数组A 的首地址在寄存器R3中, 程序段

表

执行上述代码的计算机M 采用32位定长指令字, 其中分支指令Bue 采用如下格式,

Op 为操作码:Rs 和Rd 为寄存器编号:OFFSET 为偏移量, 用补码表示。请回答下列问题, 并说

第 4 页，共 33 页