2013年全国硕士研究生入学统一考试计算机科学与技术学科联考(408)

2013 年全国硕 士研究生入学统一考试
计算机科学与技术学科联考计算机学科专业基础综合试题

一、单项选择题：1~40 小题，每小题 2 分， 共 80 分。下列每题给 出的四个选项中，只有一个
选项符合试题要求。
1. 已知两个长度分别为 m 和 n 的升序链表 ，若将它们合并为一个长度为 m+n 的降序链 表，则
最坏情况下的时间复杂度是
A. On () B. O() m ?n C. O(min(m,n)) D. O(max(m,n))
2. 一个栈的 入 栈序列为1,2,3, ,n ，其出栈 序列 是 p , p , p , , p 。若 p ? 3 ，则 p 可能取值
1 2 3 n 2 3
的个数是
A. n ?3 B. n ? 2 C. n ?1 D. 无法确定
3. 若将关键字 1，2，3，4，5，6，7 依次插入到初始为空的平衡二叉树 T 中，则 T 中平 衡因
子为 0 的分支结点的个数是
A. 0 B. 1 C. 2 D. 3
4. 已知三叉树 T 中 6 个叶结点的权分别是 2，3，4，5，6，7，T 的带权 （外部）路径长度最
小是
A. 27 B. 46 C. 54 D. 56
5. 若 X 是后序线索二叉树中的叶结点，且 X 存在左兄弟结点 Y ，则 X 的右线索指向的是
A. X 的父结点 B. 以 Y 为根的子树的最左下结点
C. X 的左兄弟结点 Y D. 以 Y 为根的子树的最右下结点
6. 在任意一棵非空二叉排序树 T 中，删除 某结点 v 之后形成二叉排序树 T ，再将v 插入 T 形
1 2 2
成二叉排序树 T 。下列 关于 T 与 T 的叙述中 ，正确的是
3 1 3
I. 若 v 是 T 的叶结点 ，则 T 与 T 不同
1 1 3
II. 若 v 是 T 的叶结点 ，则 T 与 T 相同
1 1 3
III. 若 v 不是 T 的叶结 点，则 T 与 T 不同
1 1 3
IV. 若 v 不是 T 的叶结 点，则 T 与 T 相同
1 1 3
A. 仅 I 、III B. 仅 I 、IV C. 仅 II 、III D. 仅 II 、IV
7. 设图的邻接矩阵 A 如下所示。各顶点的度依次是
0 1 0 1
??
??
0 0 1 1
??
A ?
??
0 1 0 0
??
1 0 0 0
??
A. 1 ，2，1，2 B. 2 ，2，1，1 C. 3 ，4，2，3 D. 4 ，4，2，2
8. 若对如下无向图进行遍历，则下列选项中， 不 是广度优先遍历序列的是
．
A. h ，c ，a ，b，d，e ，g ，f B. e ，a ，f ，g ，b，h，c ，d
C. d ，b，c ，a ，h，e ，f ，g D. a ，b，c ，d，h，e ，f ，g

a
b e
c d f g
h

9. 下列 AOE 网表示一项包含 8 个活动的工程。通过同时加快若干活动的进度可 以缩短整个工
程的工期。下列选项中，加快其进度就可以缩短工程工期的是
c=9
2 4
g=6
a=3
e=6
d=4
2 4
h=9
b=8
4
2
f=10

A.c 和 e B. d 和 e C. f 和 d D. f 和 h
10. 在一株高度为 2 的 5 阶 B 树中，所含关键 字的 个数最少是
A.5 B. 7 C. 8 D. 14
11. 对给定的关键字序列 110，119，007，911，114，120，122 进行基 数排序，则第 2 趟分配
收集后得到的关键字序列是
A. 007 ，110，119 ，114，911，120，122 B. 007 ，110，119 ，114，911，122，120
C. 007 ，110 ，911，114 ，119，120，122 D. 110，120，911 ，122，114，007，119
12. 某计算机主频为 1.2 GHz ，其指令分为 4 类 ，它们在基准程序中所占比例及 CPI 如下表 所
示。
指令类 型 所占比 例 CPI
A 50% 2
B 20% 3
C 10% 4
D 20% 5

该机的 MIPS 数是
A. 100 B. 200 C. 400 D. 600
13. 某数采用 IEEE 754 单精度浮点数格式表示为 C640 0000H ，则该数的值是

13 12 13 12
A. -1.5 ×2 B. -1.5×2 C. -0.5x ×2 D. -0.5×2
14. 某字长为 8 位 的 计 算 机 中 ， 已 知 整 型 变 量 x 、y 的 机 器 数 分 别 为[x] =1 1110100 ，[y] =1
补 补
0110000 。若整型变量 z=2x+y/2 ，则 z 的机器数为
A. 1 1000000 B. 0 0100100 C. 1 0101010 D. 溢出
15. 用海明码对长度为 8 位的数据进行检/ 纠错时 ，若能纠正一位错。则校 验位数至少为
A. 2 B. 3 C. 4 D. 5
16. 某计算 机主存地址空间大小为 256 MB ， 按字节编址。虚拟地址空间大小为 4 GB ，采 用页
式存储 管理，页面大小为 4 KB ，TLB （快表 ）采用全相联映射，有 4 个页表项，内容如下
表所示。
有效位 标记 页框号 ?
0 FF180H 0002H ?
1 3FFF1H 0035H ?
0 02FF3H 0351H ?
1 03FFFH 0153H ?

