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

一、应用题

1． 输入一个正整数序列（53，17，12，66，58，70，87，25，56，60），试完成下列各题。

（1）按次序构造一棵二叉排序树BS 。

（2）依此二叉排序树，如何得到一个从大到小的有序序列？ （3）画出在此二叉排序树中删除“66”后的树结构。 【答案】（1）构造的二叉排序树如图1所示：

图1 二叉排序树

（2）若二叉树非空，要得到一个从大到小的有序序列可以先中序遍历右子树；再访问根结点；最后中序遍历左子树。

（3）如图2所示：

图2

2． 数据类型和抽象数据类型是如何定义的? 二者有何相同和不同之处? 抽象数据类型的主要特点是什么? 使用抽象数据类型的主要好处是什么？

【答案】（1）数据类型的定义

数据类型是程序设计语言中的一个概念，它是一个值的集合和操作的集合。如c 语言中的整，其操作有加、减、乘、除、型、实型、字符型等。整型值的范围（对具体机器都应有整数范围）求余等。实际上数据类型是厂家提供给用户的已实现了的数据结构。

（2）抽象数据类型的定义

“抽象数据类型（ADT ）”指一个数学模型及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部 如何表示和实现无关。无论其内部结构如何变化，只要它的数学特性不变就不影响它的外部使用。

（3）两者的不同

抽象数据类型和数据类型实质上是一个概念。此外，抽象数据类型的范围更广，它已不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。

（4）抽象数据类型的主要特点

，而是向“科学”迈进了一步。 抽象数据类型的出现使程序设计不再是“艺术”（5）使用抽象数据类型的好处

使用抽象数据类型定义的软件模块含定义、表示和实现三部分，封装在一起，对用户透明（提，而不必了解实现细节。 供接口）

3． 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading ”和“being ”的存储映像如图所示。

图 存储映像7K 意图

设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为符i 所在结点的位置p ）。要求：

（1）给出算法的基本设计思想。 （2）根据设计思想，采用C 或【答案】

（1）算法的基本设计思想：

①分别求出strl 和str2所指的两个链表的长度m 和n ;

②将两个链表以表尾对齐：令指针p 、q 分别指向strl 和str2的头结点，若表中的第

个结点；若

则使q 指向链表中的第

表尾的长度相等。

③反复将指针p 和q 同步向后移动，并判断它们是否指向同一结点。若p 和q 指向同一结点，则该点即为所 求的共同后缀的起始位置。

（2）用C 语言算法描述如下：

请设计一

个时间上尽可能高效的算法，找出由strl 和str2所指的两个链表共同后缀的起始位置（如图中字

或JA V A 语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度。

则使p 指向链

个结点，即使指针p 和q 所指的结点到

两个指针同步向后移动

（3）参考答案的时间复杂度为：长度。

4． 设目标为

或

其中m 、n 分别为两个链表的

返回共同C 缀的起始点

模式为

（1）计算模式p 的nextval 函数值；

（2）不写出算法，只画出利用KMP 算法进行模式匹配时每一趟的匹配过程。 【答案】（1）P 的nextval 函数值为0110132（P 的next 函数值为0111232）。 （2）利用KMP （改进的nextval ）算法，每趟匹配过程如下： 第一趟匹配：abcab （i=5, j=5） 第二趟匹配：abc （i=7，j=3） 第三趟匹配：a （i=7，j=l） 第四趟匹配：

（成功）abcabaa （i=15，j=8）

5． 在某程序中，有两个栈共享一个一维数组空间的栈底。

（1）对栈1、栈2, 试分别写出（元素x ）入栈的主要语句和出栈的主要语句。 （2）对栈1、栈2, 试分别写出栈满、栈空的条件。 【答案】（1）入栈主要语句

出栈主要语句

分别是两个栈

（2）