2017年中国石油大学(北京)地球物理与信息工程学院858计算机科学基础之数据结构考研强化模拟题
● 摘要
一、填空题
1． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。
【答案】出度为0
【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最 后一个顶点的出度必定为零。
2． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度_____; 深度优先遍历图的时间复杂度_____, 两者不同之处在于_____, 反映在数据结构上的差别是_____。
【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈
【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。
3． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
4． 设有一个10阶对称矩阵A 采用压缩存储方式，（以行为主序存储：）则
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若则的地址为
5． 已知二维数组
【答案】1196
【解析】设元素的行标为i ，列标为j 。则它的存储位置为：
6． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。 【答案】
【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。
7． —个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
第 2 页，共 40 页 的地址为_____。若
则的地址为将代入得33。 中每个元素占4个单元，在按行优先方式将其存储到起始地址的地址是：_____。 为1000的连续存储区域时
，
8． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。
【答案】2
【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。
9． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4; 2
10．抽象数据类型的定义仅取决于它的一组_____，而与_____无关, 即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性
二、判断题
11．二叉树中除叶结点外，任一结点点的值大于等于该结点
【答案】×
【解析】二叉排序树按中序遍历的结点序列是从小到大的因为某结点的左子树根结点不一定是它的中序前驱，可能会出现某结点的左子树根结点的右子树上的值大于这个结点；其右子树根结点也不一定是它的中序后继。可能会出现右子树根结点的左子树的值小于这个结点。
12．在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。（ ）
【答案】×
【解析】伙伴系统的伙伴不一定是位置相邻的内存块。
起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：
只要符合公式的内存块都是伙伴。
13．在平衡二又树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。（ ）
【答案】×
【解析】不一定，比如一个平衡因子为1的结点，这时往它的右部插入一个新结点，就不会引起平衡旋转
14．由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间更多。（ ）
【答案】×
【解析】希尔排序把序列分成很多小序列，对于直接插入排序，记录少时的效率会大大提高。
第 3 页，共 40 页 其左子树根结点的值小于该结点的值；其右子树根结的值，则此二叉树一定是二叉排序树。（ ）
并且序列在基本有序的情况下，直接插入排序也会提高。
15．对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（ ）
【答案】√
【解析】可以有长度无穷大的广义表，只是在计算机中不能实现。
16．2，... ，n , 输出序列是栈的输入序列是1，若则有：
【答案】
【解析】出栈序列不一定满足比如1进栈，然后出栈，
17．m 阶B 树的任何一个结点的左右子树的高度都相等。（ ）
【答案】√
【解析】由B 树的性质得知，叶子结点都处于同一层。因此，m 阶B 树的任何一个结点的左右子树的高度都相等。
18．基数分类只适用于以数字为关键字的情况，不适用于以字符串为关键字的情况。（ ）
【答案】×
【解析】如果用字符串为关键字，可以将其中的字符串的每一位用Ascn 码进行比较。
19．—棵树中的叶子数一定等于与其对应的二叉树的叶子数。（ ）
【答案】×
【解析】一颗树的叶子树与它对一个的二叉树的叶子树没有直接联系。不妨举例：假设一个有三个结点的二叉树，层数为2。则它的叶结点数为2。将其按规则转为对应的二叉树时，则它的叶结点数为1。
20．对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（ ）
【答案】×
【解析】索引顺序存取方法插入操作比较麻烦，对于处理大量数据，会有大量的记录进入溢出区，而基本区中又浪费很多空间。
21．用希尔（Shell ）方法排序时，若关键字的初始排序杂乱无序，则排序效率就低。（ ）
【答案】×
【解析】希尔排序的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
22．设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度均为（ ）。 【答案】
【解析】入队和出队操作分别在队尾和队头进行，设有尾指针的循环链表对头和尾元素的操
第 4 页，共 40 页 （ ）
相关内容
相关标签