则对虚拟地址 03FF F180H 进行虚实地址变换的结果是
A. 015 3180H B. 003 5180H C. TLB 缺失 D. 缺页
17. 假设变址寄存器 R 的内容为 1000H ，指令中的形式地址为 2000 H ；地址 1000H 中的内 容
为 2000H ，地址 2000H 中的内容为 3000H ， 地址 3000 H 中的内容 为 4000H ，则变址寻址
方式下访问到的操作数是
A. 1000H B. 2000H C. 3000H D. 4000 H
18. 某 CPU 主频为 1.03 GHz ，采用 4 级指令流水线，每个流水段的执行需要 1 个时钟周期。
假定 CPU 执行了 100 条指令，在其执行过程中，没有发生任何流水线阻塞，此时 流水线
的吞吐率为
9 9
A. 0.25 ×10 条指 令/ 秒 B. 0.97 ×10 条指令/ 秒
9 9
C. 1.0 ×10 条指令/ 秒 D. 1.03 ×10 条指令/ 秒
19. 下列选项中，用于设备和设备控制器 （I/O 接口 ）之间互连的接口标准是
A. PCI B. USB C. AGP D. PCI-Express
20. 下列选项中，用于提高 RAID 可靠性 的措 施有
I. 磁盘镜像 II. 条带化 III. 奇偶 校验 IV. 增加 Cache 机制
A. 仅 I 、II B. 仅 I 、III C. 仅 I 、III 和 IV D. 仅 II 、III 和 IV
21. 某磁盘的转速为 10 000 转/ 分，平均寻道时间是 6 ms ，磁盘传输速率是 20 MB/s ，磁盘控
制器延迟为 0.2 ms ，读取一个 4 KB 的扇区所 需的平均时间约为
A. 9 ms B. 9.4 ms C. 12 ms D. 12.4 ms
22. 下列关于中断 I/O 方式和 DMA 方式比较的叙述中 ，错误的是
．．
A. 中断 I/O 方式 请求的是 CPU 处理时间，DMA 方式请求的是总线使用权
B. 中断响应发生 在一条指令执行结束后，DMA 响应发生在一个总线事务完成后
C. 中断 I/O 方式 下数据传送通过软件完成，DMA 方式下数据传送由硬件完成

D. 中断 I/O 方式 适用于所有外部设备，DMA 方式仅适用于快速外部设备
23. 用户在 删除某文件的过程中，操作系统不可能执行的操作是
A. 删除 此文件所在的目录 B. 删除与此文件关 联的目录项
C. 删除 与此文件对应的文件控制块 D. 释放与此文件关联的内存级冲区
24. 为支持 CD-ROM 中视频 文件的快速随机播放 ，播放性能最好的文件 数据块组织方式是
A. 连续结构 B. 链式结构 C. 直接索引结构 D. 多级索引结钩
25. 用户程序发出磁 盘 I/O 请求后，系统 的处理 流程是：用户程序→系统 调用处理程序→设备
骆动程序 →中断处理程序。其中，计算数据所在 磁盘的柱面号、磁 头号、扇区号的程序是
A. 用户程序 B. 系统调用处理程序
C. 设备 驱动程序 D. 中断处理程序
26. 若某文件 系统索 引 结点 （inode ）中有直 接地址项和 间接地 址项 ， 则 下列选 项中 ， 与单 个文
件长度 无关的因素是
．．
A. 索引结点的总数 B. 间接地址索引的级数
C. 地址项的个数 D. 文件块大小
27. 设系统缓冲区和用户工作区均采用单缓冲，从外设读 入 1 个数 据块到系统缓冲区的时间为
100，从系统缓冲区读 入 1 个数据块到用户工 作区的时间为 5，对用户工作区中的 1 个数据
块进行 分析的时间为 90（如下图所示） 。进程从外设读入并分析 2 个数据块的最短时间是
90
用户工 作区
5
系统缓 冲区
100
外设

A. 200 B. 295 C. 300 D .390
28. 下列选项中，会导致用户进程从用户态切换到内核态的操作是
I. 整数除以零 II. sin （ ）函数调用 III. read 系统调用
A. 仅 I 、II B. 仅 I 、III C. 仅 II、III D. I 、II 和 III
29. 计算机开机后 ，操作系统最终被加载到
A. BIOS B. ROM C. EPROM D. RAM
30. 若用户进程访问内存时产生缺 页，则下列选项中 ，操作系统可能执行的操作是
I. 处理越界错 II. 置换页 III. 分 配内存
A. 仅 I 、II B. 仅 II 、III C. 仅 I 、III D. I 、II 和 III
31. 某系统 正在执行三个进程 P1 、P2 和 P3 ，各进程的计算（CPU）时间和 I/O 时间比例 如 下
表所示。

进程 计算时 间 I/O 时间
P1 90% 10%
P2 50% 50%
P3 15% 85%

为提高系统资源利用率，合理的进程优先级设置应为
A. P1>P2>P3 B. P3>P2>P1 C. P2>P1=P3 D. P1>P2=P3
32. 下列关于银行家算法的叙述中，正确的是
A. 银 行家算法可以预防死 锁
B. 当系统处于安 全状态时 ，系统中一定无死 锁进程
C. 当系统处于不安全状态时 ，系统中一定会出现死 锁进程
D. 银行家算法破坏了死 锁必要条件中的“请求和保持 ”条件
33. 在 OSI 参考摸型中 ，下列功能需由应用层的相邻层实现的是
A. 对话管理 B. 数据格式转换 C. 路由选择 D. 可靠数据传输
34. 若下图为 10 BaseT 网卡接收到的信号波形，则该网卡收到的比特串是

