2013 年计算机学科专业基础综合全国联考卷

                     

贡献者： xzllxls; addis

1. 一、单项选择题

　　 1~40 小题，每题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项符合要求。

　　 1. 已知两个长度分别为 m 和 n 的升序链表，若将它们合并为一个长度 $m+n$ 的降序链表，则最坏情况下的时间复杂度是：
A. $O(n)$ $\qquad$ B.$O(m \times n)$ $\qquad$ C.$O(min(m,n))$ $\qquad$ D.$O(max(m,n))$

　　 2. 一个栈的入栈序列为 $1,2,3,,n$，其出栈序列是 $p_1, p_2, p_3, ...$。若 $p_2=3$，则 $p_3$ 可能取值的个数是：
A. $n-3$ $\qquad$ B.$n-2$ $\qquad$ C.$n-1$ $\qquad$ D.无法确定

　　 3.若将关键字 1，2，3，4，5，6，7 依次插入到初始为空的平衡二叉树 $T$ 中，则 $T$ 中平衡因子为 0 的分支结点的个数是
A. 0 $\qquad$ B. 1 $\qquad$ C. 2 $\qquad$ D. 3

　　 4.已知三叉树 $T$ 中 6 个叶结点的权分别是 2，3，4，5，6，7，$T$ 的带权（外部）路径长度最小是
A. 27 $\qquad$ B. 46 $\qquad$ C. 54 $\qquad$ D. 56

　　 5.若 $X$ 是后序线索二叉树中的叶结点，且 $X$ 存在左兄弟结点 $Y$，则 $X$ 的右线索指向的是
A.$X$ 的父结点
B. 以 $Y$ 为根的子树的最左下结点
C.$X$ 的左兄弟结点 $Y$
D.以 $Y$ 为根的子树的最右下结点

　　 6.在任意一棵非空二叉排序树 $T_1$ 中，删除某结点 $v$ 之后形成二叉排序树 $T_2$，再将 $v$ 插入 $T_2$ 形成二叉排序树 $T_3$。下列关于 $T_1$ 与 $T_3$ 的叙述中，正确的是
I.若 $v$ 是 $T_1$ 的叶结点，则 $T_1$ 与 $T_3$ 不同
II. 若 $v$ 是 $T_1$ 的叶结点，则 $T_1$ 与 $T_3$ 相同
III.若 $v$ 不是 $T_1$ 的叶结点，则 $T_1$ 与 $T_3$ 不同
IV. 若 $v$ 不是 $T_1$ 的叶结点，则 $T_1$ 与 $T_3$ 相同
A. 仅 I、III $\qquad$ B. 仅 I、IV $\qquad$ C. 仅 II、III $\qquad$ D. 仅 II、IV

　　 7.设图的邻接矩阵 $A$ 如下所示。各顶点的度依次是

A. 1，2，1，2 $\qquad$ B. 2，2，1，1 $\qquad$ C. 3，4，2，3 $\qquad$ D. 4，4，2，2

　　 8.若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是

　　 A. h，c，a，b，d，e，g，f $\qquad$ B. e，a，f，g，b，h，c，d
C. d，b，c，a，h，e，f，g $\qquad$ D. a，b，c，d，h，e，f，g

　　 9.下列 AOE 网表示一项包含 8 个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是

　　 A.c 和 e $\qquad$ B.d 和 e $\qquad$ C.f 和 d $\qquad$ 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 $\qquad$ B. 007，110，119，114，911，122，120
C. 007，110，911，114，119，120，122 $\qquad$ D. 110，120，911，122，114，007，119

　　 12. 某计算机主频为 1.2GHz，其指令分为 4 类，它们在基准程序中所占比例及 CPI 如下表所示。

　　 该机的 MIPS 数是
A.100 $\qquad$ B.200 $\qquad$ C.400 $\qquad$ D.600

　　 13. 某数采用 IEEE 754 单精度浮点数格式表示为 C640 0000H，则该数的值是
A. $-1.5\times2^{13}$ $\qquad$ B.$-1.5\times2^{12}$ $\qquad$ C. $-0.5\times2^{13}$ $\qquad$ D.$-0.5\times2^{12}$

