2018年安徽建筑大学计算机技术909数据结构[专业硕士]考研基础五套测试题
● 摘要
一、单项选择题
1． 下列选项中, 对正确接收到的数据帧进行确认的MAC 协议是（ ）。
A.CSMA
B.CDMA C. D.
【答案】D
【解析】可采用排除法。CDMA 是码分多址复用, 是物理层的内容; CSMA/CD即带冲突检测的载波监听多路访问, 接收方并不需要确认; CSMA/CD是CSMA 的加强版, 故CSMA 也无确定; CSMA/CD是中的协议, 其利用ACK 信号来避免冲突的发生, 也就是说, 只有当客户端收到网络上返回的ACK 信号后才确认送出的数据已经正确到达目的地址, 因此答案是D 。
2． 元素a , b , c , d , e 依次进入初始为空的栈中, 若元素进栈后可停留、可出栈, 直到所有元素都出栈, 则在所有可能的出栈序列中, 以元素d 开头的序列个数是（ ）。
A.3
B.4
C.5
D.6
【答案】B
【解析】d 首先出栈后的状态如下图所示。
此时可有以下4种操作:
(1)e进栈后出栈, 出栈序列为decba 。
(2)c出栈, e 进栈后出栈, 出栈序列为dceba 。
(3)cb出栈, e 进栈后出栈, 出栈序列为dcbea 。
(4)cba出栈, e 进栈后出栈, 出栈序列为dcbae 。
3． 设有一棵3阶B 树, 如下图所示。删除关键字78得到一棵新B 树, 其最右叶结点所含的关键字是（ ）。
图 3二叉树图
A.60
B.60, 62
C.62, 65
D.65
【答案】D 。
【解析】本题主要考查B 树删除操作。即被删关键字所在的结点中的关键字个数等于
而与该结点相邻的右兄弟(或左兄弟) 结点中的关键字数目大于
(或最大) 的关键字上移至双亲结点中, 而将双亲结点中小于(或大于) 且紧靠该上移关键字的关键字下移至被删关键字所在结点中。题目中删除关键字78得到一棵新B 树如下, 其最右叶结点所含的关键字是65。
, , 则需将其兄弟结点中最小
4． 对于下列关键字序列, 不可能构成某二叉排序树中一条查找路径的序列是（ ）。
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。
5． 用户程序发出磁盘 请求后, 系统的正确处理流程是（ ）。
A. 用户程序—系统调用处理程序—中断处理程序—设备驱动程序
B. 用户程序—系统调用处理程序—设备驱动程序—中断处理程序
C. 用户程序—设备驱动程序—系统调用处理程序—中断处理程序
D. 用户程序—设备驱动程序—中断处理程序—系统调用处理程序
【答案】B
【解析】对于一次设备的调用, 操作系统为用户准备了系统调用的接口, 当用户使用设备时, 首先在用户程序中发起一次系统调用, 操作系统的内核接到该调用请求后调用处理程序进行处理, 根据调用格式和形参, 再转到相应的设备驱动程序去处理; 大部分设备在运行时是需要时间的, 所以设备驱动程序会以中断方式驱动设备, 即设置好控制寄存器参数和中断向量等参数后阻塞自己; 当设备准备好或所需数据到达后设备硬件发出中断, 设备驱动程序唤醒, 将数据按上述调用顺序逆向回传到用户程序中, 或继续驱动设备执行下一条指令。因此, 正确的顺序应该是用户到系统调用到驱动到中断处理。中断处理处于最底层。
6． 哈希函数有一个共同的性质，即函数值应当以（ ）取其值域中的每个值。
A. 最大概率
B. 最小概率
C. 平均概率
D. 同等概率
【答案】D
7． 假定一台计算机的显示存储器用DRAM 芯片实现, 若要求显示分辨率为1600x1200, 颜色深度
为24位, 帧频为85Hz , 显存总带宽的50%用来刷新屏幕, 则需要的显存总带宽至少约为（ ）。
A.245Mbps
B.979Mbps
C.1958Mbps
D.7834Mbps
【答案】D