A. 0011 0110 B. 1010 1101 C. 0101 0010 D. 1100 0101
35. 主机甲通过 1 个路 由器 （存储转发方式）与主机乙互联，两段链路的数据传 输速率均为 10
Mbps ，主机甲分别采用报文交换和分组大小为 10 kb 的分组交换向 主机乙发送 1 个大小为
6
8 Mb （1M=10 ） 的 报 文 。. 若 忽 略 链 路 传 播 延 迟 、 分 组 头 开 销 和 分 组 拆 装 时 间 ， 则 两种交
换方式完成该报文传输所需的总时间分别为
A. 800 ms 、1 600 ms B. 801 ms 、1 600 ms
C. 1 600 ms 、800 ms D. 1 600 ms 、801 ms
36. 下列介质访问控制方法中，可能发生冲突的是
A. CDMA B. CSMA C. TDMA D. FDMA
37. HDLC 协议对 01111100 01111110 组 帧后对 应的比特串为
A. 01111100 00111110 10 B. 01111100 01111101 01111110
C. 01111100 01111101 0 D. 01111100 01111110 01111101
38. 对于 100Mbps 的以太网交换机，当输出端口无排队，以直通交换 （cut-through switching ）
方式转发一个以太网帧 （不包括前导码）时，引 入的转发延迟至少是
A. 0 μs B. 0.48 μs C. 5.12 μs D. 121.44 μs
39. 主机甲与主机乙之间已建立一个 TCP 连 接 ， 双 方 持 续 有 数 据 传 输 ， 且 数 据 无 差 错 与 丢
失。若甲收到 1 个来自乙的 TCP 段，该段的序号为 1913、确认序号为 2046、有效载荷为
100 字节，则甲立即发送给乙的 TCP 段的序 号和确认序号分别是
A. 2046 、2012 B. 2046 、2013 C. 2047 、2012 D. 2047 、2013

40. 下列关于 SMTP 协 议的叙述中，正确的是
I. 只支持传 输 7 比特 ASC II 码内容
II. 支持在邮件服 务器之间发送邮件
III. 支持从用户代 理向邮件服务器发送邮件
IV. 支持从邮件服 务器向用户代理发送邮件
A. 仅 I 、II 和 III B. 仅 I 、II 和 IV
C. 仅 I 、III 和 IV D. 仅 II 、III 和 IV
二、综合应用题：41~47 小题，共 70 分。
41. （ 13 分 ） 已 知 一 个 整 数 序 列 A ? (a ,a , ,a ) ， 其 中 0 ? a ? n(0 ? i ? n) 。 若 存 在
0 1 n ?1 i
a ? a ? ? a ? x 且 m ? n / 2(0 ? p ? n,1 ? k ? m) ，则称 x 为 A 的主 元素 。例如 A=
p12 p pm k
( 0 ， 5，5，3，5，7，5，5 ) ，侧 5 为主元 素 ；又如 A= ( 0，5，5，3，5，1，5，7 ) ， 则
A 中没有主元 素。假 设 A 中的 n 个元素保存在一个一维数组中，请设计一个尽可能高效
的算法，找出 A 的主元素。若存在主元素 ，则输出该元素；否则输出-1。要求：
（1） 给出算法的基本设计思想。
（2） 根据设计思想，采用 C 或 C++ 或 Java 语言描述算法，关 键之处给出注释。
（3） 说明你所设计算法的时间复杂度和空间复杂度。
42. （10 分 ）设包含 4 个数据元素的集合 S={ "do" ，"for" ，" repeat" ，" while"} ，各元素的 查
找概率依次为 ：p1=0.35 ，p2 = 0.15 ，p3=0. 15 ，p4=0.35。将 S 保存在一个长度为 4 的顺序
表中，采用折半查找法，查找成功时的平均查找长度为 2.2。请回答 ：
（1）若采用顺 序存 储结构保存 S， 且要求 平均查找长度更 短 ，则 元素应 如何排列 ？应使 用
何种查找方法 ？ 查找成功时的平均查找长度是多少 ？
（2）若采用链 式存 储结构保存 S， 且要求 平均查找长度更 短，则 元素应如何排列 ？应使 用
何种查找方法 ？ 查找成功时的平均查找长度是多少 ？
43.（9 分） 某 32 位计 算机，CPU 主频为 800MHz ，Cache 命中时的 CPI 为 4，Cache 块大 小为
32 字节 ；主存采用 8 体交叉存储方式，每个体的存储字长为 32 位 、存储周期为 40 ns ；
存储器总线宽度为 32 位，总线时钟频率为 200 MHz ，支持突发传送总线事务。每次读突
发传送总线事务 的过程 包括 ：送首地址 和命令 、存 储器准备数 据、传 送数据。每次突 发传
送 32 字节，传送地址或 32 位数据均需要一个总线时钟周期。请回答下列问题，要求给出
理由或计算过程。
（1）CPU 和总线的时钟周期各为多少 ？总线的带宽 （即最大数据传输率 ）为多少？
（2）Cache 缺失时 ，需要用几个读突发传送总线事务来完成一个主存块的读取 ？
（3）存储器总线完成一次读突发传送总线事务所需的时间是多少 ？
（4）若程 序 BP 执行 过程中，共 执行了 100 条指令， 平均每 条指 令需进行 1.2 次访存，
Cache 缺失率为 5% ， 不考虑替换等开销，则 BP 的 CPU 执行时 间是多少？
44. （14 分 ）某计算机采用 16 位定长指令字 格式 ，其 CPU 中有一 个标志寄存器，其中包含进
位/ 借位标志 CF 、零标志 ZF 和符号标志 NF 。假定为该机设计了条件转移指令，其格式如

下：
15 11 10 9 8 7 0
0 0 0 0 0 C Z N OFFSET


