2016年南京邮电大学物联网学院数据结构考研复试题库
● 摘要
一、选择题
1． 下列选项中，对正确接收到的数据帧进行确认的MAC 协议是（ ）。
A.CSMA
B.CDMA
C.CSMA/CD
D.CSMA/CA
答:D
【解析】可采用排除法。CDMA 是码分多址复用，是物理层的内容；CSMA/CD即带冲突检测的载波监听多 路访问，接收方并不需要确认；CSMA/CD是CSMA 的加强版，故CSMA 也无确定；CSMA/CD是802.11中的 协议，其利用ACK 信号来避免冲突的发生，也就是说，只有当
客户端收到网络上返回的ACK 信号后才确认送 出的数据已经正确到达目的地址，因此答案是D 。
2． 偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中，不属于偏移寻址方式的是（ ）。
A. 间接寻址
B. 基址寻址
C. 相对寻址
D. 变址寻址
答:A
【解析】在四种不同的寻址方式中，间接寻址按指令的形式地址从主存中取出操作数的有效地址，然后再按此有效地址从主存中读出操作数。其余三种寻址方式可以统称为偏移寻址。
3． 下列有关RAM 和ROM 的叙述中，正确的是（ ）。
I.RAM 是易失性存储器，ROM 是非易失性存储器
II.RAM 和ROM 都采用随机存取方式进行信息访问
III.RAM 和ROM 都可用作Cache
IV.RAM 和ROM 都需要进行刷新
A. 仅I 和II
B. 仅II 和III
C. 仅 I 、II 和IV
D. 仅II 、III 和IV
答:A
RAM 中的内容断电后即丢失ROM 中的内容断电后不会丢失，，【解析】（易失性）（非易失性）
，同时RAM 和ROM 都采用随机存取方式（即CPU 对任何一个存储单元的存取时间相同）区别在
于RAM 可读可写，ROM 只读不写。而ROM 显然不可用作Cache , 也不需要刷新，所以III 和IV 的叙述都是错误的。
4． 某设备中断请求的相应和处理时间为100m ，每400ns 发出一次中断请求，中断相应所容许的最长延迟时间为50ns , 贝U 在该设备持续工作过程中CPU 用于该设备的
百分比至少是（ ） A. B. C. D.
答:B
【解析】每400m 响应一次中断并且用100m 进行处理，所以该设备的时间占用CPU 时间
百分比为中断响应容许的延迟时间对此没有影响，属于干扰条件。
5． 知一棵二叉树的前序遍历结果为ABCDEF ，中序遍历结果为CBAEDF ，则后序遍历结果为（ ）。
A.CBEFDA
B.FEDCBA
C.CBEDFA
D. 不定
答:A
【解析】由前序结果可知A 为根节点，再由中序遍历结果知BC 为A 的左孩子，且C 为B 的左孩子结点，到此可排除B 项，按照这种逻辑依次推理，便可得出结果对于该类型题目，可以先根据前序遍历结果和中序遍历结果画出二叉树，然后后序遍历二叉树得到后序遍历序列。
6． 以太网的MAC 协议提供的是（ ）。
A. 无连接不可靠服务
B. 无连接可靠服务
C. 有连接不可靠服务
D. 有连接可靠服务
答:A 。
【解析】考查以太网MAC 协议，考虑到局域网信道质量好，以太网采取了两项重要的措施以使通信更简洁：①采用无连接的工作方式；②不对发送的数据帧进行编号，也不要求对方发回确认。因此，以太网提供的服务是不可靠的服务，即尽最大努力交付，差错的纠正由高层完成。
7． 在一个有N 个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（ ）。
答:B
时间占整个CPU 时间