2017年大连海事大学交通运输管理学院813管理信息系统与数据结构考研强化模拟题
● 摘要
一、填空题
1． 在循环队列中，队列长度为n ，存储位置从0到，
【答案】 编号，以rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是（ ）。
2． 己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_____次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。
【答案】2；4；3
【解析】二分法查找元素次数列表
查
找100是找到115就停止了。
3． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。
【答案】
【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉 树。故结点个数为
4． 循环队列的引入，目的是为了克服_____。
【答案】假溢出时大量移动数据元素
【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。
5． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k=_____。（注：矩阵元素下标从1开始）
【答案】93
【解析】对于上三角矩阵，将代入得93。
6． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。
【答案】集合；线性结构；树形结构；图状结构（网状结构）
在B
7． 求最短路径的Dijkstra 算法的时间复杂度为_____。 【答案】
8． 如果按关键码值递増的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。 【答案】
【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺 序查找效率一样为
9． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。 【答案】
要加“虚结点”。
设编号为
和
的结点在顺序存储中的下标为
和
。
10．中缀式
运算结果为_____。 【答案】
【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。
对应的前缀式为_____，若则后缀式的，
则结点
和
在同一层上的条件是 【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
二、判断题
11．如果数据元素保持有序，则查找时就可以采用折半查找方法。（ ）
【答案】×
【解析】采用折半查找的条件是数据元素有序且存储方式为顺序存储，对于常见的链式存储，在进行查找时主要依靠指针来操作。
12．不同的求最小生成树的方法最后得到的生成树是相同的。（ ）
【答案】×
，生成树不同，每棵树的权也可能不同。若生【解析】对于一个带权连通无向图G=（V ，E ）
成树T 上的所有边的权值之和最小，则T 称为G 的最小生成树。因此可以看出，最小生成树不是唯一的，最小生成树的权值之和总是唯一的。
13．直接访问文件也能顺序访问，只是一般效率不高。（ ）
【答案】×
【解析】直接访问文件不能进行顺序访问，只能按关键字随机存取。在ISAM 文件上检索记录时，先从主索引出发找到相应的柱面索引，再从柱面索引找到记录所在柱面的磁道索引，最后
从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直至找到为止。
14．就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（ ）
【答案】×
【解析】折半查找最小，分块查找次之，顺序查找最大。分块查找的速度虽然不如折半查找算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序。当结点很多且块数很大时，对索引表可以采用折半查找，这样能够进一步提高查找的速度。
15．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ ）
【答案】√
，使其n 个元素的最大（小）【解析】堆排序：基本思想先将原始序列构造成一个堆（初始堆）
值处于序列的第一个位置；然后交换序列第一个元素与最后一个元素的位置。
16．对于有n 个结点的二叉树，其高度为（ ）
【答案】×
【解析】例如n 结点的单枝树，高度就为n 。
17．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（ ）
【答案】√
【解析】从哈希表删除一个记录，不是将这个记录的位置置空，而是设置一个标记，标记这个元素是无效的了。
18．负载因子（装填因子）是哈希表的一个重要参数，它反映哈希表的装满程度。（ ）
【答案】√
【解析】查找过程中需和给定值进行比较的关键字的个数取决于三个因素：哈希函数，处理冲突的方法和哈希表的装填因子。其中装填因子标志哈希表的装满程度。
19．若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。 （ ）
【答案】√
【解析】因为一个有向图的邻接矩阵对角线以下元素均为零，则该图是一个有向无环图，所以该图的拓扑有序序列必定存在。
20．外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。（ ）
【答案】×
【解析】外部排序方法：按可用内存大小，将外存上含n 个记录的文件分成若干长度为z 的