其中，00000 为操作码 OP ；C 、Z 和 N 分别 为 CF 、ZF 和 NF 的对 应检测位，某检 测位为
1 时 表 示 需 检 测 对 应 标 志 ， 需 检 测 的 标 志 位 中 只 要 有 一 个 为 1 就 转 移 ， 否 则 不 转 移 ， 例
如，若 C=1 ，Z=0 ，N=1 ，则需检测 CF 和 NF 的值，当 CF=1 或 NF=1 时发生转移 ；
OFFSET 是 相 对 偏 移 量 ， 用 补 码 表 示 。 转 移 执 行 时 ， 转 移 目 标 地 址 为 （PC ）+2+2 ×
OFFSET ；顺序执行时 ，下条指令地址为 （PC ）+2 。请回答下列问题。
（1 ） 该 计 算 机 存 储 器 按 字 节 编 址 还 是 按 字 编 址 ？ 该 条 件 转 移 指 令 向 后 （反向 ） 最 多 可 跳 转 多
少条指令 ？
（2 ） 某 条 件 转 移 指 令 的 地 址 为 200CH ，指令内容如下图所示，若该指令执行时 CF=0 ，
ZF=0 ，NF=1，则该指 令执行后 PC 的值是多 少 ？若该指令执行时 CF=1，ZF=0 ，NF=0，
则该指令执行后 PC 的 值又是多少？请给出计算过程。
15 11 10 9 8 7 0
0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1


（3）实现 “无符号数比较小于等于时转移 ”功能的指令中，C 、Z 和 N 应各是什么？
（4）以下是该指令对应的数据通路示意图，要求给出图中部件 ①~ ③的名称或功能说明。
①
标志寄 存器
OP C Z N OFFSET
PC
2
加法器
符号扩 展器
②
③
多路选 择器

45. （7 分） 某博物馆最多可容纳 500 人同时参 观 ，有一个出入口，该出 入口一次仅允许一个人
通过。 参观者的活动描述如下 ：
cobegin
参观者进程 i ：

{
?
进门；
?
参观；
?
出门；
?
}
coend
请 添 加必 要的 信号 量和 P 、V （ 或 wait（） 、signal （ ）） 操 作，以 实 现上 述 过 程中 的互斥
与同步。要求写出完整的过程，说明信号量的含义并赋初值。
46. （8 分 ） 某 计 算 机主 存 按 字 节 编 址 ， 逻 辑地 址 和 物 理 地 址 都 是 32 位，页表项大小为 4 字
节。请回答下列问题。
（1）若使用一级页表的分页存储管理方式，逻辑地址结构为 ：
页号（20 位） 页内偏 移量 （12 位）

则页的大小是多少字节 ？页表最大占用多少字节 ？
（2）若使用二级页表的分页存储管理方式，逻辑地址结构为 ：
页目录 号（10 位） 页表索 引（10 位） 页内偏 移量 （12 位）

设逻辑地址为 LA ，请 分别给出其对应的页目录号和页表索引的表达式。
（3）采用 （1）中的分页存储管理方式，一个代码段起始逻辑地址为 0000 8000H ，其长 度
为 8 KB ， 被 装 载 到 从 物 理 地 址 0090 0000H 开 始 的 连 续 主 存 空 间 中 。 页 表 从 主 存
0020 0000H 开始的物 理地址处连续存放，如下图所示 （地址大小自下向上递增 ） 。请
计算出该代码 段对应的 两个页表项的 物理地址 、这两个页表 项中的页 框号以及代码页
面 2 的起始物理地址。
页表
代码页 面 2

物理地 址 3

物理地 址 2 页框 号 2
代码页 面 1
物理地 址 1 页框 号 1
0090 0000H



0020 0000H



47. （9 分 ）假设 Internet 的两个自治系统构成的网络如题 47 图所示，自治系统 ASI 由路 由器
R1 连接 两个子网构成 ；自治系统 AS2 由路 由器 R2 、R3 互联并连 接 3 个子网构成。各子

网地址、R2 的接口名、R1 与 R3 的部分接 口 IP 地址如题 47 图所 示。
AS1
R1
153.14.5.0/25
153.14.5.128/25
153.14.3.2
SO
R2
EO
194.17.20.128/25
153.14.3.2
S1
194.17.24.2
AS2
R3
194.17.20.0/25
194.17.21.0/24

题 47 图 网络拓扑结构
请回答下列问题。
（1 ） 假 设 路 由 表 结 构 如 下 表 所 示 。 请 利 用 路 由 聚 合 技 术 ， 给 出 R2 的路由表，要求包括
到达题 47 图中所有子网的路由，且路由表中的路由项尽可能少。
目的网 络 下一跳 接口

（2） 若 R2 收到一个目的 IP 地址为 194.17.20.200 的 IP 分组，R2 会通过哪个接口转发该
IP 分组？
（3）R1 与 R2 之间利 用哪个路由协议交换路由信息 ？该路由协议的报文被封装到哪个协
议的分组中进行传输 ？ 计 算机学 科专 业基础 综合 试题参 考答 案及解 析
（2013 年）

一、单项选择题
1. D
解析：m 、n 是两个升序链表，长度分别为 m 和 n。在合并过程中，最坏的情况是两个链表
中的元素依次进行比较，比较的次数最少是 m 和 n 中的最小值。
2. C
解析：除了 3 本身以外，其他的值均可以取到，因此可能取值的个数为 n ?1 。
3. D
解析：利用 7 个关键字 构建平衡二叉树 T ，平 衡因子为 0 的分支结点 个数为 3，构建的平衡
二叉树如下图所示。
5
6
2
7
1 4
3

