2016年南京邮电大学物联网学院数据结构复试笔试最后押题五套卷
● 摘要
一、选择题
1． 一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（ ）。
A. 其中任意一个结点均无左孩子
B. 其中任意一个结点均无右孩子
C. 其中只有一个叶结点
D. 其中度为2的结点最多为一个
答:C
【解析】前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树才有可能，所以本题的A 项和B 项均对，单支树的特点是只有一个叶结点，故C 项是最合适的。A 项或B 项都不全。
2． 在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电缆，传输速率为1Gbps , 电缆中的信号传播速度是200000km/s。若最小数据帧长度减少800bit ，则最远的两个站点之间的距离至少需要（ ）。
A. 增加160m
B. 增加80m
C. 减少160m
D. 减少80m
答:D
【解析】以太网采用CSMA/CD访问协议，在发送的同时要进行冲突检测，这就要求在能检测出冲突的最大时间内数据包不能够发送完毕，否则冲突检测不能有效地工作。所以，当发送的数据包太短时必须进行填充。最小帧长度=碰撞窗口大小x 报文发送速率，本题最小数据帧长度减少800b ，那么碰撞的窗口也要减少，因此距离也要减少，从而（800×2×）/（l ×）=160m，由于时间延时存在两倍的关系，因此减少的距离为80m 。
3． 某CPU 主频为1.03GHz , 采用4级指令流水线，每个段的执行需要1个时钟周期。假定CPU
执行了100条指令，在其执行过程中没有发生任何流水线阻塞，此时流水线的吞吐率为（ ）
A.
B.
C.
D.
答:C
条指令/秒 条指令/秒 条指令/秒 条指令/秒
【解析】采用4级流水线执行100条指令，在执行过程中共用
条指令/秒，故答案为C 。
4． 下列指令中，不能在用户态执行的是（ ）
A.trap 指令
B. 跳转指令
C. 后栈指令
D. 关中断指令
答:D 个时钟周期。CPU 的主频是1.03GHz , 也就是说每秒钟有1.03G 个时钟周期。流水线的吞吐率
为
【解析】关中断指令必须在和心态才能执行，trap 指令可以在用户态下执行，执行了就转到和心态，跳转与退栈指令都是可以在用户态下执行的指令。
5． 某计算机处理器主频为50MHz ，采用定时查询方式控制设备A 的I/0, 查询程序运行一次所用的时钟 周期数至少为500。在设备A 工作期间，为保证数据不丢失，每秒需对其查询至少200次，则CPU 用于设备A 的I/0的时间占整个CPU 时间的百分比至少是（ ）。
A.0.02%
B.0.05%
C.0.20%
D.0.50%
答:C
【解析】对于设备A ，每秒中查询至少200次，每次查询至少500个时钟周期，总的时钟周期数为100000, 又因为处理器主频为50MHz 。所以CPU 用于设备A 的I/0的时间占整个CPU 时间的百分比至少为100000/50=0.20%。
6． 响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括（ ）。
I. 开关中断II. 保存通用寄存器的内容III. 形成中断服务程序入口地址并送PC
A. 仅I 、II
B. 仅 I 、III
C. 仅 II 、III
D.I 、II 、III
答:B 。
【解析】中断隐指令完成的操作有3个：①保存断点；②关中断；③引出中断服务程序（形成中断服务程序入口地址并送PC ）。而保存通用寄存器内容的操作是由软件来实现，不是由中断隐指令实现的。
7． 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（ ）。
A.4
B.5
C.6
D.7
答:C
【解析】若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。具有n 个
全二叉树的高度为
叉树的高度为
8． 已知串
A.0123
B.1123
C.1231
D.1211
答:A 或或 结点的完由完全二叉树类推到完全三叉树可知，n 个结点的完全三其Next 数组值为（ ）。
【解析】KMP 算法的next 数组建立的原则
9． 以太网的MAC 协议提供的是（ ）。
A. 无连接不可靠服务
B. 无连接可靠服务
C. 有连接不可靠服务
D. 有连接可靠服务
答:A 。
【解析】考查以太网MAC 协议，考虑到局域网信道质量好，以太网采取了两项重要的措施以使通信更简洁：①采用无连接的工作方式；②不对发送的数据帧进行编号，也不要求对方发回确认。因此，以太网提供的服务是不可靠的服务，即尽最大努力交付，差错的纠正由高层完成。
10．采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（ ）。
A. 递归次数与初始数据的排列次序无关
B. 每次划分后，先处理较长的分区可以减少递归次数
C. 每次划分后，先处理较短的分区可以减少递归次数
D. 递归次数与每次划分后得到的分区的处理顺序无关
答:D
【解析】快速排序是递归的，递归过程可用一棵二叉树给出，递归调用层次数与二叉树的深
，采用快速排序方法，其对应递归调用度一致。例如：待排序列{48, 62，35, 77, 55, 14, 35, 98）
过程的二叉树如下图所示。