-计算机学科专业基础考研综合模拟试题及详细解析.doc

计算机科学与技术学科联考
计算机学科专业基础模拟试题
（第一套）

一、单项选择题：第 1～40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中， 只有一个选项最符合试题要求。
1．假设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度为（ ）。
void fun(int n){ int i,j,k;
for(i=1;i<=n;i++) for(j=1;j<=n;j++){
k=1;
while(k<=n) k=5*k;
}
}

A．O(n2log2n) C．O(n2log5n)

B．O(nlog5n) D．O(n3)
2．以下说法正确的是（
）。

Ⅰ．带头结点的循环双链表 L 为空的条件是：L->prior==L&&L->next==L
Ⅱ．线性表的插入和删除总是伴随着大量数据的移动 Ⅲ．只有删除静态链表的尾结点才不需要移动元素 Ⅳ．若线性表采用链式存储结构，要求内存中可用存储单元的地址必须不连续 A．仅Ⅰ B．仅Ⅰ、Ⅱ
C．仅Ⅱ、Ⅲ D．Ⅰ、Ⅱ、Ⅲ和Ⅳ
3．循环队列用数组 A[0….m-1]存放其元素值，已知其头尾指针分别是 front 和 rear（且队 尾指针 rear 指向队尾元素的下一个元素），则当前队列中的元素个数是（ ）。
A．(rear-front+m)%m B．(rear-front+1)%m
C．rear-front-1 D．rear-front 4．下列关于二叉树的叙述中正确的是（ ）。 Ⅰ．对于任何一棵二叉树，叶子结点数都是度为 2 的结点数加 1 Ⅱ．二叉树的左右子树不可以任意地交换

Ⅲ．二叉树只适合使用链式结构存储，不可能用顺序结构存储 Ⅳ．结点按层序编号的二叉树，第 i 个结点的左孩子（假设存在）的编号为 2i A．仅Ⅰ、Ⅱ B．仅Ⅱ
C．仅Ⅱ、Ⅳ D．仅Ⅱ、Ⅲ
5．已知一棵深度为 k 的平衡二叉树，其每个非叶子结点的平衡因子均为 0，则该树共有结 点总数为（ ）。
A．2k-1-1 B．2k-1+1
C．2k-1 D．2k+1
6．根据使用频率为 5 个字符设计的赫夫曼编码不可能是（ ）。 A．000，001，010，011，1 B．0000，0001，001，01，1 C．000，001，01，10，11 D．00，100，101，110，111
7．在具有 n 个顶点的图 G 中，若最小生成树不唯一，则（ ）。 Ⅰ．G 的边数一定大于 n-1
Ⅱ．G 的权值最小的边一定有多条 Ⅲ．G 的最小生成树代价不一定相等
A．仅Ⅰ B．仅Ⅰ、Ⅲ
C．仅Ⅰ、Ⅱ D．仅Ⅲ
8．以下哪些方法可以判断出一个有向图是否有环（ ）。 Ⅰ．深度优先遍历 Ⅱ．求最短路径
Ⅲ．拓扑排序 Ⅳ．求关键路径
A．仅Ⅰ、Ⅲ B．仅Ⅰ、Ⅲ、Ⅳ
C．仅Ⅰ、Ⅱ、Ⅲ D．Ⅰ、Ⅱ、Ⅲ和Ⅳ 9．在一棵二叉排序树上，查找关键字为 35 的结点，依次比较的关键字有可能是（ ）。 A．28，36，18，46，35 B．18，36，28，46，35
C．46，28，18，36，35 D．46，36，18，28，35 10．排序趟数与序列的原始状态无关的排序方法是（ ）。 Ⅰ．直接插入排序 Ⅱ．简单选择排序
Ⅲ．冒泡排序 Ⅳ．基数排序
A．仅Ⅰ、Ⅲ B．仅Ⅰ、Ⅱ、Ⅳ
C．仅Ⅰ、Ⅱ、Ⅲ D．仅Ⅰ、Ⅳ 11．下列关于外部排序说法正确的是（ ）。 A．内存与外设交换信息的时间只是外排序总时间的一小部分 B．外部排序就是在外存上进行排序，无需内存参与 C．败者树是一棵完全二叉树
D．置换-选择排序得到的初始归并段长度一定相等
12．图 1-1 中计算机硬件系统基本组成部件①、②、③、④和⑤的名称分别是（ ）。
A．①控制器、②运算器、③存储器、④输入设备、⑤输出设备

B．①运算器、②控制器、③存储器、④输入设备、⑤输出设备 C．①运算器、②存储器、③控制器、④输入设备、⑤输出设备 D．①运算器、②控制器、③存储器、④输出设备、⑤输入设备

