2018年大连海事大学交通运输管理学院813管理信息系统与数据结构之数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
2． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。 【答案】
【解析】无向完全图中任意一个顶点都和其他n －1个顶点都有一条边，即为n(n－1) 。又因
. 。 为每条边重复出现两次，所有无向完全图的边数为
3． 一个算法具有5个特性: _____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
4． 在单链表中设置头结点的作用是_____。
【答案】方便运算
5． VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
6． 栈是_____的线性表，其运算遵循_____的原则。
【答案】操作受限(或限定仅在表尾进行插入和删除操作) ；后进先出
7． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有 检索和_____检索。
【答案】关键字；记录号；记录号；顺序；直接
8． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度, 当它为一棵_____时，具有最大高度。
【答案】完全；只有一个叶结点的二叉树
9． 一个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
10． 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:a 11＝l) ，则a 85的地址为_____。
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若i ＞＝j ，则
＝i(i﹣l)/2＋j 。若i ＜j 。则
的地址为l ＋2＋... ＋i ﹣l ＋j 的地址为j(j﹣l)/2＋i 。将i ＝8，j ＝5代入得33。
二、判断题
11．在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。（ ）
【答案】√
【解析】最佳适配法:将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给用户；最先适配法:从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户；从适配法选择上可以看出最佳适配法会增加闲置空间。
12．—个排序算法是否稳定，是指该算法在各种情况下的时间效率是否相差不大。（ ）
【答案】×
【解析】排序的稳定性指:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序， 这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri 在rj 之前，而在排序后的序列中，ri 仍在ij 之前，则 称这种排序算法是稳定的；否则称为不稳定的。
13．从逻辑结构上看，n 维数组的每个元素均属于n 个向量。（ ）
【答案】 √
【解析】对于每一维，都有一个向量共用这个元素，比如我们最常见的二维数组，对于每个元素，在行和列都有一个向量共用这个元素。
14．哈夫曼树度为1的结点数等于度为2和0的结点数之差。（ ）
【答案】×
【解析】哈夫曼树不存在度数为1的结点。度数为2和0的结点数之差为1。
15．对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（ ）
【答案】×
【解析】索引顺序存取方法插入操作比较麻烦，对于处理大量数据，会有大量的记录进入溢出区，而基本区中又浪费很多空间。
16．在初始数据表已经有序时，快速排序算法的时间复杂度为
【答案】×
【解析】当初始数据表有序，此时快速排序所需要比较的次数最多，快速排序算法的时间复
。（ ）
杂度为。
17．一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（ ）
【答案】 √
【解析】树的前序遍历和后序遍历叶子节点的相对次序是不变的，都遵循左右的次序。
18．数据元素是数据的最小单位。（ ）
【答案】 ×
【解析】数据项是数据的不可分割的最小单位，而数据元素是数据的基本单位。
19．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（ ）
【答案】 √
【解析】算法的健壮性是指当输入数据非法时，算法能作适当的处理并作出反应，而不应死机或输出异常结果。
20． 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（ ）
【答案】 ×
【解析】队列是一种先入先出型结构，而找才是先进后出的线性结构。
三、算法设计题
21．请编写完整的程序。如果矩阵A 中存在这样的一个元素A[i，j]满足条件:A[i，j]是第i 行中值最小的元素，且又是第j 列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A 的所有马鞍点。
【答案】算法如下:
//A是的矩阵，本算法求矩阵A 中的马鞍点
//max数组存放各列最大值元素的行号，初始化为行号
//min数组存放各行最小值元素的列号，初始化为列号
//选各行最小值元素和各列最大值元素
//修改第j 列最大元素的
行号
" 修改第i 行最小元素的
列号
//第i 行最小元素的列号
相关内容
相关标签