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

一、算法设计题

1． 请运用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第f(

【答案】算法如下:

在后半部分继续进行划分

在前半部分继续进行划分

2． 设要求按

是一个记录构成的数组，

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

) 小元素。

的内容调整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． —个有向图G=(V，E) 的平方图

，使得表示。

【答案】算法如下:

4． 设记录

的关键字为

。

，树结点

的败者树，要求除

指向败者记录，

和1

为全胜以外，只

且

满足下述性质

:

2

当且仅当存在某个顶点

2

。写一个算法从给定的G 求出G , G 和G 可分别用两个邻接表

记录下标。写一算法产生对应上述用O(1)辅助空间。

【答案】算法如下:

选得最小关键字记录后，沿从叶结点R[s]到根结点T[0]的路径调整败者树

是

指示新的胜者

到:_

小数

设置T 中" 败者" 的初值

依次从

的双亲结点

为完全二叉树T 的叶结点，本算法建立败者树

是与题中要求的关键字类型相同的机器最

出发调整败者

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

【答案】算法如下:

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

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

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

//链表前一半元素入栈

//恢复最后的i 值

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

//测试

是否中心对称

//链表中心对称

//链表不中心对称

//算法结束

二、应用题

6． 组织待检索文件的倒排表的优点是什么？

【答案】倒排表作为索引的优点是索引记录快，因为从次关键字值直接找到各相关记录的物理记录号，倒排因此而得名(因通常的查询是从关键字查到记录) 。在插入和删除记录时，倒排表随之修改，倒排表中具有相同次关键字的记录号是有序的。

7． KMP 算法(字符串匹配算法) 较Brute(朴素的字符串匹配) 算法有哪些改进？

【答案】朴素的模式匹配(Brute.Force)时间复杂度是

，KMP 算法有一定改进，时间复

杂度达到O(m＋n) 。主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP 算法的优点更为突出。

8． 试比较顺序文件、索引非顺序文件、索引顺序文件、哈希文件的存储代价，检索、插入、删除记录时的优点和缺点。

【答案】(1)顺序文件只能顺序查找，优点是批量检索速度快，不适于单个记录的检索。顺序，文件不能像顺序表那样插入、删除和修改，因文件中的记录不能象向量空间中的元素那样“移动”只能通过复制整个文件实现上述操作。

(2)索引非顺序文件适合随机存取，不适合顺序存取，因主关键字未排序，若顺序存取会引起磁头频繁移动。索引顺序文件是最常用的文件组织，因主文件有序，既可顺序存取也可随机存取。索引非顺序文件是稠密索引，可以“预查找”，索引顺序文件是稀疏索引，不能“预查找”，但