图 1-1 计算机硬件系统基本组成部件

13．已知小写英文字母“a”的 ASCII 码值为 61H，现字母“g”被存放在某个存储单元中， 若采用偶校验（假设最高位作为校验位），则该存储单元中存放的十六进制数是（ ）。
A．167H B．E6H C．67H D．E7H
14．页式存储系统的逻辑地址是由页号和页内地址两部分组成的。假定页面的大小为 4KB， 地址变换过程如图 1-2 所示，图中逻辑地址用十进制数表示。逻辑地址经过变换后，十进制数 物理地址 a 应为（ ）。
A．33220 B．8644 C．4548 D．2500
图 1-2 页式存储系统的逻辑地址变换过程
15．下列关于ROM和RAM的说法中，正确的是（ ）。 Ⅰ．CD-ROM 与EPROM都采用随机存储方式 Ⅱ．SRAM读后不需要刷新，而DRAM读后需要刷新 Ⅲ．Cache可以由ROM或者RAM组成
A．Ⅰ、Ⅱ和Ⅲ B．仅Ⅱ和Ⅲ
C．仅Ⅲ D．仅Ⅱ
16．下列关于 Flash 存储器的说法正确的是（ ）。
A．Flash 存储器属于易失性存储器

B．Flash 存储器不具备写功能
C．Flash 存储器是不可擦除的存储器
D．Flash 存储器同时具有 ROM 和 RAM 的功能
17．某机器采用 16 位单字长指令，采用定长操作码，地址码为 5 位，现已定义 60 条二地 址指令，那么单地址指令最多有（ ）条。
A．4 B．32 C．128 D．256
18．指令（ ）从主存中读出。 A．总是根据程序计数器（PC） B．有时根据 PC，有时根据转移指令 C．根据地址寄存器
D．有时根据 PC，有时根据地址寄存器
19．当有中断源发出请求时，CPU 可执行相应的中断服务程序，以下可以提出中断请求的 是（ ）。
Ⅰ．外部事件 Ⅱ．Cache
Ⅲ．浮点运算下溢 Ⅳ．浮点运算上溢
A．仅Ⅰ、Ⅲ B．仅Ⅱ、Ⅲ、Ⅳ
C．仅Ⅰ、Ⅳ D．仅Ⅰ、Ⅲ、Ⅳ
20．某数码相机内置 128MB 的存储空间，拍摄分辨率设定为 1600×1200 像素，颜色深度 为 24 位，若不采用压缩存储技术，使用内部存储器最多可以存储（ ）张照片。
A．12 B．25
C．13 D．23
21．下面关于 PCI 总线的基描述中，错．误．的有（ ）。 Ⅰ．PCI总线是一个与处理器性能相关的高速外围总线 Ⅱ．PCI总线可对传输信息进行奇偶校验 Ⅲ．PCI设备一定是主设备 Ⅳ．系统中允许有多条PCI总线
A．仅Ⅰ、Ⅱ B．仅Ⅱ、Ⅲ
C．仅Ⅲ和Ⅳ D．仅Ⅰ、Ⅲ 22．下列说法正确的是（ ）。
A．在统一编址方式下，访问主存储器和访问 I/O 设备是通过不同的指令来区分的 B．计算机的外围设备就是指输入和输出设备 C．中断隐指令属于程序控制型指令 D．在中断服务程序中，恢复现场之前需要关中断 23．下列关于分时操作系统和实时操作系统说法错误的是（ ）。 Ⅰ．分时操作系统的时间片固定，那么用户数越多，响应时间越长

Ⅱ．在主存容量为 M 的多用户分时操作系统中，当注册用户数为 N 时，每个用户拥有的 主存空间为 M/N

Ⅲ．对于实时操作系统而言，处理机效率一般不作为其设计目标 Ⅳ．铁路信号系统、门禁系统和股票交易系统都需要实时操作系统支持 A．Ⅰ、Ⅳ B．Ⅱ、Ⅲ
C．只有Ⅱ D．只有Ⅳ
24．以下服务中，能发挥多线程系统的特长的是（ ）。 Ⅰ．利用线程并发地执行矩阵乘法运算
Ⅱ．Web 服务器利用线程请求 HTTP 服务 Ⅲ．键盘驱动程序为每一个正在运行的应用配备一个线程，用来响应相应的键盘输入 Ⅳ．基于 GUI 的 debugger 用不同线程处理用户的输入、计算、跟踪等操作 A．Ⅰ、Ⅲ B．Ⅱ、Ⅲ
C．Ⅰ、Ⅱ、Ⅲ D．Ⅰ、Ⅱ、Ⅳ
25．现在有 3 个同时到达的作业 J1、J2 和 J3，它们的执行时间分别为 T1、T2 和 T3，且 T1 时，唤醒一个阻塞队列进程 Ⅲ．当 S.value≤0 时，唤醒一个就绪队列进程 Ⅳ．只有当 S.value<0 时，唤醒一个就绪队列进程 A．Ⅱ、Ⅲ B．Ⅱ、Ⅲ、Ⅳ
C．Ⅰ、Ⅲ D．Ⅰ、Ⅲ、Ⅳ
27．设有 8 页的逻辑空间，每页有 1024B，它们被映射到 32 块的物理存储区中。那么逻 辑地址的有效位是（ ），物理地址至少是（ ）位。
A．10，12 B．10，15
C．13，15 D．13，12

