2018年北京市培养单位软件研究所863计算机学科综合(专业)之数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。 【答案】
【解析】无向完全图中任意一个顶点都和其他n －1个顶点都有一条边，即为n(n－1) 。又因
. 。 为每条边重复出现两次，所有无向完全图的边数为
2． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。
【答案】起泡；快速
【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为O(n)，
2而快速排序算 法需要比较的次数达到最大，时间复杂度为O (n) 。
3． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
h 为附加头结点指针
(_____)
_____；
【答案】(1)p!＝NULL //链表未到尾就一直进行
(2)q //将当前结点作为头结点后的第一元素结点插入
4． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
5． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
6． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。
【答案】f ﹣＞next ＝p ﹣＞next ；f ﹣＞prior ＝p ；p ﹣＞next ﹣＞prior ＝f ；p ﹣＞next ＝f ；
7． 已知一循环队列的存储空间为
则此循环队列判满的条件是_____ 【答案】
8． 数据结构中评价算法的两个重要指标是_____。
【答案】算法的时间复杂度和空间复杂度
9． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。
【答案】集合；线性结构；树形结构；图状结构(网状结构)
10．如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。 ，其中n ＞m ，队头和队尾指针分别为front 和rear ，
二、判断题
11．取线性表的第i 个元素的时间同i 的大小有关。（ ）
【答案】 ×
【解析】不一定，如果是顺序存储结构，它访问数据元素时的时间效率都是O(1)。
12．3阶的B-树是平衡的3路搜索树。反之，一棵平衡的3路搜索树是3阶B-树。（ ）
【答案】×
【解析】3路搜索树并不具有3阶B-树的性质。因此一棵平衡的3路搜索树不一定是3阶B-树。
13．二叉树中除叶结点外，任一结点X ，其左子树根结点的值小于该结点(X)的值；其右子树根结点的值大于等于该结点(X)的值，则此二叉树一定是二叉排序树。（ ）
【答案】×
【解析】二叉排序树按中序遍历的结点序列是从小到大的因为某结点的左子树根结点不一定是它的中序前驱，可能会出现某结点的左子树根结点的右子树上的值大于这个结点; 其右子树根结点也不一定是它的中序后继。可能会出现右子树根结点的左子树的值小于这个结点。
14．就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（ ）
【答案】×
【解析】折半查找最小，分块查找次之，顺序查找最大。分块查找的速度虽然不如折半查找算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序。当结点很多且块数很大时，对索引表可以采用折半查找，这样能够进一步提高查找的速度。
15．一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（ ）
【答案】 ×
【解析】一颗树的叶子树与它对一个的二叉树的叶子树没有直接联系。不妨举例:假设一个有三个结点的二叉树，层数为2。则它的叶结点数为2。将其按规则转为对应的二叉树时，则它的叶结点数为1。
16．循环队列也存在空间溢出问题。（ ）
【答案】 √
【解析】循环队列的存储空间也是有限的，因此也存在空间溢出问题。
17．在待排数据基本有序的情况下，快速排序效果好。（ ）
【答案】×
【解析】在待排数据基本有序的情况下，插入排序效果好。
18．一个广义表可以为其他广义表所共享。（ ）
【答案】 √
【解析】因为广义表中的元素还可能是表，所以对于一个广义表可以为其他广义表所共享。
19．平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。（ ）
【答案】×
【解析】平衡因子定义为该结点的左子树的深度减去右子树的深度，一个平衡二叉树中，某节点的左右孩子的平衡因子为0，说明左孩子的左子树和右子数的深度相同，而且右子树的左子树和右子数的深度相同，但这不能说明该节点的左子树和右子树的深度相同。
20．串是一种数据对象和操作都特殊的线性表。（ ）
【答案】 √
【解析】串是一种操作特殊的线性表，其特殊性主要体现在数据元素是一个字符。在内存中，一份文本都可以看做是一个字符串，而每一行都可以看做是其子串。
三、算法设计题