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

一、选择题

1． 设被排序的结点序列共有N 个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为（ ）。

【答案】C

【解析】因为该序列中的结点已经十分接近排序的情况，对于直接插入法，大部分结点只需要直接插入后面即可，因此时间复杂度为的时间复杂度为

对于采用归并法，它是一种稳定的排序方法，它

对于一般的快速排序法，序列越接近有序，所需要的比较次数越多，

此时的时间复杂度为

2． 若则下列表达式采用8位定点补码运算实现时，会发生溢出的是（ ）

A.x+y B.-x+y C.x-y D.-x-y

【答案】C

【解析】8位定点补码能表示的数的范围为：码能表示的数的范围，会发生溢出

3． 假设磁头当前位于第105道，正在向磁道序号増加的方向移动。现有一个磁道访问请求，序列为35, 45, 12, 68, 110, 180, 170, 195，采用SCAN 调度（电梯调度）算法得到的磁道访问序列是（ ）。

A.110, 170, 180, 195，68, 45, 35，12

B.110，68，45，35，12，170，180，195 C.110，170，180，195，12，35, 45, 68 D.12, 31, 45, 68, 110, 170, 180, 195

【答案】A

【解析】SCAN 算法类似电梯工作原理，即朝一个固定方向前进，经过的磁道有访问请求则马上服务，直至到达一端顶点，再掉头往回移动以服务经过的磁道，并这样在两端之间往返。因此，当磁头从105道向序号増加的方向移动时，便会服务所有大于105的磁道号（从小到大的顺序）；往回返时又会按照从大到小的顺序进行服务。注意与循环扫描算法的区别，所以SCAN 算法的访问序列是：110, 170，180，195, 68, 45, 35, 12。

A 结果为78, B结果为-128, D结果为-78都在此范围内，只有C 结果128超过了8位定点补

4． 分区分配内存管理方式的主要保护措施是（ ）。

A. 界地址保护 B. 程序代码保护 C. 数据保护 D. 栈保护 【答案】A

【解析】对于连续分配算法，无论固定分区或动态分区方法，程序都必须全部调入内存，不同的进程放于不同的内存块中，相互之间不可越界，因此需要进行界地址保护。通常的界地址保护方法采用软硬件结合的方法。考生要注意本题与虚拟存储方法的区别。

5． n 个结点的完全有向图含有边的数目（ ）。

A.n*n

B.n （n+l） C.n/2

D.n*（n-l ）

【答案】D

【解析】在有向图中，如果任意两个顶点之间都存在边，则称为有向完全图。顶点个数为n 的无向图，最多有

条边。如是有向图，需要在无向图的最多边的基础上乘以2，则

为n （n-l ）。

6． 下列存储器中，在工作期间需要周期性刷新的是（ ）。

A.SRAM B.SDRAM C.ROM D.FLASH 【答案】B

【解析】动态随机存储器（DRAM ）是利用存储元电路中栅极电容上的电荷来存储信息的，电容上的电荷一般只能维持

因此即使电源不掉电，信息也会自动消失。为此，每隔一定时

间必须刷新。

7． 在OSI 参考模型中，直接为会话层提供服务的是（ ）

A. 应用层 B. 表示层 C. 传输层 D. 网络层 【答案】C

【解析】OSI 参考模型中，下层直接为上层提供服务，而会话层的下层为传输层。

8． 已知关键字序列5, 8, 12, 19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（ ）。

A.3, 5，12，8, 28，20, 15，22，19 B.3, 5, 12, 19, 20, 15, 22, 8, 28 C.3, 8, 12, 5, 20, 15, 22, 28, 19 D.3, 12, 5, 8, 28, 20, 15, 22, 19 【答案】A

【解析】在堆中插入或删除一个元素后，将不再满足堆的性质。为了使其成为新堆，在输出堆顶元素后，需要调整剩余元素。具体过程如图（1）〜（5）所示，（1）为原堆，（2）为插入3后，（3）、（4）为调整过程，（5）为调整后的小根堆。