28．某虚拟存储器的用户编程空间共 32 个页面，每页 1KB，主 存为 16KB。假定某时刻用户页表中已调入主存的页面的虚页号和物 理页号对照表（见表 1-1）。
则与表 1-2 十六进制虚地址对应的物理地址为（ ）。
A．1E5C，2A5C B．1E5C，缺页中断
C．125C，2A5C D．125C，缺页中断 29．假定有一个请求分页存储管理系统，测得系统各相关设备的
利用率如下：CPU 利用率为 10%，磁盘交换区为 99.7%：其他 I/O 设 备为 5%。试问：下面措施中将可能改进 CPU 利用率的是（ ）。
Ⅰ．增大内存的容量 Ⅱ．增大磁盘交换区的容量
表 1-1 页面映射表

虚页号
物理页号
0

1

2

3
5

10

4

7

表 1-2 十六进制虚地址 对应的物理地址

虚地址
物理地址
0A5C

1A5C
（1）
（2）
模拟试题（第一套） 第 5 页（共 32 页）

Ⅲ．减少多道程序的道数 Ⅳ．增加多道程序的道数 Ⅴ．使用更快速的磁盘交换区 Ⅵ．使用更快速的 CPU A．Ⅰ、Ⅱ、Ⅲ、Ⅳ B．Ⅰ、Ⅲ
C．Ⅱ、Ⅲ、Ⅴ D．Ⅱ、Ⅵ 30．下面关于文件系统的说法正确的是（ ）。 A．文件系统负责文件存储空间的管理但不能实现文件名到物理地址的转换 B．在多级目录结构中对文件的访问是通过路径名和用户目录名进行的 C．文件可以被划分成大小相等的若干物理块且物理块大小也可以任意指定 D．逻辑记录是对文件进行存取操作的基本单位 31．一个交叉存放信息的磁盘，信息存放方式如图 1-3 所示。
每个磁道有 8 个扇区，每个扇区 512B，旋转速度为 3000 转/分。 假定磁头已在读取信息的磁道上，0 扇区转到磁头下需要 1/2 转， 且设备对应的控制器不能同时进行输入/输出，在数据从控制器传 送至内存的这段时间内，从磁头下通过的扇区数为 2，问依次读 取一个磁道上所有的扇区的数据到内存平均传输速度为（ ）。

A．57.1KB/s B．67.1KB/s
C．77.1KB/s D．87.1KB/s

图 1-3 磁盘中信息存放方式

32．假设 T 是从磁盘输入一块数据到缓冲区需要的时间，C 是 CPU 对一块数据进行处理 的时间，而 M 是将一块数据从缓冲区传送到用户区的时间。当一用户进程要按顺序访问的方 式处理大量数据时，请问在单缓冲和双缓冲的情况下，系统对一块数据的处理时间分别是
（ ）。
A．max(T,C)+M,max(T,M+C) B．max(T,M+C),max(T,C)+M
C．max(T,M)+C,max(T,M+C) D．max(T,M+C),max(T,M)+C 33．计算机网络可分为通信子网和资源子网，下列属于通信子网的是（ ）。 Ⅰ．网桥 Ⅱ．交换机
Ⅲ．计算机软件 Ⅳ．路由器
A．Ⅰ、Ⅱ、Ⅳ B．Ⅱ、Ⅲ、Ⅳ
C．Ⅰ、Ⅲ、Ⅳ D．Ⅰ、Ⅱ、Ⅲ

34．用 PCM 对语音进行数字化，如果将声音分为 128 个量化级，一个典型的电话通道是
4kHz，那么一路话音需要的数据传输率为（ ）。
A．56kbit/s B．64kbit/s
C．128kbit/s D．1024kbit/s 35．在可靠传输机制中，发送窗口的位置由窗口前沿和后沿的位置共同确定，经过一段时
间，发送窗口的后沿的变化情况可能为（ ）。 Ⅰ．原地不动 Ⅱ．向前移动 Ⅲ．向后移动 A．Ⅰ、Ⅲ B．Ⅰ、Ⅱ
C．Ⅱ、Ⅲ D．都有可能

