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

一、算法设计题

1． 已知递增有序的单链表A ，B 分别存储了一个集合，请设计算法以求出两个集合A 和B 的差集A ﹣B(即仅由在A 中出现而不在B 中出现的元素所构成的集合) ，并以同样的形式存储，同时返回该集合的元素个数。

【答案】算法如下:

//A和B 均是带头结点递增有序的单链表，本算法求两集合的差集，*n是结果集合中元素个数，初始为

//p和q 分别是链表A 和B 的工作指针

//pre为A 中p 所指结点的前驱结点的指针

//A

链表中当前结点指针后移

//B链表中当前结点指针后移

//处理A , B 中元素值相同的结点，

应刪除 //删除结点

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

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

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

【答案】算法如下:

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

//字符栈，容量足够大

//设链表带头结点

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

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

//不是回文

3． 编写递归算法，从大到小输出给定二叉排序树中所有关踺字不小于X 的数据元素。要求你的算法的时间复杂度为

【答案】算法如下:

从大到小输出二叉排序树bst 中所有关键字不小于x 的数据元素

。现要求将K n 放在将元素排序后

，其中，2为排序树中所含结点数，m 为输出的关键字个数。

4． 设有一个数组中存放了一个无序的关键序列

【答案】算法如下:

的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n(注:用程序实现) 。

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

当

时，将

入栈；当

时，输出栈顶整数并出栈。算法应对异常情况(入栈满等) 给

出相应的信息。

【答案】算法如下

:

栈空间容量

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

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

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

//从键盘读入整数序列

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

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

//算法结束。

二、应用题

6． 在模试匹配KMP 算法中所用失败函数的定义中，为何要求P 1P 2......P j 为P 1P 2......P j 两头匹配的真子串？且为最大真子串？

【答案】失败函数(即next) 的值只取决于模式串自身，若第j 个字符与主串第i 个字符失配时，假定主串不回溯，模式串用第k(即next[j])个字符与第i 个相比，有

为了不因

模式串右移与主串第i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个k 值，应取其中最大的一个。这样，因j ﹣k 最小，即模式串向右滑动的位数最小，避免因右移造成可能匹配的丢失。

7． 已知有5个顶点的图如下图所示

图

请回答下列问题

(1)写出上图的邻接矩阵A(行、列下标从0开始) 。 (2)求A2, 矩阵(3)

若已知具有么？

【答案】(1)邻接矩阵为

中位于0行3列元素值的含义是什么？

个顶点的邻接矩阵为B ,

则

非零元素的含义是什

(2)

为: