2018年大连海事大学信息科学技术学院908数据结构[专业硕士]考研基础五套测试题
● 摘要
目录
2018年大连海事大学信息科学技术学院908数据结构[专业硕士]考研基础五套测试题（一） . 2 2018年大连海事大学信息科学技术学院908数据结构[专业硕士]考研基础五套测试题（二）11 2018年大连海事大学信息科学技术学院908数据结构[专业硕士]考研基础五套测试题（三）20 2018年大连海事大学信息科学技术学院908数据结构[专业硕士]考研基础五套测试题（四）29 2018年大连海事大学信息科学技术学院908数据结构[专业硕士]考研基础五套测试题（五）37
一、填空题
1． 每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH ，中序序列是FEBGCHD ，则它的后序序列是_____。设上述二叉树是由某棵树转换而成，则该树的前序序列是_____
【答案】FEGHDCB ；BEF
【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEF 。
2． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
3． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
4． 已知链队列的头尾指针分别是f 和r ，则将值x 入队的操作序列是_____。
【答案】S ＝(LinkedList*)malloc(sizeof (LNode))；s ﹣＞data ＝x ；s ﹣＞next ＝r ﹣＞next ；r ﹣＞next ＝s ；r ＝s ；
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
5． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。
【答案】出度为0
【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最后一个顶点的出度必定为零。
6． 阅读下列程序，指出其功能，并写出空格处应填上的语句。
【答案】
【解析】本题是在哈希表中插入值为item 的元素，如该元素已在哈希表中，报告出错。
7． 对n 个记录的表进行简单选择排序，所需进行的关键字间的比较次数为_____。
【答案】n (n－1) /2
【解析】第一次需要n －1次比较，第i 此需要n －i 此比较，所以共需要
8． 循环队列的引入，目的是为了克服_____。
【答案】假溢出时大量移动数据元素
【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。
9． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有
10．在哈希函数检索和_____检索。 【答案】关键字；记录号；记录号；顺序；直接 中，p 值最好取_____。 。
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
二、判断题
11．用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（ ）
【答案】 ×
【解析】后序遍历、中序遍历也可以遍历一维数组存储的二叉树。
12．如果数据元素保持有序，则查找时就可以采用折半查找方法。（ ）
【答案】×
【解析】采用折半查找的条件是数据元素有序且存储方式为顺序存储，对于常见的链式存储，在进行查找时主要依靠指针来操作。
13．不同的求最小生成树的方法最后得到的生成树是相同的。（ ）
【答案】×
【解析】对于一个带权连通无向图G=(V，E) , 生成树不同，每棵树的权也可能不同。若生成树T 上的所有边的权值之和最小，则T 称为G 的最小生成树。因此可以看出，最小生成树不是唯一的，最小生成树的权值之和总是唯一的。
14．两个长度不相同的串有可能相等。（ ）
【答案】 ×
【解析】两个字符串相等，只有当两个字符串的长度相等，并且各个对应位置的字符相等才相等。
15． 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（ ）
【答案】 ×
【解析】队列是一种先入先出型结构，而找才是先进后出的线性结构。
16．堆是满二叉树。（ ）
【答案】×
【解析】堆的定义:
n 个关键字序列
①②且且 称为堆，当且仅当该序列满足如下性质(简称为堆性质) : 小根堆:满足第①种情况的堆；
大根堆:满足第②种情况的堆。
因此并不能保证堆是满二叉树。
17．二叉树中除叶结点外，任一结点X ，其左子树根结点的值小于该结点(X)的值；其右子树根结点的值大于等于该结点(X)的值，则此二叉树一定是二叉排序树。（ ）
【答案】×
【解析】二叉排序树按中序遍历的结点序列是从小到大的因为某结点的左子树根结点不一定是它的中序前驱，可能会出现某结点的左子树根结点的右子树上的值大于这个结点; 其右子树根结点也不一定是它的中序后继。可能会出现右子树根结点的左子树的值小于这个结点。
18．在待排数据基本有序的情况下，快速排序效果好。（ ）
【答案】×
【解析】在待排数据基本有序的情况下，插入排序效果好。