36．在 IPv6 协议中，一个数据流可以由（ ）进行标识。 A．源地址、目的地址和流名称 B．源地址、目的地址和流标号 C．源地址、端口号和流标号
D．MAC 地址、端口号和流名称
37．假定在一个局域网中计算机 A 发送了 ARP 请求分组，希望找出计算机 B 的硬件地址， 局域网上的所有计算机都能接收到这个广播发送的 ARP 请求分组。这时由（ ）使用 ARP 响应分组进行回应。
A．计算机 A B．计算机 B
C．路由器 D．不一定
38．一个有 50 个路由器的网络，采用基于距离-向量的路由选择算法，路由表的每个表项
长度为 6B，每个路由器都有 3 个邻接路由器，每秒与每个邻接路由器交换 1 次路由表，则每 条链路上由于路由器更新路由信息而耗费的带宽为（ ）。
A．2400bit/s B．3600bit/s
C．4800bit/s D．6000bit/s
39．设某 TCP 的拥塞窗口的慢启动门限值初始为 8（单位为报文段，且最大报文段长度为
1KB），当拥塞窗口上升到 12 时，网络会发生超时。按照以上给出的条件，第 12 次传输时， 拥塞窗口的大小为（ ）。
A．5 B．6 C．7 D．8 40．关于 FTP 的工作过程，下面说法错误的是（ ）。 A．每次数据传输结束后，FTP 服务器同时释放 21 和 20 端口 B．FTP 的数据连接是非持久的
C．FTP 的文件传输需要两条 TCP 连接
D．FTP 协议可以在不同类型的操作系统之间传送文件

参考答案
一、单项选择题
1
C
2
A
3
A
4
B
5
C
6
D
7
A
8
A
9
D
10
B
11
C
12
B
13
D
14
A
15
D
16
D
17
A
18
A
19
C
20
D
21
D
22
D
23
C
24
D
25
B
26
B
27
C
28
D
29
B
30
D
31
A
32
A
33
A
34
A
35
B
36
B
37
D
38
C
39
B
40
A

1．C。
首先抓基本运算语句，即 k=5*k;设其执行时间为 T（n）。对于 j 每循环一次，该语句的执 行次数为 m，有 5m≤n，即 m≤log5n。所以，
n n n n 2 2 2

2．A。
T(n) = åi=1 åj=1 m = måi=1 åj=1 = mn
= n log5 n = O(n log5 n)

Ⅰ：循环双链表为空时头结点体现如图 1-6 所示。 可见当满足 L→prior==L&&L→next==L 时，双链表 为空，并且循环双链表与循环单链表一样，没有空指针
域，所以Ⅰ正确。 Ⅱ：链表也是线性表，链表的插入和删除操作不需
要大量的数据移动，所以Ⅱ错误。


图 1-6 空循环双链表

Ⅲ：静态链表尽管使用的是数组存储方式，但是数据之间是靠指针（游标）相互关联的， 故不管是删除静态链表中的哪一个结点，都不需要移动元素，只需要修改指针即可，所以Ⅲ错误。
Ⅳ：线性表采用链表存储，前驱和后继之间的联系需要依靠由前驱指向后继的指针，而与 前驱和后继在内存中的物理位置无关，因此对于整条链表的存储，不需要划分一块连续的存储 空间；但将链表中结点挨个连续存储在一片空间中也未尝不可。对于线性表的链式存储，连续 或者不连续的存储空间都能满足要求，所以Ⅳ错误。
3．A。
因为是循环队列，所以应该分为 rear>front 和 rearfront 时，队列中元素个数为
rear-front=(rear-front+m)%m
因为 0后结果还是 rear-front+m。

