2018年上半年软件设计师

真题+答案解析 上午选择

1、对有n个结点、e条边且采用数组表示法（即邻接矩阵存储）的无向图进行深度优先遍历，时间复杂度为（1）。 A. O(n2) B. O(e2) C. O(n+e) D. O(n*e) 答案： A

在邻接表中，就是要依次访问每个顶点，然后在每个顶点中依次访问每条边，把这些边的终点的入度+1。也就是每个顶点和每条边依次要各访问一遍，所以时间复杂度是O(n+e)。在邻接矩阵中，算法需要遍历邻接矩阵的每一个点，而邻接矩阵有n*n个点，所以时间复杂度是O(n*n)。

2、浮点数的表示分为阶和尾数两部分。两个浮点数相加时，需要先对阶，即（ ）（n为阶差的绝对值）。 A. 将大阶向小阶对齐，同时将尾数左移n位 B. 将大阶向小阶对齐，同时将尾数右移n位 C. 将小阶向大阶对齐，同时将尾数左移n位

百度文库：荣光时空

D. 将小阶向大阶对齐，同时将尾数右移n位 答案： D

对阶时，小数向大数看齐；对阶是通过较小数的尾数右移实现的。

3、计算机运行过程中，遇到突发率件，要求CPU暂时停止正在运行的程序，转去为突发事件服务，服务完毕，再自动返回原程序继续执行，这个过程称为（3），其处理过程中保存现场的目的是（4）。

A. 阻塞 B. 中断 C. 动态绑定 D. 静态绑定 答案： B

4、 A. 防止丢失数据 B. 防止对其他部件造成影响 C. 返回去维续执行原程序 D. 为中断处理程序提供数据 答案： C

中断是指计算机运行过程中，出现某些意外情况需主机干预时，机器能自动停止正在运行的程序并转入处理新情况的程序，处理完毕后又返回原被暂停的程序继续运行。

百度文库：荣光时空

5、海明码是一种纠错码，其方法是为需要校验的数据位增加若干校验位，使得校验位的值决定于某些被校位的数据，当被校数据出错时，可根据校验位的值的变化找到出错位，从而纠正错误。对于32位的数据，至少需要加（5）个校验位才能构成海明码。

以

10

位数据为例，其海明码表示为

D9D8D7D6D5D4P4D3D2D1P3D0P2P1中，其中Di（0≤i≤9）表示数据位，Pj（1 ≤j≤4）表示校验位，数据位D9由P4、P3和P2进行校验（从右至左D9的位序为14，即等于8＋4＋2，因此用第8位的P4、第4位的P3和第2位的P2校验），数据位D5由（6）进行校验。 A. 3 B. 4 C. 5 D. 6 答案： D

海明不等式：校验码个数为k，2的k次方个校验信息，1个校验信息用来指出“没有错误”，满足m+k+1<=2k。所以32位的数据位，需要6位校验码。 6、A. P4P1 B. P4P2 C. P4P3P1 D. P3P2P1 答案： B

百度文库：荣光时空

数据位D9受到P4、P3、P2监督（14=8+4+2），那么D5受到P4、P2的监督（10=8+2）。

7、流水线的吞吐率是指单位时间流水线处理的任务数，如果各段流水的操作时间不同，则流水线的吞吐率是（7）的倒数。 A. 最短流水段操作时间 B. 各段流水的操作时间总和 C. 最长流水段操作时间

D. 流水段数乘以最长流水段操作时间 答案： C

流水线处理机在执行指令时，把执行过程分为若干个流水级，若各流水级需要的时间不同，则流水线必须选择各级中时间较大者为流水级的处理时间。

理想情况下，当流水线充满时，每一个流水级时间流水线输出一个结果。

流水线的吞吐率是指单位时间流水线处理机输出的结果的数目，因此流水线的吞吐率为一个流水级时间的倒数，即最长流水级时间的倒数。

8、网络管理员通过命令行方式对路由器进行管理，要确保ID，口令和会话话内存的保密性，应采取的访问方式是（8）。 A. 控制台

百度文库：荣光时空