2018年中国石油大学(北京)地球物理与信息工程学院858计算机科学基础之数据结构考研强化五套模拟题
● 摘要
一、填空题
1． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。
【答案】顺序
【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。
2． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。 【答案】
要加“虚结点”。
设编号为i 和j 的结点在顺序存储中的下标为s 和t , 则结点i 和j 在同一层上的条件是
。
3． 顺序栈用存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。 【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
【答案】if(top!＝n)data[++top]＝x ；
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
4． 设广义表L ＝(（ ），（ ）) ，则head(L)是_____tail(L)是_____L的长度是_____；深度是_____。
【答案】（ ）；(（ ）) ；2；2
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
5． 组成串的数据元素只能是_____。
【答案】字符
6． 设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f(m，n) 为这种表示方式的数目。例f(5，3) ＝5, 有5种表示方式:3＋2, 3＋1＋1，2＋2＋1，2＋1＋1＋1，1＋1＋1＋1＋1。
①以下是该函数的程序段，请将未完成的部分填入，使之完整。
_____
_____；
}
_____；
}
，
_____)
②执行程序，f(6，4) ＝_____。
【答案】①1; 1; f(m, n ﹣1) ; n ②9
7． 表达式23＋((12*3﹣2)/4＋34，5/7) ＋108/9的后缀表达式是_____。 【答案】
8． 对n 个记录的表
【答案】n (n－1) /2
【解析】第一次需要n －1次比较，第i 此需要n －i 此比较，所以共需要。
9． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
10．设有两个算法在同一机器上运行，其执行时闻分别为100n 2和2n ，要使前者快于后者，n 至少为_____。
【答案】15
【解析】当
时，100n2>2n，而，2n 时，100n ＜2 (表达式中的点(.)是数分隔符，如是三个数) 进行简单选择排序，所需进行的关键字间的比较次数为_____。
二、判断题
11．十字链表是无向图的一种存储结构。（ ）
【答案】×
【解析】十字链表是有向图的另一种链式存储结构。在十字链表中，对应于有向图的每条弧有一个结点，对应于每个顶点也有一个结点。类似于邻接表是无向图的一种链式存储结构。
12．对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（ ）
【答案】×
【解析】索引顺序存取方法插入操作比较麻烦，对于处理大量数据，会有大量的记录进入溢
出区，而基本区中又浪费很多空间。
13．基数分类只适用于以数字为关键字的情况，不适用于以字符串为关键字的情况。（ ）
【答案】×
【解析】如果用字符串为关键字，可以将其中的字符串的每一位用Ascn 码进行比较。
14．二元查找树的任何结点的左右子树都是二元查找树。（ ）
【答案】√
【解析】二元查找树也称作二元排序树。二元查找树的性质:①若左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若右子树不空，则右子树所有结点的值均大于它的根结点的值；③左右子树也分别为二元查找树。
15．有n 个数顺序(依次) 入栈，出栈序列有Cn 种，
【答案】 √
16．AOE 网一定是有向无环图。（ ）
【答案】×
【解析】在带权的有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销，则称这种有向图表示活动的网络，简称为AOE 网。因此对AOE 网是否是有向无环图没有要求。
17．二叉树中序线索化后，不存在空指针域。（ ）
【答案】×
【解析】非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。
18．3阶的B-树是平衡的3路搜索树。反之，一棵平衡的3路搜索树是3阶B-树。（ ）
【答案】×
【解析】3路搜索树并不具有3阶B-树的性质。因此一棵平衡的3路搜索树不一定是3阶B-树。
19．不同的求最小生成树的方法最后得到的生成树是相同的。（ ）
【答案】×
【解析】对于一个带权连通无向图G=(V，E) , 生成树不同，每棵树的权也可能不同。若生成树T 上的所有边的权值之和最小，则T 称为G 的最小生成树。因此可以看出，最小生成树不是唯一的，最小生成树的权值之和总是唯一的。
（ ）
相关内容
相关标签