当前位置：问答库＞考研试题

一、选择题

1． 下列关于中断

A.

中断方式和DMA 方式比较的叙述中，错误的是（ ） 方式请求的是方式请求的是CPU 处理时间，DMA 方式请求的是总线使用权

B. 中断响应发生在一条指令执行结束后，中断响应发生在一条指令执行结束后，DMA 响应发生在一个总线事务完成后

C.

中断

D. 中断

部设备

【答案】D

【解析】中断处理方式:在

与设备输入每个数据的过程中，由于无需CPU 干预，因而可使CPU

设备并行工作。仅当输完一个数据时，才需CPU 花费极短的时间去做些中断处理。因此中方式下数据传送通过软件完成，方式下数据传送通过软件完成，DMA 方式下数据方式适用于所有外部设备，方式适用于所有外部设备，DMA 方式仅适用于快速外传送由硬件完成 断申请使用的是CPU 处理时间，发生的时间是在一条指令执行结束之后，数据是在软件的控制下完成传送。而DMA 方式与之不同。DMA 方式：数据传输的基本单位是数据块，即在CPU 与设备之间，每次传送至少一个数据块，DMA 方式每次申请的是总线的使用权，所传送的数据是从设备直接送入内存的或者相反；仅在传送一个或多个数据块的开始和结束时，才需 CPU 干预，整块数据的传送是在控制器的控制下完成的。答案D 的说法不正确。

2． 二叉树在线索化后，仍不能有效求解的问题是（ ）。

A. 前序线索二叉树中求前序后继

B. 中序线索二叉树中求中序后继

C. 中序线索二叉树中求中序前驱

D. 后序线索二叉树中求后序后继

【答案】D

【解析】后序线索二叉树求后序后继要分3种情况，比较复杂，不是仅仅线索化后就能求解的，算法上还要要分情况讨论。

3． 直接插入排序在最好情况下的时间复杂度为（ ）。

【答案】B

【解析】当序列是按照直接插入排序的顺序有序时，此时进行插入时，每次都只需要和末尾的一个元素进行比较，此时的时间复杂度最好，为

第 2 页，共 31 页

4． 已知一个长度为16的顺序表L , 其元素按关键字有序排列。若采用折半查找法查找一个L 中不存在的元素，则关键字的比较次数最多是（ ）。

A.4

B.5

C.6

D.7

【答案】B

【解析】折半查找法在查找不成功时和给定值进行比较的关键字个数最多为（l 〇g2n ） +1，在本题中，n=16, 故比较次数最多为5。

5． 一个C 语言程序在一台32位机器上运行。程序中定义了3个变量x 、Y 和z ，其中x 和z 为int 型，Y 为short 型。当x=127，Y=-9时，执行赋值语句z=x+Y后，x 、Y 和z 的值分别是（ ）。

A.x=0000007FH, Y=FFF9H, z=00000076H

B.x=0000007FH, Y=FFF9H, z=FFFF0076H

C.x=0000007FH, Y=FFF7H, z=FFFF0076H

D.x=0000007FH, Y=FFF7H, z=00000076H

【答案】D

【解析】当两个不同长度的数据，要想通过算术运算得到正确的结果，必须将短字长数据转换成长字长数据，这被称为“符号扩展”。例如，x 和z 为int 型，数据长32位，Y 为short 型，数据长16位，因此首先应将y 转换成32位的数据，然后再进行加法运算。运算采用补码的形式，而x 的补码是0000007FH , Y 的补码是FFFFFFF7H , 所以x+Y=00000076H。

6． 若串其子串的数目是（ ）。

A.8

B.37

C.36

D.9

【答案】B

【解析】子串的定义是：串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。若字符串长度为

长为

为：

7． 在一株高度为2的5阶B 树中，所含关键字的个数最少是（ ）

A.5

B.7

C.8

D.14

【答案】A

【解析】根据B 树的定义可知，跟结点最少含有

树最少有（5-1）+1=5个关键字，其中根节点含有

第 3 页，共 31 页 长为n 的子串有1个，长为的子串有2个，的子串有3个，……，长为1的子串有n 个。由于空串是任何串的子串，所以本题的答案故选B 。 个关键字，高度为2的阶B 个关键字，第2层结点含有1关键字。

8． 基于比较方法的n 个数据的内部排序。 最坏情况下的时间复杂度能达到的最好下界是（ ）。

A.0（nlogn ）

B.O （logn ）

C.O （n ） D.

【答案】A

【解析】在内部排序中，最坏情况下的时间复杂度为0（nlogn ）。

已知待排序的n 个元素可分为个组，每个组包含k 个元素，且任一组内的各元素均分别大干前一

9． 某计算机系统中有8台打印机，由K 个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K 最小值是（ ）。

A.2

B.3

C.4

D.5

【答案】C

【解析】死锁的抽屉原理一般描述是：将5个苹果放进4个抽屉，那么，必然有1个抽屉中至少有2个苹果。计算机系统的资源分配充分体现了这一原理。考察进程运行的特点，只要有一个进程能够运行，则运行结束后必然会归还资源，其余的进程也就会得到满足从而可以执行（这里考虑的资源主要是可重用的资源，不可重用的资源会消失，就不可用上述方法分析）。所以最少需要4个进程竞争使用，每个进程占用2台打印机，此时会产生死锁。

10．下列进程调度算法中，综合考虑进程等待时间和执行时间的是（ ）。

A. 时间片轮转调度算法

B. 短进程优先调度算法

C. 先来先服务调度算法

D. 尚响应比优先调度算法

【答案】D

【解析】时间片轮转法和先来先服务算法都是公平的方法，并未考虑进程等待时间和执行时间，而短进程优先考虑的是进程执行时间。最高响应比优先调度算法是最先执行响应比最尚的进程（响应比=1＋等待时间/估计运行时间）。该算法综合了先来先服务（FCFS ）和短作业优先（SJF ）算法，FCFS 只考虑每个作业的等待时间，而未考虑执行时间的长短。SJF 只考虑执行时间的长短，而未考虑等待时间的长短，HRRN 算法则同时考虑执行时间和等待时间。

第 4 页，共 31 页