2017年济南大学信息科学与工程学院847计算机学科专业基础综合之数据结构考研强化模拟题
● 摘要
一、选择题
1． 处理外部中断时，应该由操作系统保存的是（ ）。
A. 程序计数器（PC ）的内容
B. 通用寄存器的内容
C. 快表（TLB ）的内容
D.Cache 中的内容
【答案】B
【解析】外部中断处理过程首先要保护现场，使得中断处理完后能够恢复程序的状态继续执
；②由中断服务程序保行。保护现场有两个含义：①由中断隐指令保存程序的断点（程序计数器）
存通用寄存器和状态寄存器的内容。中断服务程序是操作系统的一部分。
2． 在一棵具有15个关键字的4阶B 树中，含关键字的结点数最多是（ ）
A.5
B.6
C.10
D.15
【答案】D
【解析】m 阶B 树非根结点含关键字个数
4阶B 树非根结点含关键字1〜3个，所以要使关键字结点数量最多，那么每个结点只有一个关键字，一共有15个关键字那么最多有15个含有关键字的结点
3． 冯. 诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU 区分它们的依据是（ ）。
A. 指令操作码的译码结果
B. 指令和数据的寻址方式
C. 指令周期的不同阶段
D. 指令和数据所在的存储单元
【答案】C
【解析】在冯•诺依曼结构计算机中指令和数据均以二进制形式存放在同一个存储器中，CPU 可以根据指令周期的不同阶段来区分是指令还是数据，通常在取指阶段取出的是指令，其他阶段（分析取数阶段、执行阶段）取出的是数据。所以，CPU 区分指令和数据的依据是指令周期的不同阶段。
4． 设文件索引节点中有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。
5． 假定编译器规定int 和short 类型长度分别为32位和16位，执行下列C
语言语句
得到y 的机器数为（ ）。
【答案】B 。
【解析】X 和y 均为无符号数，其中X 为16位，y 为32位，将16位无符号数转化成32位
无符号数，前面要补零。因为所以
6． 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A. 单链表
B. 仅有头指针的单循环链表
C. 双链表
D. 仅有尾指针的单循环链表
【答案】D
【解析】仅有尾指针的单循环链表，在最后插入元素和删除第一个元素都会用到这个尾指针。
7． 数据链路层采用后退N 帧（GBN ）协议，发送方已经发送了编号为0〜7的倾。当计时器超时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是（ ）。
A.2
B.3
C.4
D.5
【答案】C
【解析】后退N 帧协议，即GO-BACK-N 策略的基本原理是，当接收方检测出失序的信息帧
后，要求发送方重发最后一个正确接收的信息帧之后的所有未被确认的帧；或者当发送方发送了N 个帧后，若发现该N 帧的前一个帧在计时器超时后仍未返回其确认信息，则该帧被判为出错或丢失，此时发送方就不得不重新发送出错帧及其后的N 帧。本题收到3号帧的确认，说明0，1，2，3号帧已经收到，丢失的是4，5，6, 7号帧，共4帧。因此答案为C 项。
8． 下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。
A. 二叉排序树
B. 哈夫曼树 C.
D. 堆
【答案】D
【解析】堆的定义：
n 个关键字序列
（1）（2）且且或 称为堆，当且仅当该序列满足如下性质（简称为堆性质）： 树
满足第（1）种情况的堆，称为小顶堆；满足第（2）种情况的堆，称为大顶堆。
由堆的定义可知堆可以满足上述性质。
9． 已知一个长度为16的顺序表L , 其元素按关键字有序排列。若采用折半查找法查找一个L 中不存在的元素，则关键字的比较次数最多是（ ）。
A.4
B.5
C.6
D.7
【答案】B
【解析】折半查找法在查找不成功时和给定值进行比较的关键字个数最多为（l 〇g2n ） +1，在本题中，n=16, 故比较次数最多为5。
10．下列选项中的英文缩写均为总线标准的是（ ）。
A.PCI 、CRT 、USB 、EISA
B.ISA 、CPI 、VESA 、EISA
C.ISA 、SCSI 、RAM 、MIPS
D.ISA 、EISA 、PCI 、PCI-Express
【答案】D
【解析】选项A 中的CRT 和USB 、选项B 中的CPI 、选项C 中的RAM 和MIPS 均不是总线标准的英文缩写，只有选项D 中的英文缩写均为总线标准。