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

一、算法设计题

1． 写出算法，求出中序线索二叉树中给定值为X 的结点之后继结点，返回该后继结点的指针。线索树中结点结构为；

。其中，data 存放结点的值；lc 、rc 为指向左、

右孩子或该结点前驱、后继的指针，ltag 、rtag 为标志域，若值为0, 则lc 、rc 为指向左、右孩子的指针；若值为1，则lc 、rc 为指向其前驱、后继结点的指针。

【答案】算法如下:

先在带头结点的中序线索二叉树T 中査找给定值为x 的结点，假定值为x 的结点存在

设P 指向二叉树的根结点

结束

在中序线索二叉树T 中,, 求给定值为x 的结点的

后继结点

首先在T 树上査找给定值为x 的结点，由p 指向

' 若P 的右标志为1, 则P 的rc 指针指向其后继

结点P 的右子树中最左边的结点是结点P 的中序后继

结库

.

中关键字分二路分别按序插入到辅助向量

2． 二路插入排序是将待排关键字序列二路插入。编写实现2-路插入排序算法。

【答案】算法如下:

二路插入排序的算法

辅助存储

插人后部

第 2 页，共 35 页

前半部和后半部(注.. 向量d 可视为循环表) ，其原则为，先将r[1]赋给d[1]，再从r[2]记录开始分

折半査找插入位置

移动元素

插入有序位置

插入前部

移动元素

将序列复制回去

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

【答案】算法如下:

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

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

【答案】算法如下:

第 3 页，共 35 页

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

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

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

//空链表

//奇数序号结点在L1中

//偶数序号

结点逆置插入到L2中

//置L1

表尾

5． 给定(已生成) 一个带表头结点的单链表，设head 为头指针，结点的结构为(data，next) ，data 为整型元素，next 为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求:不允许使用数组作辅助空间) 。

【答案】算法如下:

//head是带头结点的单链表的头指针

//本算法按递增顺序输出单链表各结点的值，并释放结点所占的存储空间

//循环到仅剩头结点

//pre为元素最小值结点的前驱结点的指针

//P为工作指针

//记住当前最小值结点的前驱

//输出元素最小值结点的数据

//删除元素值最小的结点，释放结点

空间

//释放头结点

二、应用题

6． 对给定文件(28，07，39，10，65，14，61，17，50，21) 选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。

【答案】快速排序的思想如下:首先将待排序记录序列中的所有记录作为当前待排序区域，以

第 4 页，共 35 页