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

一、算法设计题

1． 写算法将单链表11拆成二个链表，其中以11为头的链表保持原来向后的链接，另一个链表的头为12，其链接方向与11相反，11包含原链表的奇数序号的结点，12包含原链表的偶数序号的结点。

【答案】算法如下:

//本算法将链表L1拆成L1和L2两个链表，L2链接方向与L1相反

//空链表

//奇数序号结点在L1中

//偶数序号

结点逆置插入到L2中

//置L1

表尾

2． 试编写一算法对二叉树按前序线索化。

【答案】算法如下:

设置前驱

对以线索链表为存储结构的二叉树BT 进行前序线索化

设置左线索

设置前驱的右线索

为建立右链做准备

前驱后移

左子树前序线索化

右子树前序线索化

第 2 页，共 36 页

结束

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

【答案】算法如下:

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

4． 已知某哈希表HT 的装填因子小于1，哈希函数H(key)为关键字的第一个字母在字母表中的序号。

(1)处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程序。

(2)处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。注意，此算法中规定不能用公式直接求解计算。

【答案】(1)算法如下:

按关键字第一个字母在字母表中的顺序输出各关键字

哈希地址

1~26

设哈希表初始值为

null

取关键字第一字母在字母表中的序号

(2)算法如下:

求链地址解决冲突的哈希表査找不成功时平均査找长度

记査找不成功的总的次数

按我们约定，査找不成功指到空指针为止

第 3 页，共 36 页

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

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

-

5． 设计算法将一个带头结点的单链表A 分解为两个具有相同结构的链表B 、C , 其中B 表的结点为A 表中值小于零的结点，而C 表的结点为A 表中值大于零的结点(链表A 的元素类型为整型，要求B 、C 表利用A 表的结点) 。

【答案】算法如下:

//本算法将带头结点的单链表A 分解成数据域值小于零和大于零的两个单链表B 和

C

//为C 申请结点空间

//C初始化为空表

//P为工作指针

//B表初始化

//暂存P 的后继

//小于0的放入B 表

//将小于0的结点链人B 表

//P指向新的待处理结点

//算法结束

二、应用题

6． 输入一个正整数序列(53，17，12，66，58，70，87，25，56，60) ，试完成下列各题。

(1)按次序构造一棵二叉排序树BS 。

(2)依此二叉排序树，如何得到一个从大到小的有序序列？ (3)画出在此二叉排序树中删除“66”后的树结构。 【答案】(1)构造的二叉排序树如图1所示:

图1二叉排序树

(2)若二叉树非空，要得到一个从大到小的有序序列可以先中序遍历右子树；再访问根结点；

第 4 页，共 36 页