综合（1）、（2）可知，A 选项正确。 知识点总结：循环队列的两大状态和两大操作以及三大重点提醒。
（1）两大状态（数学式子表示） 1）队空状态：q.rear==q.front。 2）队满状态：（q.rear+1）%MAX==q.front。
（2）两大操作
1）元素 x 进队操作（移动队尾指针）。 q.rear=(q.rear+1)%MAX； q.data[q.rear]=x；
2）元素 x 出队操作（移动队头指针）。 q.front=(qu.front+1)%MAX； x=q.data[q.front]；
重点提醒 1：有些教材说循环队列队尾指针指向队尾元素，有些教材说循环队列队尾指针 指向队尾元素的下一个元素。不同的说法可能导致很多题目的答案总是相差 1。所以如果在考 研试卷中碰到，且题目没有说明（不过像考研试卷一般都会说明），一律认为是循环队列队尾 指针指向队尾元素的下一个元素。
重点提醒 2：元素入队时，先移动指针，后存入元素；元素出队时，也是先移动指针，再 取出元素。有些书上可能有不同的顺序，其实本质是一样的，考生只需去适应一种写法，对于
程序设计题目已经足够。对于选择题，则可根据题目描述确定是先存取元素，再移动指针，还 是其他处理顺序。
重点提醒 3：循环队列的队尾指针、队头指针、队中元素个数，知道其中任何两者均可算 出第三者。
4．B。 Ⅰ：Ⅰ的描述只有在非空二叉树的情况下才成立，所以考生在做这种概念题目的时候一定
要先想到这种特殊情况，所以Ⅰ错误。 Ⅱ：二叉树的左右子树是有顺序的，不能随意交换，所以Ⅱ正确。 Ⅲ：一般的二叉树确实不能使用顺序结构存储，但是完全二叉树和满二叉树一般都使用顺
序结构存储，所以Ⅲ错误。 Ⅳ：该结论只对完全二叉树才成立，所以Ⅳ错误。 综上所述，只有Ⅱ正确。
5．C。
每个非叶子结点的平衡因子均为 0，说明了该平衡二叉树为满二叉树，所以结点总数为 2k-1。
总结：（1）设 Nh 表示深度为 h 的平衡二叉树中含有的最少结点数，则
N0=0，N1=1，N2=2， L ，Nh=Nh-1+Nh-2+1
例如，深度为 5 的平衡二叉树中含有最少的结点数为 N5=12。
（2）二叉排序树的查找效率取决于其深度。对于结点个数相同的二叉排序树，平衡二叉树

的深度最小，因此效率最高。
6．D。
赫夫曼树中只有度为 0 或 2 的结点，由 D 选项可以画出对应的二叉树，如图 1-7 所示。

图 1-7 D 选项对应的二叉树

由赫夫曼树的性质可知，树中不应该含度为 1 的结点，因此 D 选项不可能。
7．A。 最小生成树边的权值之和最小，若两棵树同时为最小生成树，那么它们的边的权值之和一
定相等，故Ⅲ错误；既然最小生成树不唯一，并且最小生成树的边都为 n-1 条，说明图 G 的边 数一定会大于 n-1，故Ⅰ正确；最小生成树不唯一，和 G 的权值最小的边的条数没有任何关系， 故Ⅱ错误。
8．A。 有两种方法可以判断有向图中是否有回路。用深度优先遍历的方法，如果从有向图上某个
顶点 v 出发的遍历，在 dfs(v)结束之前出现一条从顶点 j 到 v 的边，由于 j 在生成树上是 v 的子 孙，则图中必定存在包含 v 和 j 的环，因此Ⅰ可以；用拓扑排序的方法，在拓扑排序过程中，每 次要删去一个没有前驱的顶点，如果最后图中所有顶点都被删除，则表示没有环，否则有环， 因此Ⅲ正确。而最短路径和关键路径（建立在无环的 AOE 网的基础之上）都是不可以判断的。
补充：还有一个出题点是间接出题，即若一个有向图中的顶点不能排成一个拓扑序列，则
断定该有向图一定有什么？想必 90%以上的考生都会选择有环，但是没有环这个选项，只有顶 点数目大于 1 的强连通分量这个选项，此时考生必须知道顶点数目大于 1 的强连通分量就表明 有环。
9．D。 可以根据选项画出查找路线上的结点，根据二叉排序树的规定来排除不满足条件的选项。
根据题目选项所得查找路线如图 1-8 所示。

图 1-8 查找路线图