　　 14. 某字长为 $8$ 位的计算机中，已知整型变量 $x$、$y$ 的机器数分别为 $[x]_\text{补}=1 \quad 1110100$，$[y]_\text{补}=1 \quad 0110000$。若整型变量 $z=2*x+y/2$，则 $z$ 的机器数为
A. 1 1000000 $\qquad$ B. 0 0100100 $\qquad$ C. 1 0101010 $\qquad$ D. 溢出

　　 15. 用海明码对长度为 $8$ 位的数据进行检/纠错时，若能纠正一位错。则校验位数至少为
A. 2 $\qquad$ B. 3 $\qquad$ C. 4 $\qquad$ D. 5

　　 16.某计算机主存地址空间大小为 256MB，按字节编址。虚拟地址空间大小为 4GB，采用页式存储管理，页面大小为 4KB，TLB（快表）采用全相联映射，有 4 个页表项，内容如下表所示。

　　 则对虚拟地址 03FF F180H 进行虚实地址变换的结果是
A. 015 3180H $\qquad$ B. 003 5180H $\qquad$ C. TLB 缺失 $\qquad$ D. 缺页

　　 17.假设变址寄存器 R 的内容为 1000H，指令中的形式地址为 2000H；地址 1000H 中的内容为 2000H，地址 2000H 中的内容为 3000H，地址 3000H 中的内容为 4000H，则变址寻址方式下访问到的操作数是
A. 1000H $\qquad$ B. 2000H $\qquad$ C. 3000H $\qquad$ D. 4000H

　　 18.某 CPU 主频为 1.03GHz，采用 4 级指令流水线，每个流水段的执行需要 1 个时钟周期。假定 CPU 执行了 100 条指令，在其执行过程中，没有发生任何流水线阻塞，此时流水线的吞吐率为
A. 0.25×109 条指令/秒 $\qquad$ B. 0.97×109 条指令/秒
C. 1.0×109 条指令/秒 $\qquad$ D. 1.03×109 条指令/秒

　　 19.下列选项中，用于设备和设备控制器（I/O 接口）之间互连的接口标准是
A. PCI $\qquad$ B. USB $\qquad$ C. AGP $\qquad$ D. PCI-Express

　　 20.下列选项中，用于提高 RAID 可靠性的措施有
I. 磁盘镜像 $\qquad$ II. 条带化 $\qquad$ III. 奇偶校验 $\qquad$ IV. 增加 Cache 机制
A.仅 I、II $\qquad$ B. 仅 I、III $\qquad$ C. 仅 I、III 和 IV $\qquad$ D. 仅 II、III 和 IV

　　 21.某磁盘的转速为 10000 转/分，平均寻道时间是 6ms，磁盘传输速率是 20MB/s，磁盘控制器延迟为 0.2ms，读取一个 4 KB 的扇区所需的平均时间约为
A. 9 ms $\qquad$ B. 9.4 ms $\qquad$ C. 12 ms $\qquad$ 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. 删除此文件所在的目录 $\qquad$ B. 删除与此文件关联的目录项
C. 删除与此文件对应的文件控制块 $\qquad$ D. 释放与此文件关联的内存级冲区

　　 24.为支持 CD-ROM 中视频文件的快速随机播放，播放性能最好的文件数据块组织方式是
A. 连续结构 $\qquad$ B. 链式结构 $\qquad$ C. 直接索引结构 $\qquad$ D. 多级索引结钩

　　 25.用户程序发出磁盘 I/O 请求后，系统的处理流程是：用户程序→系统调用处理程序→设备骆动程序→中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序是
A. 用户程序 $\qquad$ B. 系统调用处理程序
C. 设备驱动程序 $\qquad$ D. 中断处理程序

　　 26.若某文件系统索引结点（inode）中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是：
A. 索引结点的总数 $\qquad$ B. 间接地址索引的级数
C. 地址项的个数 $\qquad$ D. 文件块大小

　　 27 设系统缓冲区和用户工作区均采用单缓冲，从外设读入 1 个数据块到系统缓冲区的时间为 100，从系统缓冲区读入 1 个数据块到用户工作区的时间为 5，对用户工作区中的 1 个数据块进行分析的时间为 90（如下图所示）。进程从外设读入并分析 2 个数据块的最短时间是

　　 A. 200 $\qquad$ B. 295 $\qquad$ C. 300 $\qquad$ D .390

