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

一、算法设计题

1． 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key 的记录。设此组记录存放于数组

【答案】算法如下:

本句的有无不影响査找结果

2． 设要求按

是一个记录构成的数组，

是一个整数数组，其值介于1〜100之间，现

中。若查找成功，则输出该记录在r 数组中的位置及其值，否则显示“not

find ”信息。请编写出算法并简要说明算法思想。

的内容调整A 中记录的次序，比如当B[l]＝ll 时，则要求将A[l]的内容调整到A[ll]

中去。规定可使用的附加空间为O(1)。

【答案】算法如下:

//A是100个记录的数组，B 是整型数组，本算法利用数组B 对A 进行计数排序

//若B[i]＝i 则A[i]正好在自己的位置上，则不需要调整

//B[j]和B[k]交换

//r0是数组A 的元素类型，A[j]和A[k]

交换

//完成了一个小循环，第i 个已经安排好

//算法结束

3． 有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。

【答案】算法如下:

按递减次序输出二叉排序树结点的值

是元素为二叉树结点指针的栈，容量足够大

沿右子树向下

结束

4． 已知二叉树T ，试写出复制该二叉树的算法(t→T) 。

【答案】算法如下:

复制二叉树t 的非递归算法

是二叉树的结点指针的队列，容量足够大

结束本题

5． 已知顺序表中有m 个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到O(m)。

【答案】算法如下:

顺序表中记录个数

关键字

该关键字在顺序表中的下标

索引表的一项

关键字

记录中的其他数据

给有m 个记录的顺序表seq 建立索引表

index

监视哨

关键字放入正确位置

第i 个记录的下标

二、应用题

6． 假定采用带头结点的单链表保存单词, 当两个单词有相同的后缀时, 则可共享相同的后缀存储空间。例如, “loading ”和“being ”的存储映像如下图所示。

图 存储映像本意图

设str1和str2分别指向两个单词所在单链表的头结点, 链表结点结构为所在结点的位置p) 。要求:

(1)给出算法的基本设计思想。 (2)根据设计思想, 采用C 或

或JA V A 语言描述算法, 关键之处给出注释。

(3)说明你所设计算法的时间复杂度。 【答案】(1)算法的基本设计思想:

①分别求出str1和str2所指的两个链表的长度m 和n ;

②将两个链表以表尾对齐:令指针p 、q 分别指向str1和str2的头结点, 若m>n, 则使p 指向链表中的第n+1个结点; 若m

③反复将指针p 和q 同步向后移动, 并判断它们是否指向同一结点。若p 和q 指向同一结点, 则该点即为所求的共同后缀的起始位置。

(2)用C 语言算法描述如下:

, 请设计一

个时间上尽可能高效的算法, 找出由str1和str2所指的两个链表共同后缀的起始位置(如图中字符i