4. B
解析： 利 用 三 叉 树 的 6 个 叶 子 结 点 的 权 构 建 最 小 带 权 生 成 树 ， 最 小 的 带 权 路 径 长 度 为
(2 ?3) ?3 ? (4 ?5) ?2 ? (6 ? 7) ?1 ? 46 。
5. A
解析：根据后续线索二叉树的定义，X 结点 为叶子结点且有左兄弟，那么这个结点为右孩子
结点，利用后续遍历的方式可知 X 结点的后继是其父结点，即其右线索指向的是父结点。
6. C
解析：在一棵二 叉排 序树中删除一个 结点后 再将此结点插 入 到二叉 排序树中，如果 删除的 结
点是叶子结点， 那么在 插 入结点后，后 来的二 叉排序树与删除 结点之 前相同。如果删 除的结
点不是叶子结点，那么再插 入这个结点后，后来的二叉树可能发生变化，不完全相同。
7. C
解析：各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。
8. D
解析：D 选项是深度优先遍历不是广度优先遍历的顺序。
9. C

解析：根 据 AOE 网 的定 义可知，关键路径上的 活动时间同时减少， 可以缩短工期。
10. A
解析：一棵高度 为 2 的 5 阶 B 树，根结点 只有到达 5 个关键字的时候 才能产生分裂，成为
高度为 2 的 B 树。
11. C
解析：基数排 序的第 1 趟排序是按照个位 数 字来排序的，第 2 趟排序是 按然十位数字的大
小进行排序的 ，答案是 C 选项。
12. C
解析：基 准程 序的 CPI ? 2 ?0.5 ?3 ?0.2 ? 4 ?0.1 ?5 ?0.2 ? 3 ， 计算 机 的主 频为 1.2GHa ， 为 1
200MHz ，该机器的是 MIPS 为 1 200/3=400 。
13. A
解析：IEEE 754 单精 度浮点数 格式 为 C640 0000H ，二 进制格 式 为 1100 0110 0100 0000
0000 0000 0000 0000， 转换为标准的格式为：
S 阶码 尾数
1 1000 1100 100 0000 0000 0000 0000 0000

13
因此，浮点数的值为?? 1.5 2 。
14. A
解析： 将 x 左移 一位 ，y 右移 一位 ，两 个数 的 补码 相加 的机 器数为 1 1000000 ， 答案 选 择
A 。
15. C
k
解析： 设校验位的位数为 k ，数据位的位数 为 n，应满足下述关系 ：21 ?nk ? ? 。 n ? 8 ，
4
当 k ? 4 时， 2 ( ?16) ? 8 ? 4 ?1( ?13) 符合要求，校 验位至少是 4 位。
16. A
解析： 虚拟地址为 03FF F180H ，其中页号为 03FFFH ，页内地址为 180H ，根据题目中给出
的页表项可知页标记为 03FFFH 所对应的 页框号为 0153H ，页框号与页内地址之和即为物
理地址 015 3180 H 。
17. D
解析： 根 据 变 址 寻 址 的 主 要 方 法 ， 变 址 寄 存 器 的 内 容 与 形 式 地 址 的 内 容 相 加 之 后 ， 得 到 操
作数的实际地址，根据实际地址访问内存，获取操作数 4000H 。
变址寄 存器 形式地 址
地址 内容
1000 H 2000 H
1000 H 2000 H

2000 H 3000 H
＋
○
3000 H 4000 H


18. C

解析： 采用 4 级 流水 执 行 100 条 指 令 ，在 执 行 过 程 中 共 用 4 ? (100 ?1) ?103 个 时钟 周 期 。
CPU 的主频是 1.03 GHz ， 也 就 是 说 每 秒 钟 有 1.03 G 个时钟周期。流水线的吞吐率为
9
1.03G ? 100/103 ? 1.? 0 10 条指令/ 秒。
19. B
解析： 设备和设备控制 器之间的接口是 USB 接口，其余选项不符合， 答案为 B 。
20. B
解析：能够 提 高 RAID 可靠 性的措 施主 要 是对 磁盘 进行 镜像处 理 和进行 奇偶 校 验。其 余选
项不符合条件。
21. B
解析：磁盘转速是 10 000 转/ 分钟，平均转一转的时间是 6 ms ，因 此平均查询扇区的时间
是 3 ms ，平均寻道时间是 6 ms ，读取 4 KB 扇区信息的时间为 0.2 ms ，信息延迟的时间为
0.2 ms ，总时间为 3+6+0.2+0.2=9.4 ms 。
22. D
解析： 中断处理方式： 在 I/O 设备输入每个数 据的过程中， 由于无需 CPU 干预，因而可使
CPU 与 I/O 设备并行工 作。仅当 输完一个数据时，才需 CPU 花费极 短的时间去做些中断处
理。因此中断申请使 用 的是 CPU 处理时间， 发生的时间是在一条指令执行结束之后 ，数据
是在软件的控制下完成传送。而 DMA 方式与 之不同。DMA 方式： 数据传输的基本单位是
数据块，即在 CPU 与 I/O 设备之间，每次传 送至少一个数据块 ；DMA 方式每次申请的是
总 线 的 使 用 权 ， 所 传 送 的 数 据 是 从 设 备 直 接 送 入 内 存 的 ， 或 者 相 反 ； 仅 在 传 送 一 个 或 多 个
数据块的开始和结束时，才需 CPU 干预，整 块数据的传送是在控制器的控制下完成的。答
案 D 的说法不正确。
23. A
解析： 删 除 文 件 不 需 要 删 除 文 件 所 在 的 目 录 ， 而 文 件 的 关 联 目 录 项 和 文 件 控 制 块 需 要 随 着
文件一同删除，同时释放文件的关联缓冲区。
24. A
解析： 为 了 实 现 快 速 随 机 播 放 ， 要 保 证 最 短 的 查 询 时 间 ， 即 不 能 选 取 链 表 和 索 引 结 构 ， 因
此连续结构最优。
25. C
解析： 计算磁盘号、磁头号和扇区号的工作是由设备驱动程序完成的，答案选 C 。
26. A
解析： 四个选项中，只有 A 选项是与单个文件长度无关的。
27. C
解析： 数据块 1 从 外设到用户工作区的总时间为 105，在这段时间中，数据块 2 没有 进行
操作。在数据块 1 进 行分析处理时，数据块 2 从外设到用户工 作区的总时间为 105，这段
时间是并行的。再加上数据块 2 进行处理的时间 90，总共是 300，答案为 C 。
28. B
解析： 需要在系统内核态执行的操作是整数除零操作和 read 系统 调用函数，答案选 B 。
29. D

