2018年北京市培养单位计算机网络信息中心863计算机学科综合(专业)之数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
2． 外排序的基本操作过程是_____和_____。
【答案】生成有序归并段(顺串) ；归并
3． 完善算法:求KMP 算法.next 数组。
k :＝_____；next[1]:＝0；
k :＝_____；
END ；
【答案】0；next[k]
4． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
5． 栈是_____的线性表，其运算遵循_____的原则。
【答案】操作受限(或限定仅在表尾进行插入和删除操作) ；后进先出
6． 空格串是指_____，其长度等于_____。
【答案】由空格字符(ASCII值32) 所组成的字符串；空格个数
7． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。 【答案】
的次数最小。总次数为
。
第 2 页，共 61 页 【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测
8． 建立索引文件的目的是_____。
【答案】提高查找速度
9． 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。 【答案】
序查找效率一样为
10．已知二维数组
【答案】1196
【解析】设元素的行标为i ，列标为j 。则它的存储位置为:l000＋[(i﹣l)*l0＋(j﹣0)]*4
。 中每个元素占4个单元，在按行优先方式将其存储到起始地址【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺为1000的连续存储区域时，A[5，9]的地址是: _____。
二、判断题
11．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（ ）
【答案】×
【解析】例如起泡排序是稳定排序，将4， 3， 2，1按起泡排序排成升序序列，第一趟变成3， 2，1，4，此 时3就朝向最终位置的相反方向移动。
12．有n 个数顺序(依次) 入栈，出栈序列有Cn 种，
【答案】 √
13．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ）
【答案】√
【解析】由最小生成树的构建过程知，在确定根结点之后，因为连通图上各边权值均不相同，下一个结点的选择是唯一的，所以该图的最小生成树是唯一的。
14．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（ ）
【答案】 ×
【解析】对于链式存储，数据元素之间的存储地址不一定是相邻的，即结点的存储空间可以是不连续的。而结点内部的存储空间需要是连续的，因为它是一个完整的数据。
15．—个有向图的邻接表和逆邻接表中的结点个数一定相等。（ ）
【答案】√
【解析】图的邻接表表示法类似于树的孩子链表示法。对于图G 中的每个顶点，该方法把
第 3 页，共 61 页 （ ）
所以邻接于顶点
的链接成一个带头。在有向图中，为图中每个顶点建立一个入边表的方法称为逆邻接表示法。
16．就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（ ）
【答案】×
【解析】折半查找最小，分块查找次之，顺序查找最大。分块查找的速度虽然不如折半查找算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序。当结点很多且块数很大时，对索引表可以采用折半查找，这样能够进一步提高查找的速度。
17．即使有向无环图的拓扑序列唯一，也不能唯一确定该图。（ ）
【答案】×
【解析】如果有向无环图的拓扑序列唯一，则能够确定每个结点的唯一前驱和后继，因此能够确定该图。
18．在待排数据基本有序的情况下，快速排序效果好。（ ）
【答案】×
【解析】在待排数据基本有序的情况下，插入排序效果好。
19．对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（ ）
【答案】×
【解析】索引顺序存取方法插入操作比较麻烦，对于处理大量数据，会有大量的记录进入溢出区，而基本区中又浪费很多空间。
20．—个排序算法是否稳定，是指该算法在各种情况下的时间效率是否相差不大。（ ）
【答案】×
【解析】排序的稳定性指:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序， 这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri 在rj 之前，而在排序后的序列中，ri 仍在ij 之前，则 称这种排序算法是稳定的；否则称为不稳定的。
三、算法设计题
21．已知关键字序列(
试写出一算法将(
利用(1)的算法写一个建大根堆的算法。
【答案】(1)算法如下:
''
假设 是大堆，本算法把
调成大堆
) 是大根堆。 ) 调整为大根堆；
第 4 页，共 61 页
相关内容
相关标签