2018年江西中医药大学计算机学院806数据结构考研强化五套模拟题
● 摘要
一、填空题
1． 有五个数据依次入找:1，2，3，4，5。在各种出栈的序列中，以3，4先出栈的序列有_____。(3在4之前出栈)
【答案】3个
【解析】以3，4先出栈的序列有34521、34215、34251共3个。
2． 在一个具有n 个单元的顺序栈中，假定以地址高端(即下标为n 的单元) 作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top ＝_____。
【答案】top ﹣1
【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，所以top ﹣1。
3． 中缀式
运算结果为_____。 【答案】
【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。
4． 已知如下程序段:
语句1执行的时间复杂度为_____:语句2执行的时间复杂度为_____:语句3执行的时间复杂度为_____:语句4执行的时间复杂度为_____。
【答案】(1)n＋1
(2)n
(3)n(n＋3)/2
(4)n(n＋l)/2
【解析】语s 句1执行到不符合条件情况下，执行了n ＋1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为2＋3＋4...... ＋(n＋l) 加起来就是n(n＋3)/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了1
第 2 页，共 42 页 (c-d)对应的前缀式为_____，若a=l，b=2, c=3, d=4, 则后缀式的
＋2＋3...... ＋n 即n(n＋l)/2。
5． 一棵有11个结点的满二叉树有_____个度为1的结点、有_____个分支(非终端) 结点和_____个叶子，该满二叉树的深度为_____。 【答案】或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
6． 建立索引文件的目的是_____。
【答案】提高查找速度
7． 高度为h 的堆中，最多有_____元素，最少有_____个元素。 【答案】
。当最后一层只有【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为
一个元素时，此时堆的元素个数最少，元素个数为。
8． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
9． 设二维数组A 的行和列的下标范围分别为[0:8]和[0:10]，每个元素占2个单元，按行优先顺序存储，第一个元素的存储起始位置为b ，则存储位置为b+50处的元素为_____。
【答案】A[2][3]
【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是(ll*i＋j ＋l ﹣l)*2＋b 。当其值为b ＋50时，则i ＝2，j ＝3。
10．假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。 【答案】
的次数最小。总次数为
。 【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测二、判断题
11．数据元素是数据的最小单位。（ ）
【答案】 ×
【解析】数据项是数据的不可分割的最小单位，而数据元素是数据的基本单位。
第 3 页，共 42 页
12．一般来说，若深度为k 的n 个结点的二叉树只有最小路径长度，那么从根结点到第k ﹣1层具有的最多结点数为余下的
【答案】 √
【解析】求最小路径长度，即构成哈夫曼树，当哈夫曼树为k ﹣1层全满时，此时从根结点到第k ﹣1层具有最大的结点数为
13．在任何情况下，归并排序都比简单插入排序快。（ ）
【答案】×
【解析】错误。待排序序列为正序时，简单插入排序比归并排序快。
14．拓扑排序的有向图中，最多存在一条环路。（ ）
【答案】×
【解析】要进行拓扑排序，需要满足一个条件为:若顶点A 在序列中排在顶点B 的前面，则在图中不存在顶点B 到顶点A 的路径。如果是一个有环图，则不能满足这个条件，所以拓扑排序的有向图中不能存在环路。
15．队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（ ）
【答案】 ×
【解析】栈只能在一端进行操作，队列可以在表的两端进行运算。
16．即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。（ ）
【答案】 ×
【解析】栈只是一种先入后出的存储结构。对于出栈、入栈的元素不进行修改，因此，输入序列的元素不相同，不可能得到相同的输出序列。
17．设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i 个元素入栈时，入栈算法的时间复杂性为O(i)。（ ）
【答案】 ×
【解析】由于该栈采用顺序存储结构，时间复杂度应该为O(1)。
18．循环队列也存在空间溢出问题。（ ）
【答案】 √
【解析】循环队列的存储空间也是有限的，因此也存在空间溢出问题。
19．最小生成树的Krusakl 算法是一种贪心法。（ ）
【答案】√
第 4 页，共 42 页 个结点在第k 层的任一位置上。（ ）
相关内容
相关标签