　　 28.下列选项中，会导致用户进程从用户态切换到内核态的操作是
I. 整数除以零 $\qquad$ II. sin（）函数调用 $\qquad$ III. read 系统调用
A. 仅 I、II $\qquad$ B. 仅 I、III $\qquad$ C. 仅 II、III $\qquad$ D. I、II 和 III

　　 29.计算机开机后，操作系统最终被加载到
A. BIOS $\qquad$ B. ROM $\qquad$ C. EPROM $\qquad$ D. RAM

　　 30. 若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的操作是
I. 处理越界错 $\qquad$ II. 置换页 $\qquad$ III. 分配内存
A. 仅 I、II $\qquad$ B. 仅 II、III $\qquad$ C. 仅 I、III $\qquad$ D. I、II 和 III

　　 31. 某系统正在执行三个进程 P1、P2 和 P3，各进程的计算（CPU）时间和 I/O 时间比例如下表所示。

　　 为提高系统资源利用率，合理的进程优先级设置应为
A. P1>P2>P3 $\qquad$ B. P3>P2>P1 $\qquad$ C. P2>P1=P3 $\qquad$ D. P1>P2=P3

　　 32. 下列关于银行家算法的叙述中，正确的是
A.银行家算法可以预防死锁
B.当系统处于安全状态时，系统中一定无死锁进程
C.当系统处于不安全状态时，系统中一定会出现死锁进程
D.银行家算法破坏了死锁必要条件中的 “请求和保持” 条件

　　 33.在 OSI 参考摸型中，下列功能需由应用层的相邻层实现的是
A.对话管理 $\qquad$ B. 数据格式转换 $\qquad$ C. 路由选择 $\qquad$ D. 可靠数据传输

　　 34.若下图为 10 BaseT 网卡接收到的信号波形，则该网卡收到的比特串是

　　 A.0011 0110 $\qquad$ B. 1010 1101 $\qquad$ C. 0101 0010 $\qquad$ D. 1100 0101

　　 35.主机甲通过 1 个路由器（存储转发方式）与主机乙互联，两段链路的数据传输速率均为 10Mbps，主机甲分别采用报文交换和分组大小为 10kb 的分组交换向主机乙发送 1 个大小为 8Mb（$1$M=$10^6$）的报文。.若忽略链路传播延迟、分组头开销和分组拆装时间，则两种交换方式完成该报文传输所需的总时间分别为
A.800 ms、1 600 ms $\qquad$ B. 801 ms、1 600 ms $\qquad$ C. 1 600 ms、800 ms $\qquad$ D. 1 600 ms、801 ms

　　 36.下列介质访问控制方法中，可能发生冲突的是
A.CDMA $\qquad$ B. CSMA $\qquad$ C. TDMA $\qquad$ D. FDMA

　　 37.HDLC 协议对 01111100 01111110 组帧后对应的比特串为
A.01111100 00111110 10 $\qquad$ B. 01111100 01111101 01111110
C. 01111100 01111101 0 $\qquad$ D. 01111100 01111110 01111101

　　 38.对于 100Mbps 的以太网交换机，当输出端口无排队，以直通交换（cut-through switching）方式转发一个以太网帧（不包括前导码）时，引入的转发延迟至少是
A.0 μs $\qquad$ B. 0.48 μs $\qquad$ C. 5.12 μs $\qquad$ D. 121.44 μs

　　 39.主机甲与主机乙之间已建立一个 TCP 连接，双方持续有数据传输，且数据无差错与丢失。若甲收到 1 个来自乙的 TCP 段，该段的序号为 1913、确认序号为 2046、有效载荷为 100 字节，则甲立即发送给乙的 TCP 段的序号和确认序号分别是
A.2046、2012 $\qquad$ B. 2046、2013 $\qquad$ C. 2047、2012 $\qquad$ D. 2047、2013

　　 40.下列关于 SMTP 协议的叙述中，正确的是
I.只支持传输 7 比特 ASCII 码内容
II.支持在邮件服务器之间发送邮件
III.支持从用户代理向邮件服务器发送邮件
IV.支持从邮件服务器向用户代理发送邮件
A.仅 I、II 和 III $\qquad$ B. 仅 I、II 和 IV
C. 仅 I、III 和 IV $\qquad$ D. 仅 II、III 和 IV

