2018年北京信息科技大学计算机学院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 当一棵有n(
) 个结点的二叉树按顺序存储方式存储在
中时，试写一个算法，求
出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。
【答案】算法如下:
二叉树顺序存储在数组
中，本算法求结点i 和j 的最近公共祖先结点的值
下标为i 的结点的双亲结点的下标
下标为j 的结点的双亲结点的下标
所査结点的最近公共祖先的下标是
，值是
设元素类型为
整型
2． 若x 和y 是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。
【答案】算法如下:
//本算法判断两个顺序存储的串x 和y 是否相等，相等返回1，否则返回
//对应字符相等，指针后移
3． 试将下列递归过程改写为非递归过程。
【答案】算法如下:
4． 设要求按
是一个记录构成的数组，
是一个整数数组，其值介于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 个已经安排好
//算法结束
5． 写出一趟快速排序算法。
【答案】算法如下:
一趟快速排序算法，枢轴记录到位，并返回其所在位置
二、应用题
6． 快速排序的最大递归深度是多少? 最小递归深度是多少？
【答案】设待排序记录的个数为n ，则快速排序的最小递归深度为
，最大递归深度
n 。
7． 数据类型和抽象数据类型是如何定义的? 二者有何相同和不同之处? 抽象数据类型的主要特点是什么? 使用抽象数据类型的主要好处是什么？
【答案】(1)数据类型的定义
数据类型是程序设计语言中的一个概念，它是一个值的集合和操作的集合。如c 语言中的整型、实型、字符型等。整型值的范围(对具体机器都应有整数范围) ，其操作有加、减、乘、除、求余等。实际上数据类型是厂家提供给用户的已实现了的数据结构。
(2)抽象数据类型的定义
“抽象数据类型(ADT)”指一个数学模型及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部如何表示和实现无关。无论其内部结构如何变化，只要它的数学特性不变就不影响它的外部使用。
(3)两者的不同
抽象数据类型和数据类型实质上是一个概念。此外，抽象数据类型的范围更广，它已不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。
(4)抽象数据类型的主要特点
抽象数据类型的出现使程序设计不再是“艺术”，而是向“科学”迈进了一步。 (5)使用抽象数据类型的好处
使用抽象数据类型定义的软件模块含定义、表示和实现三部分，封装在一起，对用户透明(提供接口) ，而不必了解实现细节。
8． 设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值？
【答案】有两种方法，具体如下:
(1)对该算术表达式(二叉树) 进行后序遍历，得到表达式的后序遍历序列，再按后缀表达式求值。
(2)递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符(+、－、*、/等) 进行求值。
9． 设有正文AADBAACACCDACACAAD , 字符集为A , B , C , D , 设计一套二进制编码，使得上述正文的编码最短。
【答案】字符A ，B ，C ，D 出现的次数为9，1，5，3。其哈夫曼编码如下:A :1，B :000，C :01，D :001。