2017年北京市培养单位计算机与控制学院863计算机学科综合(专业)之数据结构考研题库
● 摘要
一、填空题
1． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4; 2
2． 设为哈夫曼树的叶结点数日，则该哈夫曼树共有_____个结点。
【答案】
【解析】哈夫曼树只有度为0和2的节点。
3． 循环队列的引入，目的是为了克服_____。
【答案】假溢出时大量移动数据元素
【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。
4． 文件由_____组成；记录由_____组成。
【答案】记录；数据项 5
．
求REPLACE （S ，V , m ）=_____。
【答案】
6． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
7． 高度为h 的堆中，最多有_____元素，最少有_____个元素。
【答案】
当最后一层只有
【解析】当这个堆构成的是满二叉树时，元素的个数最多，
元素个数为一个元素时，此时堆的元素个数最少，元素个数为
已
知
8． 阅读下列程序，指出其功能，并写出空格处应填上的语句。
【答案】
【解析】本题是在哈希表ht[]中插入值为的元素，如该元素已在哈希表中，报告出错。
9． VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
10．在哈希函数
中，P 值最好取_____。
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
二、判断题
11．若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（ ）
【答案】×
【解析】在含有N 个带权叶子结点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也叫做最优二叉树。关键字有序，可能叶子结点部分的关键字最大，根结点的关键字部分最小，此时就不是哈夫曼树。
12．用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（ ）
【答案】×
【解析】后序遍历、中序遍历也可以遍历一维数组存储的二叉树。
13．树形结构中元素之间存在一对多的关系。（ ）
【答案】√
【解析】树形结构是非线性结构，存在一对多的关系。
14．取线性表的第i 个元素的时间同i 的大小有关。（ ）
【答案】
【解析】不一定，如果是顺序存储结构，它访问数据元素时的时间效率都是0（1）。
15．在二叉排序树中插入一个新结点，总是插入到叶结点下面。（ ）
【答案】×
【解析】不一定。插入二叉排序树的原则：将新节点元素值与根结点元素值相比较，如小于 根结点元素值则插入到左子树口，否则插入到右子树中。所以就可能插在一个度为1的结点下面。
16．若一个有向图无环，则它一定有唯一的拓扑序列。（ ）
【答案】×
【解析】有向图无环说明它一定有拓扑序列，但这个拓扑序列不唯一。如果在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，在做拓扑排序时，则排序的结果是唯一的，即它有唯一的拓扑序列。
17．在待排数据基本有序的情况下，快速排序效果最好。（ ）
【答案】×
【解析】在待排数据基本有序的情况下，插入排序效果最好。
18．一般来说，若深度为k 的n 个结点的二叉树只有最小路径长度，那么从根结点到第的最多结点数为
【答案】√
【解析】求最小路径长度，即构成哈夫曼树，当哈夫曼树为 层具有最大的结点数为
19．在任何情况下，归并排序都比简单插入排序快。（ ）
【答案】×
【解析】错误。待排序序列为正序时，简单插入排序比归并排序快。
20．对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。（ ）
【答案】√
，【解析】形状不同的两个二叉排序树（关键字集合相同）在中序遍历下是输出排好序的序列，所以顺序是一致的。
层全满时，
此时从根结点到第
余下的
个结点在第k 层的任一位置上。（ ）
层具有
三、算法设计题
21．结点类型和存储结构如下：
相关内容
相关标签