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

一、算法设计题

1． 试设计一个C 语言算法(或C 语言程序) :用单链表做存储结构，以回车符为结束标志，输入一个任意长度的字符串，然后判断该字符串是否为“回文”(正向读和反向读时，串值相同的字符串称为“回文”) ，输出信息“Yes ”或“NO ”；最后删除字符串并释放全部空间。例如:

若输入“ABCD12321DCBA”是回文，则输出“Yes”； 若输入“ABCD123DCBA”，不是回文，则输出“NO”。

要求:定义相关数据类型，不得使用数组(顺序表) 做字符串的存储结构和辅助存储空间。假定字符串的长度为n ，试分析上述算法的时间复杂度。

【答案】算法如下:

//本算法判断数据域为字符且长为n 的单链表是否是”回文" ，返回1或0表示成功或失败

//字符栈，容量足够大

//设链表带头结点

//前一半字符入栈，链表指针后移

//若链表有奇数个结点，则跳过中间结点

//不是回文

2． 设记录

的关键字为

。

，树结点

的败者树，要求除

指向败者记录，

和1

为全胜以外，只

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

【答案】算法如下:

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

是

指示新的胜者

第 2 页，共 34 页

的双亲结点

到:_

小数

设置T 中" 败者" 的初值

依次从

出发调整败者

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

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

3． 在一棵以二叉链表表示的二叉树上，试写出按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目的算法。

【答案】算法如下:

层次遍历二叉树，并统计度为1的结点的个数

统计度为1的结点的个数

是以二叉树结点指针为元素的队列

出队，访问结点

度为1的

结点

非空左子女入队

非空右子女入队

返回度为1的结点的个数

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

) 改造为(

【答案】算法如下:

//本算法将线性表

//q指向a 1结点

//r记住a l 结点的指

针

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

//从a 2结点开始

第 3 页，共 34 页

) 。

改造为

//暂存后继

//对称放置

//恢复待处理结点

5． 串以静态存储结构存储，结构如下所述，试实现串操作equal 算法。

串被确认的最大长度

【答案】算法如下:

//本算法判断字符串S 和字符串t 是否相等，如相等返回1，否则返回

//在类C 中，一维数组下标从零开始

//两串相等

//算法结束

二、应用题

6． 证明:在二叉树的三种遍历序列中，所有叶结点间的先后关系都是相同的。要求每步论断都指出根据。

【答案】前序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。若将“根”去掉，三种遍历就剩“左右”。三种遍历中的差别就是访问根结点的时机不同。二叉树是递归定义的，对左右子树均是按左右顺序来遍历的，因此所有叶结点间的先后关系都是相同的。

7． 索引顺序存取方法(ISAM)中，主文件已按关键字排序，为何还需要主关键字索引？

【答案】ISAM 是专为磁盘存取设计的文件组织方式。即使主文件关键字有序，但因磁盘是以盘组、柱面和磁道(盘面) 三级地址存取的设备，因此通常对磁盘上的数据文件建立盘组、柱面和磁道(盘面) 三级索引。在ISAM 文件上检索记录时，先从主索引(柱面索引的索引) 找到相应柱面索引。再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直到查到为止；反之，若找遍该磁道而未找到所查记录，则文件中无此记录。

第 4 页，共 34 页