解析： 系统开机后，操作系统的程序会被自动加载到内存中的系统区，这段区城是 RAM ，
答案选 D 。
30. B
解析： 用 户 进 程 访 问 内 存 时 缺 页 会 发 生 缺 页 中 断 。 发 生 缺 页 中 断 ， 系 统 地 执 行 的 操 作 可 能
是置换页面或分配内存。系统内没有越界的错误，不会进行越界出错处理。
31. B
解析：为了合理地设置进程优先级，应该将进程的 CPU 利用时间和 I/O 时间做综合考虑，
答案选 B 。
32. B
解 析 ： 银 行 家 算 法 是 避 免 死 锁 的 方 法 。 利 用 银 行 家 算 法 ， 系 统 处 于 安 全 状 态 时 没 有 死 锁 进
程，答案选 B 。
33. B
解析：OSI 参考模型中 ，应用层的相邻层是表示层。表示层是 OSI 七层协议的第六层。表
示 层 的 目 的 是 表 示 出 用 户 看 得 懂 的 数 据 格 式 ， 实 现 与 数 据 表 示 有 关 的 功 能 。 主 要 完 成 数 据
字符集的转换、数据格式化和文本压缩、数据加密、解密等工作。因此答案选 B 。
34. A
解析：根据信号编码的基本规则可知，网卡收到的比特串为 0011 0110 ，答案选 A 。
35. D
解析：不进行分组时，发送 一个报文的时延是 8 Mb/10 Mb/s=800 ms ，在接收端接收此报文
件 的时延也是 800 ms ，共计 1 600 ms 。进行分组后，发送一个报文的时延是 10
kb/10Mb/s=1 ms ，接收一个报文的时延也是 1 ms ，但是在发送第二个报文时，第一个报文
已经开始接收。共计有 800 个分组，总时间为 801 ms 。
36. B
解析：介质 访向控制协议中能够发生冲突的是 CSMA 协议，答案为 B 。
37. A
解析：HDLC 协议对比 特串 进行组帧时，HDLC 数据帧以位模式 0111 1110 标识每一个帧的
开始和结束，因 此在帧数据中凡是出现了 5 个连续的位“1”的时候，就会在 输出的位流中
填充一个“0” 。所以答案为 A 。
38. B
解析： 直 通 交 换 方 式 是 指 以 太 网 交 换 机 可 以 在 各 端 口 间 交 换 数 据 。 它在 输入 端 口 检 测到一
个 数 据 包 时 ， 检 查 该 包 的 包 头 ， 获 取 包 的 目 的 地 址 ， 启 动 内 部 的 动 态 查 找 表 转 换 成 相 应 的
输 出 端 口 ， 在 输入 与 输 出 交 叉 处 接 通 ， 把 数 据 包 直 通 到 相 应 的 端 口 ， 实 现 交 换 功 能 。 通 常
情况下，直通交换方式只检查数据包的包头即前 14 个字节，由于不需要考虑前导码，只需
要检测 目的地址的 6 B ，所以最短的传输延迟是 0.48μs 。
39. B
解析： 若甲收到 1 个来自乙的 TCP 段， 该段的序号 seq=1913、 确认序号 ack = 2046、有效
载荷为 100 字节， 则 甲 立 即 发 送 给 乙 的 TCP 段的序号 seq1=ack=2046 和 确 认 序 号
ack1=seq+100=2013 ， 答案为 B 。

40. A
解析： 根 据 下 图 可 知 ，SMTP 协议支持在邮 件 服 务 器 之 间 发 送 邮 件 ， 也 支 持 从 用 户 代 理 向
邮件服务器发送信息。SMTP 协议只支持传输 7 比特的 ASC II 码内容 。
发送方
发件人
接收方 收件人
邮件服 务器
用户代 理
邮件服 务器 用户代 理
发送
读取
邮件
邮件
SMTP
POP3
SMTP SMTP
POP3 POP3
TCP
客户 服务器 TCP
服务器 客户
连接
连接
发送邮 件 SMTP
SMTP
SMTP
客户
服务器
TCP 连接