2. 二 综合应用题

　　 41~47 小题，共 70 分。

　　 41.（13 分）已知一个整数序列 $A=(a_0, a_1,...,a_{n-1})$，其中 $0 \leq a_i< n(0 \leq i < n)$。若存在 $a_{p1}=a_{p2}=...=a_{pm}=x$ 且 $m>n/2(0 \leq p_k < n, 1 \leq k \leq m)$，则称 x 为 A 的主元素。例如 $A=(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。假定为该机设计了条件转移指令，其格式如下：

　　 其中，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 的值又是多少？请给出计算过程。

　　 （3）实现 “无符号数比较小于等于时转移” 功能的指令中，C、Z 和 N 应各是什么？
（4）以下是该指令对应的数据通路示意图，要求给出图中部件①~③的名称或功能说明。

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

cobegin 
参观者进程 i： 
{ 
...
进门；
...
参观；
...
出门；
...
}
coend

请添加必要的信号量和 P、V（或 wait（）、signal（））操作，以实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。

　　 46.（8 分）某计算机主存按字节编址，逻辑地址和物理地址都是 32 位，页表项大小为 4 字节。请回答下列问题。
(1) 若使用一级页表的分页存储管理方式，逻辑地址结构为：

　　 则页的大小是多少字节？页表最大占用多少字节？
(2) 若使用二级页表的分页存储管理方式，逻辑地址结构为：

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

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

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

　　 （2）若 R2 收到一个目的 IP 地址为 194.17.20.200 的 IP 分组，R2 会通过哪个接口转发该 IP 分组？
（3）R1 与 R2 之间利用哪个路由协议交换路由信息？该路由协议的报文被封装到哪个协议的分组中进行传输？

3. 计算机学科专业基础综合试题参考答案及解析

一、单项选择题

　　 1.D
解析：$m$、$n$ 是两个升序链表，长度分别为 $m$ 和 $n$。在合并过程中，最坏的情况是两个链表中的元素依次进行比较，比较的次数最少是 $m$ 和 $n$ 中的最小值。

　　 2.C
解析：除了 $3$ 本身以外，其他的值均可以取到，因此可能取值的个数为 $n-1$。

　　 3.D
解析：利用 7 个关键字构建平衡二叉树 T，平衡因子为 0 的分支结点个数为 3，构建的平衡二叉树如下图所示。

　　 4.B
解析：利用三叉树的 6 个叶子结点的权构建最小带权生成树，最小的带权路径长度为
$(2+3) \times 3 + (4+5) \times 2 + (6+7) \times 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 \times 0.5 + 3 \times 0.2 + 4 \times 0.1 + 5 \times 0.2 = 3$, 计算机的主频为 $1.2GHa$，为 $1200MHz$，该机器的是 $MIPS$ 为 $1 200/3=400$。

　　 13.A
解析：IEEE 754 单精度浮点数格式为 C640 0000H，二进制格式为 1100 0110 0100 0000 0000 0000 0000 0000，转换为标准的格式为：

　　 因此，浮点数的值为 $-1.5 \times 2^{13}$。

　　 14.A
解析：将 x 左移一位，y 右移一位，两个数的补码相加的机器数为 1 1000000，答案选择 A。

　　 15.C
解析：设校验位的位数为 $k$，数据位的位数为 $n$，应满足下述关系：$2^k \leq n+k+1$。$n=8$，当 $k=4$ 时，$2^4(=16)>8+4+1(=13)$ 符合要求，校验位至少是 4 位。

　　 16.A
解析：虚拟地址为 03FF F180H，其中页号为 03FFFH，页内地址为 180H，根据题目中给出的页表项可知页标记为 03FFFH 所对应的页框号为 0153H，页框号与页内地址之和即为物理地址 015 3180 H。

　　 17.D
解析：根据变址寻址的主要方法，变址寄存器的内容与形式地址的内容相加之后，得到操作数的实际地址，根据实际地址访问内存，获取操作数 4000H。

　　 18.C
解析：采用 4 级流水执行 100 条指令，在执行过程中共用 $4+(100-1)=103$ 个时钟周期。CPU 的主频是 $1.03GHz$，也就是说每秒钟有 $1.03G$ 个时钟周期。流水线的吞吐率为 $1.03G\times100/103=1.0\times10^9$ 条指令/秒。

　　 19.B
解析：设备和设备控制器之间的接口是 USB 接口，其余选项不符合，答案为 B。

　　 20.B
解析：能够提高 RAID 可靠性的措施主要是对磁盘进行镜像处理和进行奇偶校验。其余选项不符合条件。

　　 21.B
解析：磁盘转速是 $10 000$ 转/分钟，平均转一转的时间是 $6ms$，因此平均查询扇区的时间是 $3ms$，平均寻道时间是 $6ms$，读取 $4KB$ 扇区信息的时间为 $0.2ms$，信息延迟的时间为 $0.2ms$，总时间为 $3+6+0.2+0.2=9.4ms$.

　　 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
解析：不进行分组时，发送一个报文的时延是 $8Mb/10Mb/s=800ms$，在接收端接收此报文件的时延也是 $800ms$，共计 $1600ms$。进行分组后，发送一个报文的时延是 $10kb/10Mb/s=1ms$，接收一个报文的时延也是 $1ms$，但是在发送第二个报文时，第一个报文已经开始接收。共计有 $800$ 个分组，总时间为 $801ms$。

　　 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 码内容。

二、综合应用题

　　 41.【答案要点】
（1）给出算法的基本设计思想：（4 分）
$\qquad$ 算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素 $Num$。然后重新计数，确认 $Num$ 是否是主元素。算法可分为以下两步：
$\qquad$ ①选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数 $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<n; 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; i<n; i++)  // 统计候选主元素的实际出现次数
      {
        if (A[i] == c)
          count++; 
      if (count> n/2)
        return c;                // 确认候选主元素
      else
        return -1;               // 不存在主元素 
      } // for
    } // if
  } // for
}

