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

一、算法设计题

1． 已知P 是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表(

) 改造为(

【答案】算法如下:

//本算法将线性表

//q指向a 1结点

//r记住a l 结点的指

针

//先将a 1结点放到正确位置

//从a 2结点开始

//暂存后继

//对称放置

//恢复待处理结点

2． 辅助地址表的排序是不改变结点物理位置的排序。辅助地址表实际上是一组指针，用它来指出结点排序后的逻辑顺序地址。设

用

表示辅助地址表。初始时

减序) 算法的语句序列。

【答案】算法如下:

第 2 页，共 35 页

) 。

改造为

表示n 个结点的值，用

，在排序中，凡需对结点交换就用它的地址

来进行。例如当n=3时，对K(31，11，19) 则有T(2，3，1) 。试编写实现辅助地址表排序(按非递

一趟排序无交换发生，结束

3． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为

。

【答案】算法如下:

用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值

n 为偶数时

r 最小值

("最大值) ；

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

【答案】算法如下:

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

C

//为C 申请结点空间

//C初始化为空表

//P为工作指针

//B表初始化

//暂存P 的后继

//小于0的放入B 表

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

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

//算法结束

第 3 页，共 35 页

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

【答案】算法如下:

顺序表中记录个数

关键字

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

索引表的一项

关键字

记录中的其他数据

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

index

监视哨

关键字放入正确位置

第i 个记录的下标

二、应用题

6． 模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m ，模式的长度为n ，则在主串中寻找模式的KMP 算法的时间复杂性是多少? 如果某一模式

，请给出它的next 函数值及next 函数的修正值nextval 之值。

【答案】KMP 算法的时间复杂性是O(m＋n) 。

p 的next 和nextval 值分别为01112212321和01102201320。

第 4 页，共 35 页