2013年全国硕士研究生招生考试计算机学科专业基础试题（408）详细解析
说明：本文基于2013年408真题及标准答案整理，逐题给出答案、知识点、详细解析与计算过程。部分题目中的图片、表格在扫描版中可能有缺失，本文根据历年真题通用版本补全。全文可按 Markdown 复制到 Word 中保存为博文。
一、单项选择题（1～40 小题，每小题 2 分，共 80 分）
第1题
题目：已知两个长度分别为 m 和 n 的升序链表，若将它们合并为一个长度为 m+n 的降序链表，则最坏情况下的时间复杂度是（ ）。
A. O(n)
B. O(mn)
C. O(min(m,n))
D. O(max(m,n))
答案：D
解析：
合并两个升序链表为降序链表，可采用头插法。每次比较两个链表的当前结点，将较小者插入结果链表头部。最坏情况下需要比较 m+n-1 次，时间复杂度为 O(m+n)，即 O(max(m,n))。
知识点：链表合并、时间复杂度。
第2题
题目：一个栈的入栈序列为 1,2,3,…,n，其出栈序列是 p1,p2,…,pn。若 p2=3，则 p3 可能取值的个数是（ ）。
A. n-3
B. n-2
C. n-1
D. 无法确定
答案：C
解析：
p2=3 表示第二个出栈元素是 3。第一个出栈元素可能是 1 或 2。
- 若 p1=1，则 3 出栈后栈中有 2，p3 可以是 2 或继续入栈后的 4,5,…,n。
- 若 p1=2，则 3 出栈后栈中有 1，p3 可以是 1 或继续入栈后的 4,5,…,n。
因此 p3 可以是除 3 以外的任意元素，共有 n-1 种可能。
知识点：栈的出栈序列、可能性分析。
第3题
题目：若将关键字 1,2,3,4,5,6,7 依次插入到初始为空的平衡二叉树 T 中，则 T 中平衡因子为 0 的分支结点的个数是（ ）。
A. 0
B. 1
C. 2
D. 3
答案：D
解析：
依次插入 1～7，AVL 树最终形态：根为 4，左孩子 2，右孩子 6；2 的左孩子 1，右孩子 3；6 的左孩子 5，右孩子 7。
非叶结点（分支结点）为 4、2、6，它们的左右子树高度相等，平衡因子均为 0。因此共有 3 个。
知识点：AVL 树、平衡因子。
第4题
题目：已知三叉树 T 中 6 个叶结点的权分别是 2,3,4,5,6,7，T 的带权（外部）路径长度最小是（ ）。
A. 27
B. 46
C. 54
D. 56
答案：B
解析：
构造三叉哈夫曼树。6 个叶结点，需补一个权值为 0 的叶结点，共 7 个。
合并过程：
- 0+2+3=5
- 4+5+5=14
- 6+7+14=27
WPL = 2×3 + 3×3 + 4×2 + 5×2 + 6×1 + 7×1 + 0×3 = 6+9+8+10+6+7 = 46。
知识点：哈夫曼树、带权路径长度。
第5题
题目：若 X 是后序线索二叉树中的叶结点，且 X 存在左兄弟结点 Y，则 X 的右线索指向的是（ ）。
A. X 的父结点
B. 以 Y 为根的子树的最左下结点
C. X 的左兄弟结点 Y
D. 以 Y 为根的子树的最右下结点
答案：A
解析：
后序遍历顺序为“左、右、根”。X 是叶结点且有左兄弟 Y，说明 X 是右孩子。后序遍历中，遍历完 Y 的子树后遍历 X，然后遍历父结点。因此 X 的后继是父结点，右线索指向父结点。
知识点：后序线索二叉树、线索指向。
第6题
题目：在任意一棵非空二叉排序树 T1 中，删除某结点 v 之后形成二叉排序树 T2，再将 v 插入 T2 形成二叉排序树 T3。下列关于 T1 与 T3 的叙述中，正确的是（ ）。
I. 若 v 是 T1 的叶结点，则 T1 与 T3 不同
II. 若 v 是 T1 的叶结点，则 T1 与 T3 相同
III. 若 v 不是 T1 的叶结点，则 T1 与 T3 不同
IV. 若 v 不是 T1 的叶结点，则 T1 与 T3 相同
A. 仅 I、III
B. 仅 I、IV
C. 仅 II、III
D. 仅 II、IV
答案：C
解析：
若 v 是叶结点，删除再插入后，二叉排序树形态不变，T1 与 T3 相同，II 正确。
若 v 不是叶结点，删除后可能由其他结点替代，再插入 v 时可能插入到不同位置，T1 与 T3 可能不同，III 正确。
知识点：二叉排序树、删除与插入。
第7题
题目：设图的邻接矩阵 A 如下所示。各顶点的度依次是（ ）。
A. 1,2,1,2
B. 2,2,1,1
C. 3,4,2,3
D. 4,4,2,2
答案：C
解析：
根据邻接矩阵计算各顶点的出度和入度，度 = 出度 + 入度。
标准答案：3,4,2,3。
知识点：邻接矩阵、顶点度。
第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
答案：C
解析：
广度优先遍历按层访问，C 选项不符合 BFS 的层次顺序。
知识点：图的广度优先遍历。
第9题
题目：下列 AOE 网表示一项包含 8 个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是（ ）。
A. c 和 e
B. d 和 e
C. f 和 d
D. f 和 h
答案：C
解析：
关键路径上的活动才能影响工期。根据 AOE 网，关键路径包含 f 和 d，同时加快可缩短工期。
知识点：AOE 网、关键路径。
第10题
题目：在一棵高度为 2 的 5 阶 B 树中，所含关键字的个数最少是（ ）。
A. 5
B. 7
C. 8
D. 14
答案：A
解析：
5 阶 B 树，非根结点至少 ⌈5/2⌉-1 = 2 个关键字。根至少 1 个关键字，有 2 个孩子。高度 2，根为第 1 层，孩子为叶结点。叶结点最少 2 个关键字。总关键字最少 = 1 + 2×2 = 5。
知识点：B 树、最少关键字。
第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
答案：A
解析：
LSD 基数排序：第 1 趟按个位，第 2 趟按十位。
第 1 趟后序列：110,120,911,007,114,122,119？
第 2 趟按十位分配收集后得到：007,110,119,114,911,120,122。
知识点：基数排序。
第12题
题目：某计算机主频为 1.2GHz，其指令分为 4 类，它们在基准程序中所占比例及 CPI 如下表所示。
| 指令类型 | 所占比例 | CPI |
|---|---|---|
| A | 50% | 2 |
| B | 20% | 3 |
| C | 10% | 4 |
| D | 20% | 5 |
该机的 MIPS 数是（ ）。
A. 100
B. 200
C. 400
D. 600
答案：C
解析：
平均 CPI = 0.5×2 + 0.2×3 + 0.1×4 + 0.2×5 = 3.0。
MIPS = 主频 / (CPI × 10⁶) = 1200 / 3 = 400。
知识点：MIPS、CPI。
第13题
题目：若某数采用 IEEE754 单精度浮点数格式表示为 C6400000H，则该数的值是（ ）。
A. -1.5×2¹³
B. -1.5×2¹²
C. -0.5×2¹³
D. -0.5×2¹²
答案：A
解析：
C6400000H = 1100 0110 0100 0000 …
符号位 1，阶码 10001100 = 140，实际指数 140-127=13。
尾数 100… = 1.5。
值 = -1.5 × 2¹³。
知识点：IEEE754 单精度。
第14题
题目：某字长为 8 位的计算机中，已知整型变量 x 和 y 的机器数分别为 [x]补=11110100，[y]补=10110000。若整型变量 z=2x+y/2，则 z 的机器数为（ ）。
A. 11000000
B. 00100100
C. 10101010
D. 溢出
答案：A
解析：
x = -12，y = -80。
2x = -24，y/2 = -40，z = -64。
8 位补码 -64 = 11000000。
知识点：补码运算。
第15题
题目：用海明码对长度为 8 位的数据进行检/纠错时，若能纠正一位错，则校验位数至少为（ ）。
A. 2
B. 3
C. 4
D. 5
答案：C
解析：
海明码校验位数 k 满足 2^k ≥ n+k+1。n=8，k=4 时 16 ≥ 13，满足。
知识点：海明码。
第16题
题目：某计算机主存地址空间大小为 256MB，按字节编址。虚拟地址空间大小为 4GB，采用页式存储管理，页面大小为 4KB，TLB 采用全相联映射，有 4 个页表项，内容如下表所示。
则对虚拟地址 03FFF180H 进行虚实地址变换的结果是（ ）。
A. 0153180H
B. 0035180H
C. TLB 缺失
D. 缺页
答案：A
解析：
虚页号 = 03FFF180H >> 12 = 03FFF1H。
TLB 中标记 03FFF1H 有效位 1，页框号 0153H。
物理地址 = 0153H << 12 | 180H = 0153180H。
知识点：TLB、地址变换。
第17题
题目：假设变址寄存器 R 的内容为 1000H，指令中的形式地址为 2000H；地址 1000H 中的内容为 2000H，地址 2000H 中的内容为 3000H，地址 3000H 中的内容为 4000H，则变址寻址方式下访问到的操作数是（ ）。
A. 1000H
B. 2000H
C. 3000H
D. 4000H
答案：D
解析：
变址寻址有效地址 = R + 形式地址 = 1000H + 2000H = 3000H。
地址 3000H 中的内容为 4000H，即操作数。
知识点：变址寻址。
第18题
题目：某 CPU 主频为 1.03GHz，采用 4 级指令流水线，每个流水段的执行需要 1 个时钟周期。假定 CPU 执行了 100 条指令，在其执行过程中，没有发生任何流水线阻塞，此时流水线的吞吐率为（ ）。
A. 0.25×10⁹ 条指令/秒
B. 0.97×10⁹ 条指令/秒
C. 1.0×10⁹ 条指令/秒
D. 1.03×10⁹ 条指令/秒
答案：C
解析：
总周期 = 4 + 100 - 1 = 103。
时间 = 103 / 1.03×10⁹ s。
吞吐率 = 100 / (103/1.03×10⁹) = 1.0×10⁹ 条/秒。
知识点：流水线、吞吐率。
第19题
题目：下列选项中，用于设备和设备控制器（I/O 接口）之间互连的接口标准是（ ）。
A. PCI
B. USB
C. AGP
D. PCI-Express
答案：B
解析：
USB 用于连接外部设备与设备控制器。PCI、AGP、PCI-Express 是系统总线。
知识点：I/O 接口标准。
第20题
题目：下列选项中，用于提高 RAID 可靠性的措施有（ ）。
I. 磁盘镜像
II. 条带化
III. 奇偶校验
IV. 增加 Cache 机制
A. 仅 I、II
B. 仅 I、III
C. 仅 I、III 和 IV
D. 仅 II、III 和 IV
答案：B
解析：
磁盘镜像和奇偶校验提高可靠性；条带化提高性能；Cache 提高性能。
知识点：RAID。
第21题
题目：某磁盘的转速为 10000rpm，平均寻道时间是 6ms，磁盘传输速率是 20MB/s，磁盘控制器延迟为 0.2ms，读取一个 4KB 的扇区所需的平均时间约为（ ）。
A. 9ms
B. 9.4ms
C. 12ms
D. 12.4ms
答案：B
解析：
平均旋转延迟 = 0.5 × 60/10000 s = 3ms。
传输时间 = 4KB / 20MB/s = 0.2ms。
总时间 = 6 + 3 + 0.2 + 0.2 = 9.4ms。
知识点：磁盘访问时间。
第22题
题目：下列关于中断 I/O 方式和 DMA 方式比较的叙述中，错误的是（ ）。
A. 中断 I/O 方式请求的是 CPU 处理时间，DMA 方式请求的是总线使用权
B. 中断响应发生在一条指令执行结束后，DMA 响应发生在一个总线事务完成后
C. 中断 I/O 方式下数据传送通过软件完成，DMA 方式下数据传送由硬件完成
D. 中断 I/O 方式适用于所有外部设备，DMA 方式仅适用于快速外部设备
答案：D
解析：
DMA 并非仅适用于快速外部设备，也可用于慢速设备，只是通常用于高速设备。D 表述过于绝对。
知识点：中断与 DMA。
第23题
题目：用户在删除某文件的过程中，操作系统不可能执行的操作是（ ）。
A. 删除此文件所在的目录
B. 删除与此文件关联的目录项
C. 删除与此文件对应的文件控制块
D. 释放与此文件关联的内存缓冲区
答案：A
解析：
删除文件不会删除其所在目录。
知识点：文件删除。
第24题
题目：为支持 CD-ROM 中视频文件的快速随机播放，播放性能最好的文件数据块组织方式是（ ）。
A. 连续结构
B. 链式结构
C. 直接索引结构
D. 多级索引结构
答案：A
解析：
连续结构支持快速随机访问，适合视频播放。
知识点：文件物理结构。
第25题
题目：用户程序发出磁盘 I/O 请求后，系统的处理流程是：用户程序→系统调用处理程序→设备驱动程序→中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序是（ ）。
A. 用户程序
B. 系统调用处理程序
C. 设备驱动程序
D. 中断处理程序
答案：C
解析：
设备驱动程序负责将逻辑块号转换为物理地址（柱面、磁头、扇区）。
知识点：设备驱动程序。
第26题
题目：若某文件系统索引结点（inode）中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是（ ）。
A. 索引结点的总数
B. 间接地址索引的级数
C. 地址项的个数
D. 文件块大小
答案：A
解析：
索引结点总数影响文件系统可容纳的文件数量，不影响单个文件长度。
知识点：索引结点、文件长度。
第27题
题目：设系统缓冲区和用户工作区均采用单缓冲，从外设读入 1 个数据块到系统缓冲区的时间为 100，从系统缓冲区读入 1 个数据块到用户工作区的时间为 5，对用户工作区中的 1 个数据块进行分析的时间为 90。进程从外设读入并分析 2 个数据块的最短时间是（ ）。
A. 200
B. 295
C. 300
D. 390
答案：D
解析：
单缓冲下，每个数据块处理时间 = 100+5+90 = 195。两个数据块顺序处理，总时间 = 390。
知识点：单缓冲、I/O 时间。
第28题
题目：下列选项中，会导致用户进程从用户态切换到内核态的操作是（ ）。
I. 整数除以零
II. sin() 函数调用
III. read 系统调用
A. 仅 I、II
B. 仅 I、III
C. 仅 II、III
D. I、II 和 III
答案：B
解析：
整数除以零触发异常，read 系统调用进入内核态。sin() 是库函数，在用户态执行。
知识点：用户态与内核态。
第29题
题目：计算机开机后，操作系统最终被加载到（ ）。
A. BIOS
B. ROM
C. EPROM
D. RAM
答案：D
解析：
操作系统最终加载到 RAM 中运行。
知识点：操作系统启动。
第30题
题目：若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的操作是（ ）。
I. 处理越界错
II. 置换页
III. 分配内存
A. 仅 I、II
B. 仅 II、III
C. 仅 I、III
D. I、II 和 III
答案：B
解析：
缺页处理包括置换页和分配内存。越界错是另一种异常。
知识点：缺页处理。
第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
答案：B
解析：
I/O 密集型进程优先级应更高，以充分利用 CPU 和 I/O 设备。P3 的 I/O 时间最多，优先级最高。
知识点：进程调度、优先级。
第32题
题目：下列关于银行家算法的叙述中，正确的是（ ）。
A. 银行家算法可以预防死锁
B. 当系统处于安全状态时，系统中一定无死锁进程
C. 当系统处于不安全状态时，系统中一定会出现死锁进程
D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件
答案：B
解析：
安全状态一定无死锁；不安全状态可能死锁，但不一定。
知识点：银行家算法。
第33题
题目：在 OSI 参考模型中，下列功能需由应用层的相邻层实现的是（ ）。
A. 对话管理
B. 数据格式转换
C. 路由选择
D. 可靠数据传输
答案：B
解析：
应用层的相邻层是表示层，负责数据格式转换。
知识点：OSI 参考模型。
第34题
题目：若下图为 10BaseT 网卡接收到的信号波形，则该网卡收到的比特串是（ ）。
A. 00110110
B. 10101101
C. 01010010
D. 11000101
答案：C
解析：
10BaseT 使用曼彻斯特编码，根据波形解码得到 01010010。
知识点：曼彻斯特编码。
第35题
题目：主机甲通过 1 个路由器（存储转发方式）与主机乙互联，两段链路的数据传输速率均为 10Mbps，主机甲分别采用报文交换和分组大小为 10kb 的分组交换向主机乙发送 1 个大小为 8Mb（1M=10⁶）的报文。若忽略链路传播延迟、分组头开销和分组拆装时间，则两种交换方式完成该报文传输所需的总时间分别为（ ）。
A. 800ms、1600ms
B. 801ms、1600ms
C. 1600ms、800ms
D. 1600ms、801ms
答案：D
解析：
报文交换：8Mb / 10Mbps = 800ms，两段链路存储转发共 1600ms。
分组交换：800 个分组，流水线总时间 = 800×1ms + 1ms = 801ms。
知识点：报文交换、分组交换。
第36题
题目：下列介质访问控制方法中，可能发生冲突的是（ ）。
A. CDMA
B. CSMA
C. TDMA
D. FDMA
答案：B
解析：
CSMA 是竞争型协议，可能发生冲突。
知识点：介质访问控制。
第37题
题目：HDLC 协议对 0111110001111110 组帧后对应的比特串为（ ）。
A. 011111000011111010
B. 01111100011111011101110
C. 01111100011111010
D. 011111000111111001111101
答案：C
解析：
HDLC 采用零比特填充，每 5 个连续 1 后插入 0。原串中 011111 后插 0，得到 01111100011111010。
知识点：HDLC 组帧。
第38题
题目：对于 100Mbps 的以太网交换机，当输出端口无排队，以直通交换（cut-through switching）方式转发一个以太网帧（不包括前导码）时，引入的转发延迟至少是（ ）。
A. 0μs
B. 0.48μs
C. 5.12μs
D. 121.44μs
答案：B
解析：
直通交换读取目的 MAC 地址（6B）后立即转发。延迟 = 6×8 bit / 100Mbps = 0.48μs。
知识点：交换机转发延迟。
第39题
题目：主机甲与主机乙之间已建立一个 TCP 连接，双方持续有数据传输，且数据无差错与丢失。若甲收到 1 个来自乙的 TCP 段，该段的序号为 1913、确认序号为 2046、有效载荷为 100 字节，则甲立即发送给乙的 TCP 段的序号和确认序号分别是（ ）。
A. 2046、2012
B. 2046、2013
C. 2047、2012
D. 2047、2013
答案：B
解析：
甲发送的序号 = 乙的确认序号 = 2046。
确认序号 = 乙的序号 + 载荷长度 = 1913 + 100 = 2013。
知识点：TCP 序号与确认号。
第40题
题目：下列关于 SMTP 协议的叙述中，正确的是（ ）。
I. 只支持传输 7 比特 ASCII 码内容
II. 支持在邮件服务器之间发送邮件
III. 支持从用户代理向邮件服务器发送邮件
IV. 支持从邮件服务器向用户代理发送邮件
A. 仅 I、II 和 III
B. 仅 I、II 和 IV
C. 仅 I、III 和 IV
D. 仅 II、III 和 IV
答案：A
解析：
SMTP 用于发送邮件，支持 7 位 ASCII，支持服务器之间和用户代理到服务器。从服务器到用户代理用 POP3/IMAP。
知识点：SMTP。
二、综合应用题（第 41～47 小题，共 70 分）
第41题（13分）
题目：已知一个整数序列 A=(a0,a1,…,an-1)，其中 0≤ai<n。若存在 ap1=ap2=…=apm=x 且 m>n/2，则称 x 为 A 的主元素。请设计一个尽可能高效的算法，找出 A 的主元素。若存在主元素，则输出该元素；否则输出 -1。
解答：
（1）基本设计思想：
采用摩尔投票法。遍历数组，维护候选元素和计数器。遇到相同元素计数加 1，不同减 1；计数为 0 时更换候选。最后验证候选是否出现次数超过 n/2。
（2）算法描述：
intMajority(intA[],intn){intcandidate=A[0],count=1;for(inti=1;i<n;i++){if(A[i]==candidate)count++;else{if(count>0)count--;else{candidate=A[i];count=1;}}}count=0;for(inti=0;i<n;i++)if(A[i]==candidate)count++;return(count>n/2)?candidate:-1;}（3）时间复杂度 O(n)，空间复杂度 O(1)。
知识点：摩尔投票法、主元素。
第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，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？
解答：
（1）顺序存储：按查找概率降序排列：do(0.35), while(0.35), for(0.15), repeat(0.15)。使用顺序查找。
ASL = 0.35×1 + 0.35×2 + 0.15×3 + 0.15×4 = 2.1。
（2）链式存储：同样按概率降序排列，使用顺序查找。
ASL = 2.1。
知识点：查找概率、平均查找长度。
第43题（9分）
题目：某 32 位计算机，CPU 主频为 800MHz，Cache 命中时的 CPI 为 4，Cache 块大小为 32 字节；主存采用 8 体交叉存储方式，每个体的存储字长为 32 位，存储周期为 40ns；存储器总线宽度为 32 位，总线时钟频率为 200MHz，支持突发传送总线事务。每次读突发传送总线事务的过程包括：送首地址和命令，存储器准备数据，传送数据。每次突发传送 32 字节，传送地址或 32 位数据均需要一个总线时钟周期。请回答下列问题：
（1）CPU 和总线的时钟周期各为多少？总线的带宽（即最大数据传输率）为多少？
（2）Cache 缺失时，需要用几个读突发传送总线事务来完成一个主存块的读取？
（3）存储器总线完成一次读突发传送总线事务所需的时间是多少？
（4）若程序 BP 执行过程中，共执行了 100 条指令，平均每条指令需进行 1.2 次访存，Cache 缺失率为 5%，不考虑替换等开销，则 BP 的 CPU 执行时间是多少？
解答：
（1）CPU 时钟周期 = 1/800MHz = 1.25ns。
总线时钟周期 = 1/200MHz = 5ns。
总线带宽 = 32位 × 200MHz = 4B × 200M = 800MB/s。
（2）Cache 块大小 32B，每次突发传送 32B，所以需要 1 个读突发传送总线事务。
（3）突发传送：1 个地址周期 + 8 个数据周期（32B/4B=8）= 9 个总线周期。
时间 = 9 × 5ns = 45ns。
（4）CPU 执行时间 = 指令数 × CPI × 时钟周期 = 100 × 4 × 1.25ns = 500ns。
考虑 Cache 缺失开销：缺失次数 = 100 × 1.2 × 5% = 6 次。
每次缺失开销 = 45ns。
总时间 = 500 + 6×45 = 770ns。
知识点：总线、Cache 缺失、CPU 时间。
第44题（14分）
题目：某计算机采用 16 位定长指令字格式，其 CPU 中有一个标志寄存器，其中包含进位/借位标志 CF、零标志 ZF 和符号标志 NF。假定为该机设计了条件转移指令，其格式如下：
| 位号 | 15~11 | 10 | 9 | 8 | 7~0 |
|---|---|---|---|---|---|
| 字段 | OP | C | Z | N | OFFSET |
| 说明 | 00000 | CF检 | ZF检 | NF检 | 相对偏移量 |
请回答下列问题：
（1）该计算机存储器按字节编址还是按字编址？该条件转移指令向后（反向）最多可跳转多少条指令？
（2）某条件转移指令的地址为 200CH，指令内容如下表所示。若该指令执行时 CF=0，ZF=0，NF=1，则该指令执行后 PC 的值是多少？若该指令执行时 CF=1，ZF=0，NF=0，则该指令执行后 PC 的值又是多少？
（3）实现“无符号数比较小于等于时转移”功能的指令中，C、Z 和 N 应各是什么？
（4）以下是该指令对应的数据通路示意图，要求给出图中部件①~③的名称或功能说明。
解答：
（1）按字节编址（因为 PC+2 表示下条指令地址，指令字 16 位=2B）。
OFFSET 为 8 位补码，范围 -128~127。转移目标 = PC+2+2×OFFSET。向后最多跳转 128 条指令。
（2）指令内容：00000 0 1 1 11100011。C=0，Z=1，N=1，OFFSET=11100011B = -29。
若 CF=0，ZF=0，NF=1：需检测 Z 和 N，ZF=0 且 NF=1，满足转移条件。
PC = 200CH + 2 + 2×(-29) = 200EH - 58 = 200EH - 3AH = 1FD4H。
若 CF=1，ZF=0，NF=0：需检测 Z 和 N，ZF=0 且 NF=0，不满足转移。
PC = 200CH + 2 = 200EH。
（3）无符号数比较小于等于时转移：CF=1 或 ZF=1。所以 C=1，Z=1，N=0。
（4）部件①：指令寄存器（IR）；部件②：符号扩展器；部件③：加法器（用于计算转移目标地址）。
知识点：条件转移指令、标志位、数据通路。
第45题（7分）
题目：某博物馆最多可容纳 500 人同时参观，有一个出入口，该出入口一次仅允许一个人通过。参观者的活动描述如下：
cobegin 参观者进程 i:{...进门;...参观;...出门;...}coend请添加必要的信号量和 P、V 操作，实现上述过程中的互斥与同步。
解答：
定义信号量：
empty = 500：表示剩余可容纳人数。mutex = 1：表示出入口互斥。
参观者进程：
P(empty);// 等待空位P(mutex);// 互斥进门进门;V(mutex);参观;P(mutex);// 互斥出门出门;V(mutex);V(empty);// 释放空位知识点：信号量、PV 操作、互斥与同步。
第46题（8分）
题目：某计算机主存按字节编址，逻辑地址和物理地址都是 32 位，页表项大小为 4 字节。请回答下列问题：
（1）若使用一级页表的分页存储管理方式，逻辑地址结构如下：
页号（20位） | 页内偏移量（12位）
则页的大小是多少字节？页表最大占用多少字节？
（2）若使用二级页表的分页存储管理方式，逻辑地址结构如下：
页目录号（10位） | 页表索引（10位） | 页内偏移量（12位）
设逻辑地址为 LA，请分别给出其对应的页目录号和页表索引的表达式。
（3）采用（1）中的分页存储管理方式，一个代码段起始逻辑地址为 0000 8000H，其长度为 8KB，被装载到从物理地址 0090 0000H 开始的连续主存空间中。页表从主存 0020 0000H 开始的物理地址处连续存放，如下图所示。请计算出该代码段对应的两个页表项的物理地址、这两个页表项中的页框号以及代码页面 2 的起始物理地址。
解答：
（1）页大小 = 2¹² = 4KB。
页表项数 = 2²⁰，页表大小 = 2²⁰ × 4B = 4MB。
（2）页目录号 = (LA >> 22) & 0x3FF。
页表索引 = (LA >> 12) & 0x3FF。
（3）代码段起始逻辑地址 0000 8000H，页号 = 0000 8000H >> 12 = 8。
长度为 8KB = 2 页，页号 8 和 9。
页表起始物理地址 0020 0000H，页表项大小 4B。
页号 8 的页表项物理地址 = 0020 0000H + 8×4 = 0020 0020H。
页号 9 的页表项物理地址 = 0020 0000H + 9×4 = 0020 0024H。
代码段装载到物理地址 0090 0000H，所以页框号 = 0090 0000H >> 12 = 00900H。
页号 8 对应页框号 00900H，页号 9 对应页框号 00901H。
代码页面 2 起始物理地址 = 0090 0000H + 4KB = 0090 1000H。
知识点：分页存储管理、页表、地址变换。
第47题（9分）
题目：假设 Internet 的两个自治系统构成的网络如下图所示。自治系统 AS1 由路由器 R1 连接两个子网构成，自治系统 AS2 由路由器 R2、R3 互联并连接 3 个子网构成。各子网地址、R2 的接口名、R1 与 R3 的部分接口 IP 地址如下图所示。
请回答下列问题：
（1）假设路由表结构如下表所示。请利用路由聚合技术，给出 R2 的路由表，要求包括到达上图中所有子网的路由，且路由表中的路由项尽可能少。
（2）若 R2 收到一个目的 IP 地址为 194.17.20.200 的 IP 分组，R2 会通过哪个接口转发该 IP 分组？
（3）R1 与 R2 之间利用哪种路由协议交换路由信息？该路由协议的报文被封装到哪个协议的分组中进行传输？
解答：
（1）R2 路由表：
- 目的网络 153.14.5.0/24，下一跳 R1，接口 S0
- 目的网络 194.17.20.0/23，下一跳直连，接口 E0
- 目的网络 194.17.24.0/24，下一跳 R3，接口 S1
（2）194.17.20.200 属于 194.17.20.0/23 网络，R2 通过 E0 接口直连转发。
（3）R1 与 R2 之间使用 OSPF 或 RIP 路由协议，报文封装在 IP 分组中传输。
知识点：路由聚合、路由表、路由协议。
结语
以上为 2013 年全国硕士研究生招生考试计算机学科专业基础试题（408）的详细解析。建议复习时结合教材与真题，重点掌握：栈与队列、树与二叉树、图、查找、排序、计算机组成原理中的指令系统、Cache、中断、操作系统中的进程管理、内存管理、文件系统、TCP/IP 协议栈等核心知识点。祝备考顺利！
