2018年新疆农业大学计算机与信息工程学院856数据结构及操作系统之数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 直接插入排序在最好情况下的时间复杂度为（ ）。 A.
B.O(n) C. 2D.O(n)
【答案】B
【解析】当序列是按照直接插入排序的顺序有序时，此时进行插入时，每次都只需要和末尾的一个元素进行比较，此时的时间复杂度最好，为O(n)。
2． 设文件索引节点中有7个地址项，其中4个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节，若磁盘索引块和磁盘数据块的大小均为256字节，则可表示的单个文件最大长度是（ ）.
A.33KB
B.519KB
C.1057KB
D.16513KB
【答案】C
【解析】4个地址项为直接地址索引，其指向的数据块大小4×256B ＝lKB ，一级间接地址索引可以索引256/4＝64个直接地址索引，故2个一级间接地址索引指向的数据块大小为2×64×256B ＝32KB ，二级间接地址索引为256/4×256/4＝4096个直接地址索引，故1个二级间接地址索引指向的数据块大小为4096×256B ＝1024KB ，共计1KB ＋32KB ＋1024KB ＝1057KB.
3． 一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（ ）。
A. 其中任意一个结点均无左孩子
B. 其中任意一个结点均无右孩子
C. 其中只有一个叶结点
D. 其中度为2的结点最多为一个
【答案】C
【解析】前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树才有可能，所以本题的A 项和B 项均对，单支树的特点是只有一个叶结点，故C 项是最合适的。A 项或B 项都不全。
4． 图G 是n 个顶点的无向完全图，则下列说法不正确的是（ ）
A.G 的邻接多重表需要n(n－1) 个边结点和n 个顶点结点
B.G 的连通分量个数最少
C.G 为连通图
D.G 所有顶点的度的总和为n(n—1)
【答案】A
A 项中G 的邻接多重表中需要【解析】
n 个结点的度的总和为n(n－1) 。
5． 在下列表述中，正确的是（ ）
A. 含有一个或多个空格字符的串称为空格串
B. 对n(n＞0) 个顶点的网，求出权最小的n ﹣1条边便可构成其最小生成树
C. 选择排序算法是不稳定的
D. 平衡二叉树的左右子树的结点数之差的绝对值不超过1
【答案】C
【解析】平衡二叉树的左右子树的深度之差的绝对值不超过1。求最小生成树时，每次挑最小权值边，是要求该边的两点都在不同的连通分量上的。
6． float 类型(即IEEE754单精度浮点数格式) 能表示的最大正整数是（ ）。 A. B. C. D.
【答案】D 。
【解析】IEEE754单精度浮点数尾数采用隐藏位策略的原码表示, 且阶码用移码表示的浮点数。规格化的短浮点数的真值为:
故float 类型能表示的最大整数是
。
7． 若磁盘转速为7200转/分, 平均寻道时间为8ms , 每个磁道包含1000个扇区, 则访问一个扇区的平均存取时间大约是（ ）。 A. B. C. D.
【答案】B
【解析】磁盘的平均寻址时间包括平均寻道时间和平均等待时间。平均寻道时间为8ms , 平均
个边结点和n 个顶点结点。此时连通分量最少为1。无向完全图中任意两个顶点之间都存在路径，则G 必为连通图。每个顶点的度为n －1，则, S 为符号位, E 的取值为, f 为23位;
等待时间与磁盘转速有关, 为
。
磁盘的存取一个扇区的时间为
因此总的时间为:
。
8． 对于下列关键字序列, 不可能构成某二叉排序树中一条查找路径的序列是（ ）。
A.95, 22, 91, 24, 94, 71
B.92, 20, 91, 34, 88, 35
C.21, 89, 77, 29, 36, 38
D.12, 25, 71, 68, 33, 34
【答案】A
【解析】各选项对应的查找过程如下图所示, 从中看到选项B 、C 、D 对应的查找树都是二叉排序树, 只有选项A 对应的查找树不是一棵二叉排序树, 因为在以91为根的左子树中出现了比91大的结点94。
9． 设二维数组
A.(i﹣1)*n＋j
B.(i﹣1)*n＋j ﹣l
C.i*(j﹣1)
D.j*m＋i ﹣l
【答案】A
【解析】前i ﹣1的元素个数为(i﹣1)*n，所以二维数组元素A[i，j]在一维数组B 中的下标为(i﹣1)*n＋j 。需要注意数组B 的下标是从0开始，还是从1开始。
10．对n 个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（ ）。
A. 每次分区后，先处理较短的部分
(即m 行n 列) 按行存储在数组中，则二维数组元素A[i，j]在一维数组B 中的下标为（ ）。