2018年常州大学艺术学院858数据结构考研强化五套模拟题
● 摘要
一、单项选择题
1． 若某文件系统索引结点(inode)中有直接地址项和间接地址项, 则下列选项中, 与单个文件长度无关的因素是（ ）
A. 索引结点的总数
B. 间接地址索引的级数
C. 地址项的个数
D. 文件块大小
【答案】A
【解析】根据文件长度与索引结构的关系可知, 只有选项A 是与单个文件长度无关的。
2． 为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据. 该缓冲区的逻辑结构应该是（ ）.
A. 找
B. 队列
C. 树
D. 图
【答案】B
【解析】这类问题一般都先分析题目中的数据具有什么操作特性或是结构特性比如“先进后“先进先出”等再判断其逻辑结构. 栈和队列是操作受限的线性表，出”、栈具有先进后出的特性而队列具有先进先出的特性. 由于本题中先进入打印数据缓冲区的文件先被打印，因此打印数据缓冲区具有先进先出性，则它的逻辑结构应该是队列.
3． 某计算机主存容量为64KB ，其中ROM 区为4KB ，其余为RAM 区，按字节编址. 现要用2K ×8位的ROM 芯片和4K ×4位的RAM 芯片来设计该存储器，则需要上述规格的ROM 芯片数和RAM 芯片数分别是（ ）
A.1、15
B.2、15
C.1、30
D.2、30
【答案】D
【解析】主存储器包括RAM 和ROM 两部分，由于ROM 区为4KB ，则RAM 区为60KB. 存储容量的扩展方法有字扩展、位扩展、字和位同时扩展三种. 选用2Kx8位的ROM 芯片，只需采用2片芯片进行字扩展便可得到4KB 的ROM 区；选用4Kx4位的RAM 芯片，需采用(60)/4*2片芯片进行字和位同时扩展便可得60KB 的RAM 区.
4． 在系统内存中设置磁盘缓冲区的主要目的是（ ）。
A. 减少磁盘次数
B. 减少平均寻道时间
C. 提高磁盘数据可靠性
D. 实现设备无关性
【答案】A
【解析】访问磁盘的开销远远大于访问内存的开销。磁盘缓冲区便是利用主存中的存储空间, 来暂存从磁盘中读出(或写入) 的信息, 频繁使用的一部分磁盘数据和信息, 暂时存放在磁盘缓存中, 可减少访问磁盘的次数。
5． 一个非空广义表的表尾（ ）。
A. 不能是子表
B. 只能是子表
C. 只能是原子
D. 是原子或子表
【答案】B
【解析】广义表的定义是一个递归定义，当广义表非空时，称第一个元素是它的表头，称其余元素构成的表称为它的表尾。因此一个非空广义表的表尾只能是子表。
6． 下列因素中, 不会影响信道数据传输速率的是（ ）
A. 信噪比
B. 频率宽带
C. 调制速率
D. 信号传播速度
【答案】D
【解析】信道数据传输速率与信噪比、频率宽度、调制速率都有关。
7． 设有一棵3阶B 树, 如下图所示。删除关键字78得到一棵新B 树, 其最右叶结点所含的关键字是（ ）。
图 3二叉树图
A.60
B.60, 62
C.62, 65
D.65
【答案】D 。
【解析】本题主要考查B 树删除操作。即被删关键字所在的结点中的关键字个数等于
而与该结点相邻的右兄弟(或左兄弟) 结点中的关键字数目大于
(或最大) 的关键字上移至双亲结点中, 而将双亲结点中小于(或大于) 且紧靠该上移关键字的关键字下移至被删关键字所在结点中。题目中删除关键字78得到一棵新B 树如下, 其最右叶结点所含的关键字是65。
, , 则需将其兄弟结点中最小
8． 就平均性能而言，目前最好的内排序方法是（ ）排序法。
A. 起泡
B. 希尔插入
C. 交换
D. 快速
【答案】D
【解析】快速排序的平均时间复杂度是nlogn 所需要的辅助存储为
间复杂度也是
注意仅仅表示的是一个量级，比如和的量级都为，虽然堆排序的时。之所以说，所需要的辅助存储为O(1)，看似堆排序比快速排序的性能好，但是需要快排最好，是在综合考虑的情况下。
9． 若磁盘转速为7200转/分, 平均寻道时间为8ms , 每个磁道包含1000个扇区, 则访问一个扇区的平均存取时间大约是（ ）。 A. B. C.