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

一、算法设计题

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

【答案】算法如下:

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

2． 试将下列递归过程改写为非递归过程。

【答案】算法如下:

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

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

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

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

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

【答案】算法如下:

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

//字符栈，容量足够大

//设链表带头结点

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

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

//不是回文

4． 当一棵有n(

) 个结点的二叉树按顺序存储方式存储在

中时，试写一个算法，求

出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。

【答案】算法如下:

二叉树顺序存储在数组

中，本算法求结点i 和j 的最近公共祖先结点的值

下标为i 的结点的双亲结点的下标

下标为j 的结点的双亲结点的下标

所査结点的最近公共祖先的下标是

整型

5． 设排序二叉树中结点的结构为下述三个域构成:

Data :给出结点数据的值；left :给出本结点的左儿子结点的地址；right :给出本结点的右儿子结点的地址。设data 域为正整数，该二叉树根结点地址为T 。现给出一个正整数x 。请编写非递归程序，实现将data 域之值小于等于x 的结点全部删除掉。

，值是设元素类型为

【答案】算法如下:

非递归删除以r 为根的二叉排序树

栈，容量足够大，栈中元素是二叉排序树结点的指针

沿左分枝向下

出栈，沿栈顶结点的右子树向下刪除，释放被删除结点空间

在二叉排序树T 中删除所有小于等于x

的结点

根结点的值小于等于

x

删除二叉树p ，删除持续到" 根" 结点值大于x 或T 为空树为止

沿根结点左分支向下，査小干等于x 的结点

q 记P 的双亲

结点的值小于等于

x

再査原P 的右子树中小于等于x 的结点

二、应用题

6． 证明:置换选择排序法产生的初始归并段的长度至少为m(m是所用缓冲区的长度) 。

【答案】由置换选择排序思想，第一个归并段中第一个元素是缓冲区中最小的元素，以后每选一个元素都不应小于前一个选出的元素，故当产生第一个归并段时(即初始归并段) ，缓冲区中m 个元素中除最小元素之外，其他m －1个元素均大于第一个选出的元素，即当以后读入元素均小于输出元素时，初始归并段中也至少能有原有的m 个元素。

7． 某网络中的路由器运行OSPF 路由协议, 下表是路由器R1维护的主要链路状态信息(LSI), 下图是根据下表及R1的接口名构造出来的网络拓扑。

表 R1所维护的LSI