A 选项中 28 的右子树中出现了小于它的 18，不满足二叉排序树规定，排除。 B 选项中 36 的左子树中出现了大于它的 46，不满足二叉排序树规定，排除。 C 选项中 28 的左子树中出现了大于它的 36，不满足二叉排序树规定，排除。
补充：在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度相当于折 半查找的时间复杂度，即 O(log2n)。平衡二叉树的查找效率最高，因为二叉树的查找效率取决
于二叉树的高度，对于结点个数相同的二叉树，平衡二叉树的高度最小。
10．B。
直接插入排序：每趟排序都是插入一个元素，所以排序趟数固定为 n-1（n 为元素数）。 简单选择排序：每趟排序都是选出一个最小（或最大）的元素，所以排序趟数固定为 n-1
（n 为元素数）。
交换类的排序：其趟数和原始序列状态有关，所以冒泡排序与初始序列有关。 基数排序：每趟排序都要进行“分配”和“收集”，排序趟数固定为 d（d 为组成元素的关
键字位数）。
综上所述，Ⅰ、Ⅱ、Ⅳ都是无关的，所以选 B。 11．C。
A：影响外排序时间的主要因素就是内存与外设交换信息的总次数，所以 A 错误。
B：外部排序也是在内存上进行排序，只不过需要分为多步而已，所以 B 错误。 C：从败者树的构建方式可知，败者树是一棵完全二叉树，所以 C 正确。 补充知识点：败者树和堆有什么区别？
解析：外排序中败者树和堆排序的区别在于：
（1）败者树是在双亲结点中记下刚进行完的这场比赛的败者而让胜者去参加更加高一层 的比赛，便可得到一棵败者树。而堆排序可看做一种胜者树，即双亲结点表示其左右孩子中的 胜者。
（2）在败者树中，参加比较的 n 个关键字全部为叶子结点，双亲即为其左、右子女的败者， 败者树中结点总数为 2n-1，加上冠军结点恰好为 2n。而堆是由 n 个关键字组成的完全二叉树， 每个关键字作为树中一个结点，根是 n 个关键字中的胜者，树中结点总数为 n。
D：使用置换-选择排序得到的初始归并段长度不一定相等，从最佳归并树构造赫夫曼树的

过程也可以得到答案，所以 D 错误。

外排序的基本过程： 基于磁盘进行的排序多使用归并排序方法。其排序过程主要分为两个阶段：
（1）建立用于外排序的内存缓冲区。根据它们的大小将输入文件划分为若干段，用某种内 排序方法对各段进行排序。经过排序的段叫做初始归并段。当它们生成后就被写到外存中。
（2）按归并树模式，把（1）生成的初始归并段加以归并，一趟趟扩大归并段和减少归并 段数，直到最后归并成一个大归并段为止。
例如：设有一个包含 4500 个记录的输入文件，现用一台其内存至多可容纳 750 个记录的
计算机对该文件进行排序。输入文件放在磁盘上，磁盘每个页块可容纳 250 个记录，这样全部 记录可存储在 4500/250=18 个块中。输出文件也放在磁盘上，用以存放归并结果。由于内存中 可用于排序的存储区域能容纳 750 个记录，所以内存中恰好能存 3 个块的记录。在外排序一开
始，把 18 块记录每 3 块一组读入内存。利用某种内排序方法进行内排序，形成初始归并段，
再写回外存。总共可得到 6 个初始归并段。然后一趟一趟进行归并排序，如图 1-9 所示。

图 1-9 归并排序

12．B。
图中实线框为 CPU，而 CPU 包含五大部件中的运算器和控制器，排除 C 选项。控制器为 计算机提供工作统一的时钟及其发出各种控制命令来协调计算机的各部件自动地工作，所以控 制器应该与其他四大部件相连，可得①为运算器，②为控制器。最后，根据数据的流向可以判 断，④为输入设备，⑤为输出设备。剩下③为存储器。
13．D。
由于“a”的 ASCII 码值为 61H，而“g”是第 7 个字母，所以可以得到“g”的 ASCII 码 值应为 61H +6=67H=1100111B。现在“g”的 ASCII 码值中有 5 个“1”，按照偶校验的规则， 应该在最高位上添加一个 1，使得“1”的个数为偶数个，最后可得该存储单元中存放的十六进 制数为 E7H（1110 0111）。
14．A。 本题考查的是页式存储系统管理中的地址变换知识。在页式存储系统管理中，逻辑地址除

以页的大小，然后向下取整为页号，取余为页内地址。本题页面的大小为 4KB，逻辑地址 8644 除以 4096，取整为 2，取余为 452。页号为 2，查页表得物理块号为 8。因此，a 的有效地址为 8×4096+452=33220。
15．D。 对于选项Ⅰ：首先，ROM和RAM都是采用随机存取方式。由于EPROM属于ROM，故采
用随机存取方式。而CD-ROM属于光盘，为非随机存储，故Ⅰ错误。 对于选项Ⅱ：SRAM采用双稳态触发器来记忆信息，因此不需要刷新；而DRAM采用电容
存储电荷的原理来存储信息，只能维持很短的时间，因此需要刷新，故Ⅱ错误。 对于选项Ⅲ：Cache需要有信息的输入和输出，而ROM只可读，不可输入，因此不能作
为Cache，故Ⅲ错误。
16．D。
Flash 存储器是一种具有较高存储容量、较低价格、非易失性、可在线擦除与编程的新一 代读写存储器。从基本工作原理上看，Flash 存储器属于 ROM 型存储器，但由于它又可以随时 改写其中的信息，所以从功能上看，它又相当于随机存储器（RAM）。
Flash 存储器与其他存储器的区别总结（见表 1-6）。
表 1-6 Flash 存储器与其他存储器区别

