2018年浙江师范大学数理与信息工程学院885数据结构与程序设计之数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）。
A. 选择排序法 B. 插入排序法 C. 快速排序法 D. 堆排序法 【答案】A
【解析】选择排序的基本思想是:
第i 趟排序开始时，当前有序区和无序区分别为则是从当前无序区中选出关键字最小的记录和
分别变为新的有序区和新的无序区。
和
，该趟排序
，将它与无序区的第1个记录R[i]交换，使
2． 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（ ）。
A.4 B.5 C.6 D.7
【答案】C
【解析】若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。具有n 个(n＞0) 结点的完全二叉树的高度为
或
由完全二叉树类推到完全三叉树可知，n 个结点的完
全三叉树的高度为
或》
3． 下列关于无向连通图特性的叙述中，正确的是（ ）.
(1)所有的顶点的度之和为偶数 (2)边数大于顶点个数减1 (3)至少有一个顶点的度为1 A. 只有(1) B. 只有(2) C. (1)和(2) D.(1)和(3)
【解析】在图中，
顶点的度
之和与边的数目满足关系式：
(n为图的
总结点数，e 为总边数) ，因此， (1)项正确. 对于(2)、(3)项中的特性不是一般无向连通图的特性，可以轻松地举出反例.“至少有一个顶点的度为1”的反例如下图1所示，“边数大于顶点个数减1”的反例如下图2所示
.
图
1
图2
4． 下列四个序列中，哪一个是堆（ ）?
A.75，65，30，15，25，45，20，10 B.75，65，45，10，30，25，20，15 C.75，45，65，30，15，25，20，10 D.75，45，65，10，25，30，20，15
【答案】C 【解析】堆的定义: n 个关键字序列①②
且且
称为堆，当且仅当该序列满足如下性质(简称为堆性质) :
小根堆:满足第①种情况的堆； 大根堆:满足第②种情况的堆。
根据堆定义即可得出答案。
5． 设有一棵3阶B 树, 如下图所示。删除关键字78得到一棵新B 树, 其最右叶结点所含的关键字是（ ）。
图 3二叉树图
A.60 B.60, 62 C.62, 65 D.65
【解析】本题主要考查B 树删除操作。即被删关键字所在的结点中的关键字个数等于而与该结点相邻的右兄弟(或左兄弟) 结点中的关键字数目大于
(或最大) 的关键字上移至双亲结点中, 而将双亲结点中小于(或大于) 且紧靠该上移关键字的关键字下移至被删关键字所在结点中。题目中删除关键字78得到一棵新B 树如下, 其最右叶结点所含的关键字是65。
,
, 则需将其兄弟结点中最小
6． 设文件索引节点中有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.
7． 用户程序发出磁盘请求后, 系统的处理系统的处理流程是:用户程序一系统调用处理程序—设备骆动程序一中断处理程序。其中, 计算数据所在磁盘的柱面号、磁头号、扇区号的程序是（ ）
A. 用户程序 B. 系统调用处理程序 C. 设备驱动程序 D. 中断处理程序 【答案】C
【解析】计算磁盘号、磁头号和扇区号的工作是由设备驱动程序完成的, 所以答案选C 。
8． 向一个栈顶指针为h 的带头结点的链栈中插入指针S 所指的结点时，应执行（ ）。
A.h ﹣＞next ＝s ； B.s ﹣＞next ＝h ；