两道最新网易在线笔试真题的分析和解答

3月21日刚刚进行的网易2016年招聘在线笔试中有这样两个题目：

题目一：

若一棵二叉树的前序遍历序列和后序遍历序列分别为1, 2,3, 4和4, 3, 2, 1，则该二叉树的中序遍历序列不会是

A．1, 2,3, 4 

B．2, 3,4, 1

C．3, 2,4, 1

D．4, 3,2, 1

该题考查二叉树的三种遍历方法，及由两种遍历序列构造二叉树的过程。

已知一棵二叉树的前序序列和中序序列，或已知其后序序列和中序序列，都能唯一确定该二叉树。而由一棵二叉树的前序序列和后序序列并不能唯一确定这棵二叉树。

因此，该题的解法可以用题目中所给的前序序列与选项中的中序序列来构造二叉树，再来验证这棵二叉树的后序序列是否是4,3,2,1。

前序序列为1,2,3,4时，采用选项A、B、D所给出的中序序列，均能得到后序序列为4,3,2,1的二叉树。这3棵二叉树依次为

而当前序序列为1,2,3,4、中序序列为3,2,4,1时，所确定的二叉树的后序序列为3,4,2, 1，对应的二叉树为

与题目中所给的后序序列4,3,2,1不一致。所以答案为C。

题目二：

某计算机的CPU主频为500MHz，CPI为5（即执行每条指令平均需5个时钟周期）。假定某外设的数据传输率为0.5 MB/s，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。

（1）在中断方式下，CPU用于该外设I/O的时间占整个CPU时间的百分比是多少？

（2）当该外设的数据传输率达到5 MB/s时，改用DMA方式传送数据。假定每次DMA传送块大小为5000 B，且DMA预处理和后处理的总开销为500个时钟周期，则CPU用于该外设I/O的时间占整个CPU时间的百分比是多少？（假设DMA与CPU之间没有访存冲突）

参考答案：

（1）中断方式下，CPU每次用于数据传送的时钟周期数为：5*18 +5*2 = 100

为达到外设0.5 MB/s的数据传输率，外设每秒申请的中断次数为：0.5 MB /4 B = 125 000

1秒钟内用于中断的开销：100 * 125 000 = 12500 000 = 12.5 M个时钟周期 

因此，CPU用于外设I/O的时间占整个CPU时间的百分比：12.5 M/500 M = 2.5% 

 （2）外设数据传输率提高到5 MB/s时，1秒钟内需产生的DMA次数：

5 MB/5 000 B = 1000   

CPU用于DMA处理的总开销：1000 *500 = 500000 = 0.5 M个时钟周期  

CPU用于外设I/O的时间占整个CPU时间的百分比：0.5 M/500 M = 0.1%