考研408计算机学科专业基础在线题库每日一练（五十九）

本文提供考研408计算机学科专业基础在线题库每日一练，以下为具体内容

1、求整数n （n≥0）阶乘的算法如下，其时间复杂度是

A、 O（log₂n）

B、 O（n）

C、 O（nlog₂n）

D、 O（n²）

2、外部中断包括不可屏蔽中断（NMI）和可屏蔽中断，下列关于外部中断的叙述中，错误的是（ ）。

A、CPU处于关中断状态时，也能响应NMI请求

B、一旦可屏蔽中断请求信号有效，CPU将立即响应

C、不可屏蔽中断的优先级比可屏蔽中断的优先级高

D、可通过中断屏蔽字改变可屏蔽中断的处理优先级

3、内部异常（内中断）可分为故障（fault）、陷阱（trap）和终止（abort）三类。下列有关内部异常的叙述中，错误的是（  ）。

A、内部异常的产生与当前执行指令相关

B、内部异常的检测由CPU内部逻辑实现

C、内部异常的响应发生在指令执行过程中

D、内部异常处理后返回到发生异常的指令继续执行

4、使用迪杰斯特拉（Dijktra） 算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是（  ）。

A、 5，2，3，4，6

B、 5，2，3，6，4

C、 5，2，4，3，6

D、 5，2，6，3，4

5、在无转发机制的五段基本流水线（取指、译码/读寄存器、运算、访存、写回寄存器）中，下列指令序列存在数据冒险的指令对是（  ）。I1：add R1,R2,R3;(R2)+(R3)→R1I2：add R5,R2,R4;(R2)+(R4)→R5I3：add R4,R5,R3;(R5)+(R3)→R4I4：add R5,R2,R6;(R2)+(R6)→R5

A、I1和I2

B、I2和I3

C、I2和I4

D、I3和I4

1、试题答案：B

试题解析：

【考点】本题考查时间复杂度的计算。
【解析】上述算法为递归算法。由程序段可以分析，当n<=1时，函数调用1次；当n>1时，函数的调用次数与n的大小有关，函数会调用n-1次，而乘法形式出现的n不影响调用次数，可以看做fact(n-1)的系数。根据上述程序该递归算法的时间复杂度分两部分讨论，当n<=1时，时间复杂度为O(1)；当n>1时，时间复杂度为T(n-1)+1。根据时间复杂度的运算规则，上述程序的时间复杂度为O(n)，故本题选B。

2、试题答案：B

试题解析：

【考点】本题考查计算机组成原理--输入输出系统--程序中断方式--中断的基本类型--非屏蔽中断和可屏蔽中断。
【解析】由CPU内部产生的异常称为内中断。通过中断请求线INTR和NMI从CPU外部发出的中断请求为外中断。内中断都是不可屏蔽中断。通过INTR信号线发出的外中断是可屏蔽中断，而通过NMI信号线发出的是不可屏蔽中断。不可屏蔽中断的处理优先级最高，任何时候只要发生不可屏蔽中断，都要中止现行程序的执行，转到不可屏蔽中断处理程序执行。CPU响应可屏蔽中断需要满足3个条件：（1）首先中断源要发出中断请求，同时CPU还要接收到这个中断请求信号；（2）CPU允许中断，即开中断；（3）一条指令执行完毕且没有更紧迫的任务时。故本题选B。

3、试题答案：D

试题解析：

【考点】本题考查计算机组成原理--中央处理器（CPU）--异常和中断处理--内部异常。
【解析】内部异常（exception）是指由处理器内部异常引起的意外事件。内部异常的发生通常与当前执行的指令有关，例如除零错误、无效操作码等。故排除选项A；CPU内部的逻辑电路负责检测和识别内部异常的发生。故排除选项B；当内部异常被检测到时，通常会中断当前指令的执行，跳转到异常处理程序进行相应的处理。故排除选项C；处理内部异常后，根据异常类型和处理程序的设计，可能会有不同的行为。有些异常处理程序可能会返回到发生异常的指令继续执行，但也有可能会终止当前程序的执行或者进行其他的操作。故本题选D。

4、试题答案：B

试题解析：

【考点】本题考查迪杰斯特拉算法求单源最短路径。
【解析】设添加的目标顶点序列为A，未添加的序列为B根据迪杰斯特拉算法求出顶点1到其余各点的距离的过程如下：
（1）初始时，A={1}，B={2,3,4,5,6}，顶点1到其余各点的距离：

从B中选出距离顶点1最近的顶点5添加到B中，此时A={1,5}，B={2,3,4,6}，顶点1到其余各点的距离更新为：

从B中选出距离顶点1最近的顶点2添加到B中，此时A={1,5,2}，B={3,4,6}，顶点1到其余各点的距离更新为：

从B中选出距离顶点1最近的顶点3添加到B中，此时A={1,5,2,3}，B={4,6}，顶点1到其余各点的距离更新为：

从B中选出距离顶点1最近的顶点6添加到B中，此时A={1,5,2,3,6}，B={4}，顶点1到其余各点的距离更新为：

从B中选出距离顶点1最近的顶点6添加到B中，此时A={1,5,2,3,6,4}，B={}，顶点1到其余各点的距离更新为：

从顶点A的序列得出依次加入的目标顶点为5、2、3、6、4，故本题选B。

5、试题答案：B

试题解析：

【考点】本题考查计算机组成原理--中央处理器（CPU）--流水线技术--指令流水线的相关性--数据相关/数据冒险。
【解析】后续指令要使用前面指令的操作结果，而这一结果尚未产生或者未送到指定的位置，从而造成后续指令无法运行的局面称为数据冒险。未对数据相关进行特殊处理的流水线如下表所示。

指令I2在WB段（第6个时钟周期）才将计算结果写入寄存器R5中，但指令I3在其ID段（第4个时钟周期）就要从寄存器R2中读取该计算结果。因此存在I2和I3对存在RAW相关。故本题选B。