2018年北京市培养单位光电研究院864程序设计之数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． 组成串的数据元素只能是_____。
【答案】字符
2． 一个算法具有5个特性: _____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
3． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关，即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性
4． 外排序的基本操作过程是_____和_____。
【答案】生成有序归并段(顺串) ；归并
5． 一个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
6． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
7． VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
8． 在有n 个顶点的有向图中，每个顶点的度最大可达_____。
【答案】2(n－1)
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n －1。
9． 实现字符串拷贝的函数strcpv 为:
(_____)
【答案】s++＝*t++或(*s++＝*t++)!＝'\0’
10．阅读下列程序说明和程序，填充程序中的_____。
【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示。
本程序采用非递归的方法，设立一个堆栈stack 存放还没有转换过的结点，它的栈顶指针为tp 。交换左、右子树的算法为:
(1)把根结点放入堆栈。
(2)当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。
(3)重复(2)直到堆栈为空时为止。
【答案】
【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈是否为空，如果不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。
二、判断题
11．数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ）
【答案】X
【解析】数据的逻辑结构是指数据元素之间的逻辑关系。
12．哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念（ ）
【答案】×
【解析】哈希文件是使用一个函数(算法) 来完成一种将关键字映射到存储器地址的映射，根据用户给出的关键字，经函数计算得到目标地址，再进行目标的检索。哈希表是根据关键码值而直接进行访问的数据结构。
13．强连通分量是无向图的极大强连通子图。（ ）
【答案】×
【解析】强连通分量是对有向图而言的，一般在无向图中讨论连通性。
14．对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（ ）
【答案】×
【解析】索引顺序存取方法插入操作比较麻烦，对于处理大量数据，会有大量的记录进入溢出区，而基本区中又浪费很多空间。
15．取线性表的第i 个元素的时间同i 的大小有关。（ ）
【答案】 ×
【解析】不一定，如果是顺序存储结构，它访问数据元素时的时间效率都是O(1)。
16．堆肯定是一棵平衡二叉树。（ ）
【答案】×
【解析】堆是n 个元素的序列，排序树，更不会是平衡二叉树。
可以看成是完全二叉树，但相对于根并无左小右大的要求，故其既不是二叉
17．数据元素是数据的最小单位。（ ）
【答案】 ×
【解析】数据项是数据的不可分割的最小单位，而数据元素是数据的基本单位。
18．就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（ ）
【答案】×
【解析】折半查找最小，分块查找次之，顺序查找最大。分块查找的速度虽然不如折半查找算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序。当结点很多且块数很大时，对索引表可以采用折半查找，这样能够进一步提高查找的速度。
19．对于有n 个结点的二叉树，其高度为log 2n 。（ ）
【答案】 ×
【解析】例如n 结点的单枝树，高度就为n 。
20．顺序存储结构的主要缺点是不利于插入或删除操作。（ ）
【答案】 √
【解析】因为顺序表的插入删除会移动大量的元素。
三、算法设计题