一、选择题

1． 图G 是n 个顶点的无向完全图，则下列说法不正确的是( )

A.G 的邻接多重表需要n (n-l )个边结点和n 个顶点结点 B.G 的连通分量个数最少 C.G 为连通图

D.G 所有顶点的度的总和为n (n-1) 【答案】A

【解析】A 项中G 的邻接多重表中需要n (n-l )/2个边结点和n 个顶点结点。此时连通分量最少为1。无向完全图中任意两个顶点之间都存在路径，则G 必为连通图。每个顶点的度为n-1，则n 个结点的度的总和为n (n-l )。

2． 下列关于虚拟存储的叙述中，正确的是( )。

A. 虚拟存储只能基于连续分配技术 B. 虚拟存储只能基于非连续分配技术 C. 虚拟存储容量只受外存容量的限制 D. 虚拟存储容量只受内存容量的限制 【答案】D 。

【解析】所谓虚拟存储，是指运行的进程不必全部装入内存，只需要部分装入便可以开始运行的一种技术，在运行过程中，当所需要的代码部分不在内存时，通过一种技术(例如缺页中断，技术)将所需要的页面调入内存，从而继续运行。虚拟存储可以在较少的内存中运行较大的程序。但是需要有较大的外存以及相应的软、硬件 机制配合才能实现。虚拟存储器可以连续分配也可以非连续分配，虚拟存储器和外存大小没有关系，所以选项中 的A ，B ，C 都是错误的，所以答案是D 项。

3． 已知串

A.0123 B.1123 C.1231 D.1211 【答案】A

其Next 数组值为( )。

【解析】KMP 算法的next 数组建立的原则

4． 系统为某进程分配了4个页框，该进程已访问的页号序列为2, 0, 2, 9, 3, 4, 2, 8, 2, 3, 8, 4, 5, 若进程要访问的下一页的页号为7，依据LRU 算法，应淘汰页的页号是( )。

A.2 B.3 C.4 D.8

【答案】B

【解析】LRU 置换算法是选择最近最久未使用的页面予以淘汰。进程有4个页框，题中访问过程中页框的变化如下：

序列：页框：

淘汰：3。

5． 对于栈操作数据的原则是( )。

A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 【答案】B

【解析】先进先出是队列操作数据的原则。先进后出是栈操作数据的原则，栈限定在表尾进行插入和删除。

6． 动态存储管理系统中，通常可有( )种不同的分配策略。

【答案】C

【解析】动态存储管理系统中有以下三种：首次拟合法、最佳拟合法、最差拟合法。①首次拟合法，从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户。②最佳拟合法，将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给用户。则系统在分配前首先要对可利用空间表从头到尾扫视一遍，然后从中找出一块不小于n 且最接近n 的空闲块进行分配。③最差拟合法，将可利用空间表中不小于n 且是链表中最大的空闲

访问页号为7的页时，内存中存在的页的页号是：3、8、4和5，根据LRU 定义应淘汰的是

块的一部分分配给用户。

7． 当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度( )。

A. 必定快 B. 不一定

C. 在大部分情况下要快 D. 取决于表递增还是递减 【答案】C

【解析】对于有序顺序存储表折半查找的效率较高，但是不是所有情况下都是如此，比如要查找的元素就是第一个时，用顺序查找比它就快的多了。这类情况外折半都高于顺序查找。

8． 下列有关总线定时的叙述中，错误的是( )。

A. 异步通信方式中，全互锁协议最慢 B. 异步通信方式中，非互锁协议的可靠性最差 C. 同步通信方式中，同步时钟信号可由多设备提供 D. 半同步通信方式中，握手信号的采样由同步时钟控制 【答案】C

【解析】A 项正确，异步通信方式中，全互锁协议最慢，主从模块都需要等待确认后才能撤销其信号；B 项正确，异步通信方式中，非互锁协议没有相互确认机制，因此可靠性最差；C 项错误，同步通信要遵循统一的时钟信号，不能由多设备提供；D 项正确，半同步通信方式中，握手信号的采样由同步时钟控制。

9． 下列有关RAM 和ROM 的叙述中，正确的是( )。

I.RAM 是易失性存储器，ROM 是非易失性存储器 II.RAM 和ROM 都采用随机存取方式进行信息访问 III.RAM 和ROM 都可用作Cache IV .RAM 和ROM 都需要进行刷新 A. 仅I 和II B. 仅II 和III C. 仅 I 、II 和IV D. 仅II 、III 和IV 【答案】A

RAM 中的内容断电后即丢失ROM 中的内容断电后不会丢失，，【解析】(易失性)(非易失性)，区别在同时RAM 和ROM 都采用随机存取方式(即CPU 对任何一个存储单元的存取时间相同)于RAM 可读可写，ROM 只读不写。而ROM 显然不可用作Cache , 也不需要刷新，所以III 和IV