内存类型
非易失性
高密度
可写
Flash 存储器
是
是
是
SRAM
不是
不是
是
DRAM
不是
是
是
ROM
是
是
不是
EPROM
是
是
不是
EEPROM
是
不是
是

17．A。
首先可以计算出操作码字段的长度为 16-5-5=6。所以一共可以定义 26=64 条指令，既然二 地址指令占了 60 条，且是定长操作码，故单地址指令最多可以有 64-60=4 条，所以选 A。
如果此题将条件改为采用不定长操作码，答案又是什么？分析如下： 如果采用不定长（扩展）操作码，每条二地址指令可扩展为 32 条单地址指令，那么单地
址指令最多有 32×4=128 条。
18．A。 指令总是根据程序计数器（PC）从主存中读出（一定记住）。可能考生会想到无条件转移
指令情况，认为不一定总是根据 PC 读出。实际上，正确的执行顺序是这样的，当前指令正在
执行时，其实 PC 已经是下一条指令的地址了，如果遇到了无条件转移指令，则只需要简单地 把跳转的地址覆盖 PC 的内容就可以了，最终的结果还是指令需要根据程序计数器从主存读出。
19．C。 Ⅰ：外部事件是可以提出中断请求的，如可以通过敲击键盘来终止现在正在运行的程序，

这个就可以看做一个中断，所以Ⅰ可以。
Ⅱ：Cache 是属于存储设备，不能提出中断请求，所以Ⅱ不可以。 Ⅲ、Ⅳ：浮点运算下溢，可以当做机器零处理，不需要中断来处理；而浮点运算上溢，必
须中断来做相应的处理，所以Ⅲ不可以，Ⅳ可以。
20．D。
24 位图像是典型的 JPG 图片，RGB 各占 8 位，合计 3B。未经压缩的图片大小=1600×1200×
3B≈5.5MB，128MB/5.5MB=23.3，所以内置的存储空间最多可存储 23 张照片。
21．D。
PCI 总线与 CPU 及时钟频率都无关，故Ⅰ错误；PCI 总线支持即插即用并且可对数据和 地址进行奇偶校验，并且 PCI 总线采用猝发传送方式，故Ⅱ正确；主设备指获得总线控制权 的设备，所以 PCI 设备不一定都是主设备，故Ⅲ错误；系统中肯定允许有多条 PCI 总线，以 此来提升计算机的效率，故Ⅳ正确。
22．D。
A：在统一编址方式下，访问主存储器和访问 I/O 设备是通过不同的地址码来区分的；在 独立编址方式下，访问主存储器和访问 I/O 设备是通过不同的指令来区分的，所以 A 错误。
B：除主机外的硬件装置统称为外围设备或外部设备，包括输入、输出设备和外存储器， 所以 B 错误。
C：中断隐指令并不是一条真正的指令，因此不可能把它预先编入程序中，只能在响应中 断时由硬件直接控制执行，它就好像是隐藏于机器中的指令，只有在响应中断时被执行。中断 隐指令不在指令系统中，不属于程序控制指令，所以 C 错误。
补充：在中断周期中，由中断隐指令自动完成保护断点、寻找中断服务程序入口地址以及
硬件关中断的操作。
D：为了防止在恢复现场过程中又出现新的中断，在恢复现场前需要增加关中断操作，所 以 D 正确。
提醒：请注意区分，保护现场前的关中断由中断隐指令完成，但是恢复现场前的关中断是 由中断服务程序完成。
23．C。 Ⅰ正确。在分时操作系统中，响应时间跟时间片和用户数成正比。
响应时间：从提交第一个请求到产生第一个响应所用时间。在 RR 算法中，用户作业时间 片结束后，就认为产生了第一个响应。
Ⅱ错误。操作系统具有主存的共享性，因此每个用户拥有的主存空间大小是由用户程序的 大小决定的。
Ⅲ正确。实时操作系统要求在安全的情况下对时间的要求较苛刻，为保证系统的工作时效， 牺牲效率也是必然的。
Ⅳ正确。铁路信号系统需要实时调度车辆，延时会出事故；门禁系统需要及时响应用户的 进入请求；股票交易系统需要当前的实时行情，上述应用均要求使用实时操作系统。
综上所述，本题选 C。