二、综合应用题
41. 【答案要点】
（1）给出算法的基本设计思想：（ 4 分）
算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素 Num 。 然
后重新计数 ，确认 Num 是否是主元素。
算法可分为以下两步 ：
① 选取候选的主元素 ：依次扫描所给数组中的每个整数，将第一个遇到的整数 Num 保存
到 c 中，记录 Num 的 出现次数为 1；若遇到的下一个整数仍等于 Num ，则计数加 1，
否则计数减 1；当计数减到 0 时，将遇到的下一个整数保存到 c 中， 计数重新记为 1，
开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。
② 判断 c 中元素 是否是真正的主元素 ：再次扫描该数组，统计 c 中元素出现的次 数，若
大于 n/2 ，则为主元素 ；否则，序列中不存在主元素。
（2）算法实现：（ 7 分 ）
int Majority ( int A[ ], int n )
{
int i, c, count=1; / / c 用来保存候选主元素，count 用来计数
c = A[0]; / / 设置 A[0] 为候 选主元素
for ( i=1; i if ( A[i] = = c )
count++; / / 对 A 中的候选主元素计数
else
if ( count > 0) / / 处理不是候选主元素的情况
count--;
else / / 更换候选主元素，重新计数
{ c = A[i];

count = 1;
}
if ( count>0 )
for ( i=count=0; iif ( A[i] = = c )
count++;
if ( count> n/2 ) return c; / / 确认候选主元素
else return -1; / / 不存在主元素
}
【（ 1）、（ 2）的评分说明】
① 若 考 生 设 计 的 算 法 满 足 题 目 的 功 能 要 求 且 正 确 ， 则 （1 ） 、 （2 ） 根 据 所 实 现 算 法 的 效 率
给分，细则见下表：
时间 空间 （1） （2）
说明
复杂度 复杂度 得分 得分
O ( n ) O ( 1 ) 4 7
O ( n ) O ( n ) 4 6 如采用 计数 排序 思想 ，见 表后 Majority1 程序
O ( nlog n ) 其他 3 6 如采用 其他 排序 的思 想
2
2
≥O ( n ) 其他 3 5 其他方 法

int Majority1 ( int A[ ], int n) / / 采用计数排序思想，时间：O ( n ), 空 间：O ( n )
{
int k, p, max;
p = ( int ) malloc ( sizeof ( int ) n ); / / 申 请辅助 计数 数组
for ( k=0; k < n ; k++ ) p [k] =0; / / 计 数数组 清 0
max = 0 ;
for ( k=0; k{ p[ A[k] ] ++; / / 计 数器+1
if (p[A[k] ] >p [ max ] ) max = A[k]; / / 记 录出现 次数 最多 的元 素
}
if ( p[ max ] > n/2 ) return max;
else return -1;
}
② 若 在 算 法 的 基 本 设 计 思 想 描 述 中 因 文 字 表 达 没 有 非 常 清 晰 反 映 出 算 法 思 路 ， 但 在 算 法
实现中能够清晰看出算法思想且正确的，可参照 ①的标准给分 。
③ 若 算 法 的 基 本 设 计 思 想 描 述 或 算 法 实 现 中 部 分 正 确 ， 可 参 照 ① 中各 种 情 况 的 相 应 给 分
标准酌情给分。
④ 参考答案中只给出了使用 C 语言的版本，使用 C++ 或 Java 语 言的答案视同使用 C 语
言。

（3） 说明算法复杂性：（ 2 分）
参考答案中实现的程序的时间复杂度为 O （n） ，空间复杂度为 O （1） 。
【评分说明 】若 考 生所估计的时间 复杂度 与空间复杂度与 考生所 实现的算法一致 ，可各 给
1 分。
42.【答案要点】
（1） 采用顺序存储结构，数据元素按其查找概率降序排列。 （2 分 ）
采用顺序查找方法。 （1 分）
查找成功时的平均查找长度= 0.35×1+0.35 ×2+0.15 ×3+0.15 ×4=2.1。（ 2 分）
（2）
【答案 一】
采用链式存储结构 ， 数据元素按其查找概率降序排列，构成单链表。 （2 分）
采用顺序查找方法。 （1 分）
查找成功时的平均查找长度=0.35×1+0.35 ×2+0.15 ×3+0.15×4=2.1 。 （2 分）
【答案二 】
采用二 叉链表存储结构，构造 二叉排序树 ，元素存储方式见下图。 （2 分）
repeat
for
while
while do
do 或
for
repeat
二叉排 序 树 2
二叉排 序 树 1

采用二叉排序树的查找方法。 （1 分）
查找成功时的平均查找长度=0.15×1+0.35×2+0.35×2+0.15×3=2.0。 （2 分）
【（ 1）、（ 2）的评分说明】
① 若考生以实际元素表示“降序排列” ，同样给分。
② 若考生正确 求出与 其查找方法对应 的查找 成功时的平均查 找长度 ，给 2 分；若计 算过
程正确，但结果错误，给 1 分。
③ 若考生给出其他更高效的查找方法且正确，可参照评分标准给分。
43. 【答案要点】
（1）CPU 的时钟周期为 ：1/800 MHz = 1.25 ns。（ 1 分）
总线的时钟周期为 ：1/200 MHz = 5 ns。（ 1 分）
总线带宽为 ：4 B ×200 MHz = 800 MB/s 或 4 B/5 ns = 800 MB/s。（ 1 分）
（2）Cache 块大小是 32 B ，因此 Cache 缺失 时需要一个读突发传送总线事务读取一个主存
块。 （1 分）
（3）一次读突发传送总线事务包括一次地址传送和 32 B 数据传送 ：用 1 个总线时钟周期

传输地址；每隔 40 ns/8 = 5 ns 启动一个体工 作（各进行 1 次存取） ，第一个体读数据
花费 40 ns ，之后数据存取与数据传输重叠；用 8 个总线时钟周期 传输数据。读突发
传送总线事务时间：5 ns + 40 ns + 8×5 ns = 85 ns。（ 2 分）
（4）BP 的 CPU 执行 时间包括 Cache 命中时 的指令执行时间和 Cache 缺失时带来的额外开
销。命中时的指令执行时间：100 ×4 ×1.25 ns = 500 ns。（ 1 分）指令执行过程中
Cache 缺失时的额外开 销：1.2×100×5% ×85 ns = 510 ns 。BP 的 CPU 执行时间：
500 ns+510 ns=1 010 ns。（ 2 分）
【评分说明】
① 执行时间采用如下公式计算时，可酌情给分。
执行时间= 指令条数 ×CPI ×时钟周期×命中率+ 访存次数×缺失率×缺失损失
② 计算公式正确但运算结果不正确时，可酌情给分。
44. 【答案要点】
（1）因为指令长度为 16 位，且下条指令地址为 （PC ）+2 ，故编址单位是字节。 （1 分）
偏 移 OFFSET 为 8 位补码，范围为-128~127，故相对于当前条件转 移指令，向后最多
可跳转 127 条指令。 （2 分）
【评分说明】若正确给出 OFFSET 的取值范围 ，则酌情给分。
（2）指令中 C = 0，Z = 1，N = 1，故应根 据 ZF 和 NF 的值来判断 是否转移。当 CF=0 ，
ZF=0 ，NF=1 时，需转 移。 （1 分）已知指令中 偏移量为 1110 0011B=E3H ，符号扩展
后为 FFE3 H ，左移一 位 （乘 2）后为 FFC6 H ，故 PC 的值 （即转移目标地址）为
200CH+2+FFC6H=1FD4H 。 （2 分）当 CF = 1 ，ZF = 0，NF = 0 时不 转移。 （1 分）PC
的值为 ：200CH+2=200EH 。 （1 分）
（3）指令中的 C 、Z 和 N 应分别设置为 C=Z=1 ，N=0 。 （3 分）
（4） 部件 ① ：指 令寄 存器 （ 用于存 放当 前指 令）； 部件② ：移位 寄 存器（ 用于左 移一 位）；
部件 ③：加法器 （地址相加） 。 （3 分）
【评分说明】合理给出部件名称或 功能说明均给分。
45. 【答案要点】
定义两个信号量
Semaphore empty = 500; / / 博物馆可以容纳的最多人数（2 分）
Semaphore mutex = 1; / / 用于出入口资源的控制（2 分）
参观者进程 i;
{
?
P ( empty );
P ( mutex );
进门;
V( mutex );
参观;
P ( mutex );

出门;
V( mutex );
V( empty );
?
}
coend （3 分）
【评分说明】
① 信号量初值给 1 分，说明含义给 1 分，两个信号量的初值和含义共 4 分。
② 对 mutex 的 P 、V 操作正确给 2 分。
③ 对 empty 的 P 、V 操作正确给 1 分。
④ 其他答案，参照 ①~ ③的标准给分。
46. 【答案要点】
（1）因为页内偏移量是 12 位，所以页大小为 4 KB，（ 1 分）
32 20 20
页表项数为 2 /4K=2 ，该一级页表最 大为 2 ×4 B=4 MB 。 （2 分）
（2）页目录号可表示为 ：( ( ( unsigned int ) ( LA ) ) >> 22 ) & 0x3FF 。 （1 分）
页表索引可表示为 ：( ( ( unsigned int ) ( LA ) ) >> 12 ) & 0x3FF 。 （1 分）
【评分说明 】
① 页目录号也可以写成( ( unsigned int ) ( LA ) ) >> 22 ；如果两个 表达式没有对 LA 进行 类型
转换，同样给分。
② 如果用除法和其他开销很大的运算方法，但对基本原理是理解的，同样给分。
③ 参考答案给出的是 C 语言的描述，用其他语言 （包括自然语言） 正确地表述了，同样给
分。
（3）代码页面 1 的逻 辑地址为 0000 8000H ，表明其位于第 8 个页 处，对应页表中的 第 8 个
页表项，所以第 8 个 页 表 项 的 物 理 地 址 = 页表起始地址+8 × 页 表 项 的 字 节 数 = 0020
0000H+8 ×4 = 0020 0020H 。由此可得如下图所示的答案。 （3 分 ）
页表



代码 页 面 2
0090 1000H
00901H
0020 0024H
00900H
0020 0020H
0090 0000H
代码页 面 1






【评分说明】共 5 个 答数。物理地址 1 和物 理地址 2 共 1 分；页框 号 1 和页框号 2 共 1 分 ；
物理地址 3 给 1 分。
47.【答案要点 】

（1）（ 6 分 ） 在 AS1 中，子网 153.14.5.0/25 和子网 153.14.5.128/25 可 以 聚 合 为 子 网
153.14.5.0/24 ；在 AS2 中，子网 194.17.20.0/25 和子网 194.17.21.0/24 可以聚合为子网
194.17.20.0/23 ，但缺少 194.17.20.128/25 ；子网 194.17.20.128/25 单独连接到 R2 的接
口 E0 。
于是可以得到 R2 的路由表如下：
目的网 络 下一跳 接口
153.14.5.0/24 153.14.3.2 S0
194.17.20.0/23 194.17.24.2 S1
194.17.20.128/25 — E0

【评分说明】
① 每正确解答 1 个路 由项，给 2 分，共 6 分，每条路由项正确解答目的网络 IP 地址但无
前缀 长度，给 0.5 分， 正确解答前缀长度给 0.5 分，正确解答下一跳 IP 地址给 0.5 分，
正确解答接口给 0.5 分。
② 路由项解答部分正确或路由项多于 3 条，可酌情给分。
（2）该 IP 分组的目 的 IP 地址 194.17.20.200 与路由表中 194.17.20.0/23 和 194.17.20.128/25
两 个 路 由 表 项 均 匹 配 ， 根 据 最 长 匹 配 原 则 ，R2 将通过 E0 接 口 转 发 该 1P 分组。 （1
分 ）
（3）R1 与 R2 之间 利用 BGP4 （或 BGP ） 交换路由信息；（ 1 分）BGP4 的报文被封装到
TCP 协议段中进行传输 。 （1 分）
【评分说明 】
若考生解答为 EGP 协议，且正确解答 EGP 采用 IP 协议进行通信 ，亦给分。