2017年北京市培养单位计算技术研究所863计算机学科综合(专业)之数据结构考研题库
● 摘要
一、填空题
1． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法
，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）
中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。
Prior （node , x ）
{ if（node !=null）
If （ （1） ） *x=node->right；else * x-node->left;
}
next （bt , node, x ）/*bt是二叉树的树根*/
{ （2） ;
if （node->rflag）（3）;
else {do t=*x；;
while （*x==node ）;
*x=t;
}
}
【答案】nodc->rflag==O; *x=ht; *x=nodc->right; prior （t , X ）
2． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
3． 在单链表L 中，指针P 所指结点有后继结点的条件是_____ 【答案】
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
4． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_____和记录的_____，
【答案】比较；移动
5． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度，当它为一棵_____ 时. 具有最大高度
【答案】完全；只有一个叶结点的二叉树
6． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
7． 在哈希函数中，P 值最好取_____。
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
8． G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。
【答案】9
【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。
9． 设单链表的结点结构为为指针域，已知指针px 指向单链表中data 为x 的结
_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：
_____; 【答案】
10．求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e
【答案】克鲁斯卡尔
【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。
二、判断题
11．在待排数据基本有序的情况下，快速排序效果最好。（ ）
【答案】×
【解析】在待排数据基本有序的情况下，插入排序效果最好。
12．外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。（ ）
【答案】×
【解析】外部排序方法：按可用内存大小，将外存上含n 个记录的文件分成若干长度为z 的子文件或段，依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写入外存，通常称这些有序子文件为归并段或顺串（run ）。对这些归并段进行逐趟归
并，使归并段（有序的子文件）逐渐由小至大，直至得到整个有序文件为止。一般情况下，外部排序所需总的时间=内部排序（产生初始归并段）所需的时间
存信息读写的时间内部归并所需的时间
13．倒排文件是对次关键字建立索引。（ ）
【答案】√
，将所有具有相同【解析】倒排文件是对每一个次关键字项建立次关键字索引（称为倒排表）
次关键字的记录的物理记录号都填入倒排表为此次关键字的表中。
14．若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（ ）
【答案】×
【解析】在含有N 个带权叶子结点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也叫做最优二叉树。关键字有序，可能叶子结点部分的关键字最大，根结点的关键字部分最小，此时就不是哈夫曼树。
15．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ） 【答案】
【解析】前者正确，后者错误。顺序存储方式在插入、删除元素时需要挪动大量的元素，执行效率较低。
16．3阶的B-树是平衡的3路搜索树。反之，一棵平衡的3路搜索树是3阶B-树。（ ）
【答案】×
【解析】3路搜索树并不具有3阶B-树的性质。因此一棵平衡的3路搜索树不一定是3阶B-树。
17．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（ ）
【答案】×
【解析】例如起泡排序是稳定排序，将4，3，2，1按起泡排序排成升序序列，第一趟变成3，2，1，4，此时3就朝向最终位置的相反方向移动。
18．用希尔（Shell ）方法排序时，若关键字的初始排序杂乱无序，则排序效率就低。（ ）
【答案】×
【解析】希尔排序的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
外