　　 【（1）、（2）的评分说明】 ① 若考生设计的算法满足题目的功能要求且正确，则（1）、（2）根据所实现算法的效率给分，细则见下表：

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<n; 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 分）

　　 采用二叉排序树的查找方法。（1 分） 查找成功时的平均查找长度=0.15×1+0.35×2+0.35×2+0.15×3=2.0。（2 分） 【（1）、（2）的评分说明】 ①若考生以实际元素表示 “降序排列”，同样给分。 ②若考生正确求出与其查找方法对应的查找成功时的平均查找长度，给 2 分；若计算过程正确，但结果错误，给 1 分。 ③若考生给出其他更高效的查找方法且正确，可参照评分标准给分。

　　 43.【答案要点】
（1）CPU 的时钟周期为：$1/800MHz = 1.25ns$。（1 分）总线的时钟周期为：$1/200MHz = 5ns$。（1 分） 总线带宽为：$4B\times200MHz = 800MB/s$ 或 $4B/5ns = 800MB/s$。（1 分）
（2）Cache 块大小是 $32B$，因此 $Cache$ 缺失时需要一个读突发传送总线事务读取一个主存块。（1 分）
（3）一次读突发传送总线事务包括一次地址传送和 $32B$ 数据传送：用 $1$ 个总线时钟周期传输地址；每隔 $40ns/8 = 5ns$ 启动一个体工作（各进行 1 次存取），第一个体读数据花费 $40ns$，之后数据存取与数据传输重叠；用 $8$ 个总线时钟周期传输数据。读突发传送总线事务时间：$5ns + 40ns + 8\times5ns = 85ns$。（2 分）
（4）BP 的 CPU 执行时间包括 Cache 命中时的指令执行时间和 Cache 缺失时带来的额外开销。命中时的指令执行时间：$100\times4\times1.25ns = 500ns$。（1 分）指令执行过程中 Cache 缺失时的额外开销：$1.2\times100\times5\%\times85ns = 510ns$。BP 的 CPU 执行时间：$500ns + 510ns = 1010ns$。（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 分）页表项数为 232/4K=220，该一级页表最大为 220×4 B=4 MB。（2 分）
（2）页目录号可表示为：( ( ( unsigned int ) ( LA ) ) >> 22 ) \& 0x3FF。（1 分） 页表索引可表示为：( ( ( unsigned int ) ( LA ) ) >> 12 ) \& 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 分）

　　 【评分说明】共 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 的路由表如下：

　　 【评分说明】
①每正确解答 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 协议进行通信，亦给分。