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

一、算法设计题

1． 设从键盘输入一整数的序列:a 1，a 2，a 3，... ，a n ，试编写算法实现:用栈结构存储输入的整数，

当时，将入栈；当时，输出栈顶整数并出栈。算法应对异常情况(入栈满等) 给出相应的信息。

【答案】算法如下

:

栈空间容量

//s是元素为整数的栈，本算法进行入栈和出栈操作

//top为栈顶指针，定义top ＝0时为栈空

//n个整数序列进行处理

//从键盘读入整数序列

//读入的整数不等于﹣1时人栈

//读入的整数等于﹣1时出栈

//算法结束。

2． 设单链表的表头指针为h ，结点结构由data 和next 两个域构成，其中data 域为字符型。写出算法dc(h，n) ，判断该链表的前n 个字符是否中心对称。例如xyx ，xyyx 都是中心对称。

【答案】算法如下:

//h是带头结点的n 个字符元素的单链表，本算法判断链表是否中心对称

//i记下结点个数，s 是字符栈

//P是链表的工作指针，指向待处理的当前元素

//链表前一半元素入栈

//恢复最后的i 值

//若n 是奇数，后移过中心结点

//测试

是否中心对称

//链表中心对称

//链表不中心对称

//算法结束

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

【答案】算法如下:

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

4． 已知一个单链表中每个结点存放一个整数，并且结点数不少于2, 请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回ture ，否则返回false 。

【答案】算法如下:

//la是结点的元素为整数的单链表。本算法判断从第二结点开始

//毎个元素值是否等干其序号的平方减去其前驱的值，如是返回true ；否则，返回

false

//P是工作指针，初始指向链表的第二项

//pre是p 所指结点的前驱指针

//i是la 链表中结点的序号，初始值为

2

//结点值间的关

系符合题目要求

//当前结点的值不等于其序号的平方减去前驱的值

//未查到表尾就结束了

//成功返回

//算法结束

//假设无头结点，初始P 指向第一元素结点

中。若查找成功，则输出该记录在r 数组中的位置及其值，否则显示“not find ”信息。请编写出算法并简要说明算法思想。

//初始p ﹣＞next 指向第二项

//失败

//成功

5． 试编写在带头结点的单链表中删除(一个) 最小值结点的(高效) 算法。delete(Linklist&L)

【答案】算法如下:

//L是带头结点的单链表，本算法删除其最小值结点

//P为工作指针。指向恃处理的结点。假定链表非空

//pre指向最小值结点的前驱

//q指向最小值结点，初始假定第一元素结点是最小值结点

//查最小值结点

//指针后移

//从链表上刪除最小值结点

//释放最小值结点空间

//结束算法Delete

二、应用题

6． 给出一组关键字:29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程:

归并排序，每归并一次书写一个次序。

快速排序，每划分一次书写一个次序。

堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。

【答案】(1)2—路归并第一趟:18，29，25，47，12，58，10，51; 第二趟:18，25，29，47，10，12，51，58;

第三趟:10，12，18，25，29，47，51，58

(2)快速排序第一趟:10，18，25，12，29，58，51，47;

第二趟:10，18，25，12，29，47，51，88;

第三趟:10，12，18，25，29，47，51，88

(3)堆排序

建大堆:58，47，51，29，18，12，25，10; ①