24．D。
在多线程操作系统中，通常一个进程中包括多个线程，每个线程都是作为利用 CPU 的基 本单位，是花费最小开销的实体。线程具有下述属性：
（1）轻型实体。线程中的实体基本上不拥有系统资源，只是有一点必不可少的，即能保证 独立运行的资源。它包含了一个线程 ID、一个程序计数器、一个寄存器组和一个堆栈。
（2）独立调度和分派的基本单位。
（3）可并发执行。
（4）共享进程资源。在同一进程中的各个线程，都可以共享该进程所拥有的资源，包括共 享代码段、数据段以及其他的操作系统资源（如打开的文件）等。
多线程最大的优点就是并发执行。在 4 个服务中，只有键盘操作是无法并发执行的，因为 整个系统只有一个键盘，而且键盘输入是人的操作，速度比较慢，完全可以使用一个线程来处 理整个系统的键盘操作，所以选择 D。
25．B。
J1、J2 和 J3 同时在 0 时刻到达，按短作业优先算法，选择 J1 和 J2 执行，则 J1 和 J2 等待 时间为 0。又因为 T1为 T1+T3。 所以平均周转时间为（2T1+T2+T3）/3。
知识点回顾：
周转时间=等待时间+运行时间=结束时间-到达时间
26．B。
提醒：计数型信号量就是记录型信号量，不要被这个搞混了。 Ⅰ正确。当执行 V 操作后，S.value≤0，说明了在执行 V 操作之前 S.value<0（此时 S.value 的绝对值就是阻塞队列中进程的个数），所以阻塞队列必有进程在等到，所以需要唤醒一个阻
塞队列的进程。
Ⅱ错误。由Ⅰ的分析可知，S.value≤0 就会唤醒。因为可能在执行 V 操作前，只有一个进 程在阻塞队列，也就是说 S.value=-1，执行 V 操作后，唤醒该阻塞进程，S.value=0。
Ⅲ和Ⅳ错误。S.value 的值和就绪队列中的进程没有此层关系，所以全错。 综上所述，本题选 B。
27．C。
对于逻辑地址结构，因为 8 页=23 页，所以表示页号的地址有 3 位，又因为每页有 1024B= 210B，所以页内偏移地址有 10 位。因此总共逻辑地址有 13 位。
对于物理地址结构，因为页面的大小和物理块的大小是一样的，所以每个物理块也是 1024B，而内存至少有 32 块物理块，所以内存大小至少是 32×1024B=215B。因此物理地址至少 要 15 位，不然无法访问内存的所有区域。

28．D。
每页 1KB，默认字长为 1B，那么页内地址需要 10 位，则剩下的 6 位为虚页号。计算过程 如表 1-7 所示。
表 1-7 十六进制虚地址及物理地址

十六进制虚地址
0A5C
1A5C
二进制虚地址
0000 1010 0101 1100
0001 1010 0101 1100
二进制虚页号
0000 10
0001 10
二进制物理页号
0001 00
缺页中断
二进制页内地址
10 0101 1100

二进制物理地址
0001 0010 0101 1100

十六进制物理地址
125C

29．B。 Ⅰ正确。增大内存可使每个程序得到更多的页面，能减少缺页率，因而减少换入和换出过
程，可提高 CPU 利用率。 Ⅱ错误。因为系统实际已处于频繁的换入和换出过程中，不是因为磁盘交换区容量不够，
因此增大磁盘交换区的容量无用。
Ⅲ正确。因为从给定的条件中磁盘交换区的利用率为 99.7%，说明系统现在已经处于频繁 的换入和换出过程中，可减少主存中的程序。
Ⅳ错误。系统处于频繁的换入和换出过程中，再增加主存中的用户进程数，只能导致系统 的换入和换出更频繁，使性能更差。
Ⅴ错误。因为系统现在处于频繁的换入和换出过程中，即使采用更快的磁盘交换区，其换 入和换出频率也不会改变，因此没用。
Ⅵ错误。系统处于频繁的换入和换出过程中，CPU 处于空闲状态利用率不高，提高 CPU
的速度无济于事。 综上所述，本题选 B。 30．D。
图 1-10 所示为文件系统模型。可将该模型分为 3 个层次，其最底 层是对象及其属性；中间层是对对象进行操纵和管理的软件集合；最 高层是文件系统提供给用户的接口。
其中对对象操纵和管理的软件集合这个层次，是文件系统的核心 部分。文件系统的功能大多是在这一层实现的，其中包括：对文件存 储空间的管理、对文件目录的管理、用于将文件的逻辑地址转换为物 理地址的机制、对文件读和写的管理以及对文件的共享与保护等功能。

所以 A 选项是错误的。
图 1-10 文件系统模型

在多级目录结构中，