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

一、填空题

1． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。

【答案】物理上相邻；指针

【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。

2． 在基于关键字比较且时间为O （nl 〇g2n ）的排序中，若要求排序是稳定的，则可选用_____，则可选用_____排序。 排序；若要求就地排序（及辅助空间为0（1））

【答案】归并；堆

3． 属于不稳定排序的有_____。

【答案】希尔排序、简单选择排序、快速排序、堆排序等

4． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。

【答案】

【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

5． 一个有2001个结点的完全二叉树的高度是_____。

【答案】11

【解析】完全二叉树的高度

6． 文件可按其记录的类型不同而分成两类，即_____和_____文件。

【答案】操作系统文件；数据库

7． 串是一种特殊的线性表，其特殊性表现在_____; 串的两种最基本的存储方式是_____、_____; 两个串相等的充分必要条件是_____。

【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等

8． —个字符串中_____称为该串的子串。

【答案】任意个连续的字符组成的子序列

9． 二叉树的前序序列和中序序列相同的条件是_____。

【答案】空树或任何结点至多只有右子树的二叉树

【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。

10．A 是一个任意给定的整数。free_tree设T 是一棵结点值为整数的二叉排序树，在下面的算法中，（T ）在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点；

首

先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下处理：（1）若找不到值为A 的结点，则返回根结点的地址（2）若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返否则返回根结点的地址。

【答案】

二、判断题

11．哈希表的结点中只包含数据元素自身的信息，不包含任何指针。（ ）

【答案】×

【解析】哈希表的结点中可以包括指针，指向其元素。如哈希链表。

12．在任何情况下，归并排序都比简单插入排序快。（ ）

【答案】×

【解析】错误。待排序序列为正序时，简单插入排序比归并排序快。

13．直接访问文件也能顺序访问，只是一般效率不高。（ ）

【答案】×

【解析】直接访问文件不能进行顺序访问，只能按关键字随机存取。在ISAM 文件上检索记录时，先从主索引出发找到相应的柱面索引，再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直至找到为止。

14．最小生成树的Krusakl 算法是一种贪心法。（ ）

【答案】√

【解析】在构建最小生成树常见的有三种贪心算法：kruskal , prim , soilion 。

15．数据元素是数据的最小单位。（ ）

【答案】

【解析】数据项是数据的不可分割的最小单位，而数据元素是数据的基本单位。

16．十字链表是无向图的一种存储结构。（ ）

【答案】×

【解析】十字链表是有向图的另一种链式存储结构。在十字链表中，对应于有向图的每条弧有一个结点，对应于每个顶点也有一个结点。类似于邻接表是无向图的一种链式存储结构。

17．二维以上的数组其实是一种特殊的广义表。（ ）

【答案】√