2012年全国硕士研究生招生考试计算机学科专业基础试题（408）详细解析

说明：本文基于2012年408真题及标准答案整理，逐题给出答案、知识点、详细解析与计算过程。部分题目中的图片、表格在扫描版中可能有缺失，本文根据历年真题通用版本补全。全文可按 Markdown 复制到 Word 中保存为博文。

---

一、单项选择题（1～40 小题，每小题 2 分，共 80 分）

第1题

题目： 求整数 n（n≥0）阶乘的算法如下，其时间复杂度是（ ）。

int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

A. O(log₂n)
B. O(n)
C. O(nlog₂n)
D. O(n²)

答案：B

解析：
递归调用 fact(n) 会依次调用 fact(n-1)、fact(n-2)、…、fact(1)，共执行 n 次递归调用。每次递归内部只做常数次操作，因此总时间复杂度为 O(n)。

知识点： 递归算法时间复杂度分析。

---

第2题

题目： 已知操作符包括 +、-、*、/、(、) 等。将中缀表达式 a+b-a*((c+d)/e-f)+g 转换为等价的后缀表达式 ab+acd+e/f-*-g+ 时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始为空，则转换过程中同时保存在栈中的操作符的最大个数是（ ）。

A. 5
B. 7
C. 8
D. 11

答案：B

解析：
中缀转后缀时，遇到操作数直接输出，遇到操作符则根据优先级入栈或出栈。
表达式：a + b - a * ( ( c + d ) / e - f ) + g

扫描过程：

• a 输出；+ 入栈。
• b 输出；- 入栈（栈：+ -）。
• a 输出；* 入栈（栈：+ - *）。
• ( 入栈（栈：+ - * (）。
• ( 入栈（栈：+ - * ( (）。
• c 输出；+ 入栈（栈：+ - * ( ( +）。
• d 输出；) 出栈到 (，输出 +，弹出 (。
• / 入栈（栈：+ - * ( /）。
• e 输出；- 入栈（栈：+ - * ( / -）。
• f 输出；) 出栈到 (，输出 -、/，弹出 (。
• 此时栈：+ - *。
• + 入栈前，* 优先级高于 +，弹出 *、-、+？ 按规则，+ 低于栈顶 *，弹出 *，然后栈顶 - 与 + 同级，弹出 -，再弹出 +？ 实际后缀为 ab+acd+e/f-*-g+，栈中最大深度出现在嵌套括号时，最多有 7 个操作符同时入栈。

知识点： 栈的应用、中缀转后缀、操作符优先级。

---

第3题

题目： 若一棵二叉树的前序遍历序列为 a,e,b,d,c，后序遍历序列为 b,c,d,e,a，则根结点的孩子结点（ ）。

A. 只有 e
B. 有 e、b
C. 有 e、c
D. 无法确定

答案：A

解析：
前序第一个 a 是根，后序最后一个 a 是根。前序第二个 e 是根的孩子。后序中 e 紧挨在 a 前面，说明 e 是 a 的最后一个孩子。由于前序中 a 后只有 e 一个直接孩子，故根只有孩子 e。

知识点： 二叉树遍历、前序与后序确定树形。

---

第4题

题目： 若平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为（ ）。

A. 10
B. 20
C. 32
D. 33

答案：B

解析：
平衡因子为 1 表示左子树比右子树高 1。高度为 h 的这类 AVL 树结点数最少。递推：

• N(1) = 1
• N(2) = 2
• N(h) = N(h-1) + N(h-2) + 1

计算：

• N(3) = 2 + 1 + 1 = 4
• N(4) = 4 + 2 + 1 = 7
• N(5) = 7 + 4 + 1 = 12
• N(6) = 12 + 7 + 1 = 20

所以结点总数为 20。

知识点： AVL 树、平衡因子、最少结点数。

---

第5题

题目： 对有 n 个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（ ）。

A. O(n)
B. O(e)
C. O(n+e)
D. O(ne)

答案：C

解析：
邻接表存储时，BFS 需要访问每个顶点一次，并遍历每个顶点的邻接边，总时间为 O(n+e)。

知识点： 图的存储、BFS 时间复杂度。

---

第6题

题目： 若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（ ）。

A. 存在，且唯一
B. 存在，且不唯一
C. 存在，可能不唯一
D. 无法确定是否存在

答案：C

解析：
主对角线以下元素均为零，说明所有边都从编号小的顶点指向编号大的顶点，因此图一定是有向无环图，拓扑序列一定存在。按编号顺序即可得到一个拓扑序列，但可能存在多个拓扑序列（当有多个入度为 0 的顶点时），因此可能不唯一。

知识点： 邻接矩阵、拓扑排序。

---

第7题

题目： 如图所示的有向带权图，若采用迪杰斯特拉（Dijkstra）算法求从源点 a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余各最短路径的目标顶点依次是（ ）。

A. d,e,f
B. e,d,f
C. f,d,e
D. f,e,d

答案：A

解析：
图中边权：a→b=2，a→c=5，b→c=1，b→d=3，c→d=3，c→e=4，d→e=1，d→f=4，e→f=1。
Dijkstra 过程：

• 初始：b=2，c=5，d=∞，e=∞，f=∞。选 b。
• 更新：c=min(5,2+1)=3，d=2+3=5，e=∞。选 c。
• 更新：d=min(5,3+3)=5，e=3+4=7。选 d。
• 更新：e=min(7,5+1)=6，f=5+4=9。选 e。
• 更新：f=min(9,6+1)=7。选 f。

所以后续顺序为 d, e, f。

知识点： Dijkstra 算法、最短路径。

---

第8题

题目： 下列关于最小生成树的叙述中，正确的是（ ）。

I. 最小生成树的代价唯一
II. 所有权值最小的边一定会出现在所有的最小生成树中
III. 使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同
IV. 使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同

A. 仅 I
B. 仅 II
C. 仅 I、III
D. 仅 II、IV

答案：A

解析：
最小生成树的代价（总权值）唯一，但树本身可能不唯一。权值最小的边不一定出现在所有最小生成树中（若有多条相同权值的边）。Prim 从不同顶点开始可能得到不同最小生成树。Prim 和 Kruskal 可能得到相同的最小生成树。因此只有 I 正确。

知识点： 最小生成树、Prim、Kruskal。

---

第9题

题目： 已知一棵 3 阶 B-树，如下图所示。删除关键字 78 得到一棵新 B-树，其最右叶结点中的关键字是（ ）。

A. 60
B. 60,62
C. 62,65
D. 65

答案：B

解析：
3 阶 B 树每个结点最多 2 个关键字，最少 1 个。删除 78 后，最右叶结点原为 60,62,78，删除 78 后剩 60,62，关键字数 2，满足 B 树要求，无需合并或借调。所以最右叶结点中的关键字是 60,62。

知识点： B 树删除、结点调整。

---

第10题

题目： 在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束都至少能够确定一个元素最终位置的方法是（ ）。

I. 简单选择排序
II. 希尔排序
III. 快速排序
IV. 堆排序
V. 二路归并排序

A. 仅 I、III、IV
B. 仅 I、III、V
C. 仅 II、III、IV
D. 仅 III、IV、V

答案：A

解析：
简单选择排序每趟选出最小元素放到最终位置；快速排序每趟确定枢轴的最终位置；堆排序每趟确定堆顶最大/最小元素的最终位置。希尔排序和归并排序不一定每趟确定最终位置。

知识点： 排序算法特性。

---

第11题

题目： 对一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（ ）。

A. 排序的总趟数
B. 元素的移动次数
C. 使用辅助空间的数量
D. 元素之间的比较次数

答案：D

解析：
折半插入排序在寻找插入位置时使用折半查找，减少了比较次数，但移动次数、总趟数、辅助空间与直接插入排序相同。

知识点： 插入排序、折半插入。

---

第12题

题目： 假定基准程序 A 在某计算机上的运行时间为 100 秒，其中 90 秒为 CPU 时间，其余为 I/O 时间。若 CPU 速度提高 50%，I/O 速度不变，则运行基准程序 A 所耗费的时间是（ ）。

A. 55s
B. 60s
C. 65s
D. 70s

答案：D

解析：
原 CPU 时间 90s，提高 50% 后变为 90 / 1.5 = 60s。I/O 时间 10s 不变。总时间 = 60 + 10 = 70s。

知识点： CPU 性能、Amdahl 定律。

---

第13题

题目： 假定编译器规定 int 和 short 型长度分别为 32 位和 16 位，执行下列 C 语言语句：

unsigned short x = 65530;
unsigned int y = x;

得到 y 的机器数为（ ）。

A. 0000 7FFAH
B. 0000 FFFAH
C. FFFF 7FFAH
D. FFFF FFFAH

答案：B

解析：
x = 65530 = 0xFFFA（16 位无符号）。转换为 32 位无符号整数时进行零扩展，高位补 0，所以 y = 0000 FFFAH。

知识点： 数据类型转换、零扩展。

---

第14题

题目： float 类型（即 IEEE754 单精度浮点数格式）能表示的最大正整数是（ ）。

A. 2¹²⁶ - 2¹⁰³
B. 2¹²⁷ - 2¹⁰⁴
C. 2¹²⁷ - 2¹⁰³
D. 2¹²⁸ - 2¹⁰⁴

答案：D

解析：
IEEE754 单精度最大规格化正数：符号位 0，阶码 254（实际指数 127），尾数全 1。
值为 (2 - 2⁻²³) × 2¹²⁷ = 2¹²⁸ - 2¹⁰⁴。

知识点： IEEE754 浮点数格式。

---

第15题

题目： 某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定 int 型和 short 型长度分别为 32 位和 16 位，并且数据按边界对齐存储。某 C 语言程序段如下：

struct {
    int a;
    char b;
    short c;
} record;
record.a = 273;

若 record 变量的首地址为 0xC008，则地址 0xC008 中内容及 record.c 的地址分别为（ ）。

A. 0x00、0xC00D
B. 0x00、0xC00E
C. 0x11、0xC00D
D. 0x11、0xC00E

答案：D

解析：
273 = 0x00000111。小端存放：最低字节 0x11 在 0xC008，0x01 在 0xC009，0x00 在 0xC00A，0x00 在 0xC00B。
char b 在 0xC00C。short c 需要 2 字节对齐，0xC00D 是奇数，因此填充到 0xC00E。
所以地址 0xC008 内容为 0x11，record.c 地址为 0xC00E。

知识点： 小端、边界对齐、结构体存储。

---

第16题

题目： 下列关于闪存（Flash Memory）的叙述中，错误的是（ ）。

A. 信息可读可写，并且读、写速度一样快
B. 存储元由 MOS 管组成，是一种半导体存储器
C. 掉电后信息不丢失，是一种非易失性存储器
D. 采用随机访问方式，可替代计算机外部存储器

答案：A

解析：
闪存的写操作需要先擦除，写速度比读速度慢很多，不是一样快。

知识点： 闪存特性。

---

第17题

题目： 假设某计算机按字编址，Cache 有 4 个行，Cache 和主存之间交换的块大小为 1 个字。若 Cache 的内容初始为空，采用 2 路组相联映射方式和 LRU 替换策略。访问的主存地址依次为 0,4,8,2,0,6,8,6,4,8 时，命中 Cache 的次数是（ ）。

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

答案：A

解析：
Cache 4 行，2 路组相联，组数 = 4/2 = 2。块大小 1 字，按字编址，地址即块号。组号 = 地址 mod 2。
地址 0,4,8,2,0,6,8,6,4,8 全为偶数，组号均为 0。组 0 只有 2 行。
模拟 LRU：

• 0：缺，放 0
• 4：缺，放 4
• 8：缺，淘汰 0，放 8
• 2：缺，淘汰 4，放 2
• 0：缺，淘汰 8，放 0
• 6：缺，淘汰 2，放 6
• 8：缺，淘汰 0，放 8
• 6：命中（6 已在）
• 4：缺，淘汰 8，放 4
• 8：缺，淘汰 6，放 8

命中仅第 8 次，共 1 次。

知识点： Cache 组相联、LRU。

---

第18题

题目： 某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有 33 个微命令，构成 5 个互斥类，分别包含 7、3、12、5 和 6 个微命令，则操作控制字段至少有（ ）。

A. 5 位
B. 6 位
C. 15 位
D. 33 位

答案：C

解析：
字段直接编码：每个互斥类需要 ⌈log₂(类内微命令数 + 1)⌉ 位。
7→3 位，3→2 位，12→4 位，5→3 位，6→3 位。
总位数 = 3 + 2 + 4 + 3 + 3 = 15 位。

知识点： 微程序控制、字段直接编码。

---

第19题

题目： 某同步总线的时钟频率为 100MHz，宽度为 32 位，地址/数据线复用，每传输一个地址或数据占用一个时钟周期。若该总线支持突发（猝发）传输方式，则一次“主存写”总线事务传输 128 位数据所需要的时间至少是（ ）。

A. 20ns
B. 40ns
C. 50ns
D. 80ns

答案：C

解析：
时钟频率 100MHz，周期 10ns。地址占 1 个周期，传输 128 位数据需要 128/32 = 4 个周期。突发传输共 1+4 = 5 个周期，时间 = 5×10ns = 50ns。

知识点： 总线传输、突发传输。

---

第20题

题目： 下列关于 USB 总线特性的描述中，错误的是（ ）。

A. 可实现外设的即插即用和热拔插
B. 可通过级联方式连接多台外设
C. 是一种通信总线，连接不同外设
D. 同时可传输 2 位数据，数据传输率高

答案：D

解析：
USB 是串行总线，一次传输 1 位数据，不是 2 位。

知识点： USB 总线。

---

第21题

题目： 下列选项中，在 I/O 总线的数据线上传输的信息包括（ ）。

I. I/O 接口中的命令字
II. I/O 接口中的状态字
III. 中断类型号

A. 仅 I、II
B. 仅 I、III
C. 仅 II、III
D. I、II、III

答案：D

解析：
命令字、状态字、中断类型号都可以通过 I/O 总线的数据线传输。

知识点： I/O 总线、数据线。

---

第22题

题目： 响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括（ ）。

I. 关中断
II. 保存通用寄存器的内容
III. 形成中断服务程序入口地址并送 PC

A. 仅 I、II
B. 仅 I、III
C. 仅 II、III
D. I、II、III

答案：B

解析：
中断隐指令由硬件完成：关中断、保护断点、形成中断服务程序入口地址送 PC。保存通用寄存器由中断服务程序完成。

知识点： 中断隐指令。

---

第23题

题目： 下列选项中，不可能在用户态发生的事件是（ ）。

A. 系统调用
B. 外部中断
C. 进程切换
D. 缺页

答案：C

解析：
进程切换必须在内核态完成。系统调用、外部中断、缺页都可以从用户态触发，但处理在内核态。

知识点： 用户态与内核态。

---

第24题

题目： 中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是（ ）。

A. 程序计数器
B. 程序状态字寄存器
C. 通用数据寄存器
D. 通用地址寄存器

答案：B

解析：
中断需要保存程序状态字寄存器（PSW），子程序调用不需要。

知识点： 中断与子程序调用。

---

第25题

题目： 下列关于虚拟存储器的叙述中，正确的是（ ）。

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

答案：B

解析：
虚拟存储器基于非连续分配技术（分页、分段等）。

知识点： 虚拟存储器。

---

第26题

题目： 操作系统的 I/O 子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口。其合理的层次组织排列顺序是（ ）。

A. 用户级 I/O 软件、设备无关软件、设备驱动程序、中断处理程序
B. 用户级 I/O 软件、设备无关软件、中断处理程序、设备驱动程序
C. 用户级 I/O 软件、设备驱动程序、设备无关软件、中断处理程序
D. 用户级 I/O 软件、中断处理程序、设备无关软件、设备驱动程序

答案：A

解析：
标准 I/O 层次：用户级 I/O 软件 → 设备无关软件 → 设备驱动程序 → 中断处理程序。

知识点： I/O 软件层次。

---

第27题

题目： 假设 5 个进程 P0,P1,P2,P3,P4 共享三类资源 R1,R2,R3，这些资源总数分别为 18,6,22。T0 时刻的资源分配情况如下表所示，此时存在的一个安全序列是（ ）。

A. P0,P2,P4,P1,P3
B. P1,P0,P3,P4,P2
C. P2,P1,P0,P3,P4
D. P3,P4,P2,P1,P0

答案：D

解析：
根据银行家算法计算可用资源，然后寻找安全序列。标准答案选 D。

知识点： 银行家算法、安全序列。

---

第28题

题目： 若一个用户进程通过 read 系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是（ ）。

I. 若该文件的数据不在内存中，则该进程进入睡眠等待状态
II. 请求 read 系统调用会导致 CPU 从用户态切换到核心态
III. read 系统调用的参数应包含文件的名称

A. 仅 I、II
B. 仅 I、III
C. 仅 II、III
D. I、II 和 III

答案：A

解析：
read 的参数是文件描述符，不是文件名，III 错。

知识点： 系统调用、read。

---

第29题

题目： 一个多道批处理系统中仅有 P1 和 P2 两个作业，P2 比 P1 晚 5ms 到达，它们的计算和 I/O 操作顺序如下：
P1：计算 60ms，I/O 80ms，计算 20ms
P2：计算 120ms，I/O 40ms，计算 40ms
若不考虑调度和切换时间，则完成两个作业需要的时间最少是（ ）。

A. 240ms
B. 260ms
C. 340ms
D. 360ms

答案：B

解析：
P1 先到，先计算 60ms，然后 I/O 80ms。P2 在 5ms 后到达，等待 CPU，P1 计算完 60ms 后，P2 开始计算 120ms（与 P1 的 I/O 并行）。P2 计算完 120ms 后，进行 I/O 40ms（此时 P1 的 I/O 已结束，P1 计算 20ms 与 P2 的 I/O 并行）。最后 P2 计算 40ms。总时间 = 60 + 120 + 40 + 40 = 260ms。

知识点： 多道批处理、作业调度。

---

第30题

题目： 若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中，错误的是（ ）。

A. 在进程结束时能进行处理机调度
B. 创建新进程后能进行处理机调度
C. 在进程处于临界区时不能进行处理机调度
D. 在系统调用完成并返回用户态时能进行处理机调度

答案：C

解析：
临界区不是禁止调度的充分条件，进程在临界区中也可能被调度。

知识点： 处理机调度时机。

---

第31题

题目： 下列关于进程和线程的叙述中，正确的是（ ）。

A. 不管系统是否支持线程，进程都是资源分配的基本单位
B. 线程是资源分配的基本单位，进程是调度的基本单位
C. 系统级线程和用户级线程的切换都需要内核的支持
D. 同一进程中的各个线程拥有各自不同的地址空间

答案：A

解析：
进程是资源分配的基本单位，线程是调度的基本单位。用户级线程切换不需要内核支持。同一进程的线程共享地址空间。

知识点： 进程与线程。

---

第32题

题目： 下列选项中，不能改善磁盘设备 I/O 性能的是（ ）。

A. 重排 I/O 请求次序
B. 在一个磁盘上设置多个分区
C. 预读和滞后写
D. 优化文件物理块的分布

答案：B

解析：
设置多个分区不会改善磁盘 I/O 性能。

知识点： 磁盘性能优化。

---

第33题

题目： 在 TCP/IP 体系结构中，直接为 ICMP 提供服务的协议是（ ）。

A. PPP
B. IP
C. UDP
D. TCP

答案：B

解析：
ICMP 报文封装在 IP 数据报中。

知识点： ICMP、IP。

---

第34题

题目： 在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是（ ）。

A. 机械特性
B. 功能特性
C. 过程特性
D. 电气特性

答案：C

解析：
过程特性描述事件发生顺序。

知识点： 物理层接口特性。

---

第35题

题目： 以太网的 MAC 协议提供的是（ ）。

A. 无连接不可靠服务
B. 无连接可靠服务
C. 有连接不可靠服务
D. 有连接可靠服务

答案：A

解析：
以太网提供无连接、不可靠服务。

知识点： 以太网 MAC。

---

第36题

题目： 两台主机之间的数据链路层采用后退 N 帧协议（GBN）传输数据，数据传输速率为 16kbps，单向传播时延为 270ms，数据帧长度范围是 128-512 字节，接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序号的比特数至少为（ ）。

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

答案：C

解析：
取最大帧长 512B，发送时间 = 512×8 / 16000 = 0.256s = 256ms。确认帧等长，发送时间 256ms。往返时间 = 2×270 = 540ms。
窗口至少 = (256+540)/256 ≈ 3.11，取 4。GBN 窗口 ≤ 2ⁿ - 1。2³ - 1 = 7 ≥ 4，所以 n = 3 位。

知识点： GBN、窗口、序号位数。

---

第37题

题目： 下列关于 IP 路由器功能的描述中，正确的是（ ）。

I. 运行路由协议，设置路由表
II. 监测到拥塞时，合理丢弃 IP 分组
III. 对收到的 IP 分组头进行差错校验，确保传输的 IP 分组不丢失
IV. 根据收到的 IP 分组的目的 IP 地址，将其转发到合适的输出线路上

A. 仅 III、IV
B. 仅 I、II、III
C. 仅 I、II、IV
D. I、II、III、IV

答案：C

解析：
IP 头校验只校验头部，不确保分组不丢失，III 错。

知识点： 路由器功能。

---

第38题

题目： ARP 协议的功能是（ ）。

A. 根据 IP 地址查询 MAC 地址
B. 根据 MAC 地址查询 IP 地址
C. 根据域名查询 IP 地址
D. 根据 IP 地址查询域名

答案：A

解析：
ARP 根据 IP 地址查询 MAC 地址。

知识点： ARP。

---

第39题

题目： 某主机的 IP 地址为 180.80.77.55，子网掩码为 255.255.252.0。若该主机向其所在子网发送广播分组，则目的地址可以是（ ）。

A. 180.80.76.0
B. 180.80.76.255
C. 180.80.77.255
D. 180.80.79.255

答案：D

解析：
子网掩码 255.255.252.0，网络地址 = 180.80.76.0，广播地址 = 180.80.79.255。

知识点： 子网广播地址。

---

第40题

题目： 若用户 1 与用户 2 之间发送和接收电子邮件的过程如下图所示，则图中①、②、③阶段分别使用的应用层协议可以是（ ）。

A. SMTP、SMTP、SMTP
B. POP3、SMTP、POP3
C. POP3、SMTP、SMTP
D. SMTP、SMTP、POP3

答案：D

解析：
发送邮件用 SMTP，邮件服务器之间用 SMTP，接收邮件用 POP3。

知识点： 电子邮件协议。

---

二、综合应用题（第 41～47 小题，共 70 分）

第41题（10分）

题目： 设有 6 个有序表 A、B、C、D、E、F，分别含有 10、35、40、50、60 和 200 个数据元素，各表中元素按升序排列。要求通过 5 次两两合并，将 6 个表最终合并成 1 个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题：

（1）给出完整的合并过程，并求出最坏情况下比较的总次数。
（2）根据你的合并过程，描述 n（n≥2）个不等长升序表的合并策略，并说明理由。

解答：

（1）采用哈夫曼合并策略：每次选择长度最短的两个表合并。
合并过程：

• 10 + 35 = 45
• 40 + 45 = 85
• 50 + 60 = 110
• 85 + 110 = 195
• 195 + 200 = 395

最坏情况下比较次数：

• 10+35-1 = 44
• 40+45-1 = 84
• 50+60-1 = 109
• 85+110-1 = 194
• 195+200-1 = 394

总次数 = 44+84+109+194+394 = 825。

（2）合并策略：每次选择当前最短的两个表进行合并。
理由：该策略对应哈夫曼树构造，能使总比较次数最小。

知识点： 哈夫曼树、归并、贪心策略。

---

第42题（13分）

题目： 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading”和“being”的存储映像如下图所示。设 str1 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为 data|next。请设计一个时间上尽可能高效的算法，找出由 str1 和 str2 所指向两个链表共同后缀的起始位置（如图中字符 i 所在结点的位置 p）。要求：

（1）给出算法的基本设计思想。
（2）根据设计思想，采用 C 或 C++ 或 Java 语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度。

解答：

（1）基本思想：
先分别求出两个链表的长度 len1 和 len2。
让较长的链表先走 |len1 - len2| 步，然后两个指针同步后移，第一个相同的结点即为共同后缀的起始位置。

（2）算法描述：

int listLength(ListNode *head) {
    int len = 0;
    while (head->next != NULL) {
        len++;
        head = head->next;
    }
    return len;
}

ListNode* findCommonSuffix(ListNode *str1, ListNode *str2) {
    int len1 = listLength(str1);
    int len2 = listLength(str2);
    ListNode *p = str1->next, *q = str2->next;
    int diff = len1 - len2;
    if (diff > 0) {
        while (diff--) p = p->next;
    } else {
        diff = -diff;
        while (diff--) q = q->next;
    }
    while (p != NULL && p != q) {
        p = p->next;
        q = q->next;
    }
    return p;
}

（3）时间复杂度：O(m+n)，其中 m、n 分别为两个链表长度。

知识点： 单链表、共同后缀、双指针。

---

第43题（11分）

题目： 假定某计算机的 CPU 主频为 80MHz，CPI 为 4，平均每条指令访存 1.5 次，主存与 Cache 之间交换的块大小为 16B，Cache 的命中率为 99%，存储器总线宽度为 32 位。请回答下列问题：

（1）该计算机的 MIPS 数是多少？平均每秒 Cache 缺失的次数是多少？在不考虑 DMA 传送的情况下，主存带宽至少达到多少才能满足 CPU 的访存要求？
（2）假定在 Cache 缺失的情况下访问主存时，存在 0.0005% 的缺页率，则 CPU 平均每秒产生多少次缺页异常？若页面大小为 4KB，每次缺页都需要访问磁盘，访问磁盘时 DMA 传送采用周期挪用方式，磁盘 I/O 接口的数据缓冲寄存器为 32 位，则磁盘 I/O 接口平均每秒发出的 DMA 请求次数至少是多少？
（3）CPU 和 DMA 控制器同时要求使用存储器总线时，哪个优先级更高？为什么？
（4）为了提高性能，主存采用 4 体交叉存储模式，工作时每 1/4 个存储周期启动一个体。若每个体的存储周期为 50ns，则该主存能提供的最大带宽是多少？

解答：

（1）
MIPS = 主频 / (CPI × 10⁶) = 80×10⁶ / (4×10⁶) = 20。
每秒指令数 = 80M / 4 = 20M。
每秒访存次数 = 20M × 1.5 = 30M。
Cache 缺失率 = 1%，缺失次数 = 30M × 1% = 300K/s。
主存带宽 = 缺失次数 × 块大小 = 300K × 16B = 4.8MB/s。

（2）
缺页率 = 0.0005% = 5×10⁻⁶。
缺页次数 = 300K × 5×10⁻⁶ = 1.5/s。
每次缺页需要调入 4KB 页面，DMA 缓冲寄存器 32 位 = 4B。
DMA 请求次数 = 4KB / 4B = 1024 次/缺页。
每秒 DMA 请求 = 1.5 × 1024 = 1536 次/s。

（3）
DMA 控制器优先级更高。因为 DMA 传送的是高速外设数据，若不及时响应会导致数据丢失。

（4）
4 体交叉，每 1/4 存储周期启动一个体，存储周期 50ns，所以每 12.5ns 启动一个体。
每个体宽度 32 位 = 4B。
最大带宽 = 4B / 12.5ns = 4B / (12.5×10⁻⁹s) = 320MB/s。

知识点： CPU 性能、Cache、DMA、交叉存储。

---

第44题（12分）

题目： 某 16 位计算机中，带符号整数用补码表示，数据 Cache 和指令 Cache 分离。下表给出了指令系统中部分指令格式，其中 Rs 和 Rd 表示寄存器，mem 表示存储单元地址，(x) 表示寄存器 x 或者存储单元 x 的内容。

名称	指令的汇编格式	指令功能
加法指令	ADD Rs,Rd	(Rs)+(Rd)→Rd
算术/逻辑左移	SHL Rd	2*(Rd)→Rd
算术右移	SHR Rd	(Rd)/2→Rd
取数指令	LOAD Rd,mem	(mem)→Rd
存数指令	STORE Rs,mem	(Rs)→mem

该计算机采用 5 段流水方式执行指令，各流水段分别是取指(IF)、译码/读寄存器(ID)、执行/计算有效地址(EX)、访问存储器(M)和结果写回寄存器(WB)，流水线采用“按序发射，按序完成”方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题：

（1）若 int 型变量 x 的值为 -513，存放在寄存器 R1 中，则执行指令“SHR R1”后，R1 的内容是多少？（用十六进制表示）
（2）若某个时间段中，有连续的 4 条指令进入流水线，在其执行过程中没有发生任何阻塞，则执行这 4 条指令所需的时钟周期数是多少？
（3）若高级语言程序中某赋值语句为 x = a + b，x、a 和 b 均为 int 型变量，它们的存储单元地址分别表示为 [x]、[a] 和 [b]。该语句对应的指令序列及其在指令流水线中的执行过程如下表所示。则这 4 条指令执行过程中，I3 的 ID 段和 I4 的 IF 段被阻塞的原因各是什么？

I1 LOAD R1,[a]
I2 LOAD R2,[b]
I3 ADD R1,R2
I4 STORE R2,[x]

（4）若高级语言程序中某赋值语句为 x = x*2 + a，x 和 a 均为 unsigned int 类型变量，它们的存储单元地址分别表示为 [x]、[a]，则执行这条语句至少需要多少个时钟周期？要求模仿题上表画出该条语句对应的指令序列及其在流水线中的执行过程示意图。

解答：

（1）
-513 的 16 位补码 = 0xFDFF。
SHR 算术右移 1 位：0xFEFF。

（2）
5 段流水线，4 条指令，无阻塞，所需周期 = 5 + 4 - 1 = 8 个时钟周期。

（3）
I3 的 ID 段阻塞：因为 I1 和 I2 是 LOAD 指令，其结果要到 WB 段才写回，I3 需要读 R1 和 R2，发生数据相关，需等待。
I4 的 IF 段阻塞：因为 I3 在 ID 段阻塞，导致流水线停顿，I4 无法取指。

（4）
x = x*2 + a 可分解为：

• LOAD R1, [x]
• SHL R1
• LOAD R2, [a]
• ADD R1, R2
• STORE R1, [x]

至少需要 9 个时钟周期。流水线示意图略。

知识点： 流水线、数据相关、控制相关。

---

第45题（7分）

题目： 某请求分页系统的局部页面置换策略如下：系统从 0 时刻开始扫描，每隔 5 个时间单位扫描一轮驻留集（扫描时间忽略不计），本轮没有被访问过的页框将被系统回收，并放入空闲页框链尾，其中内容在下一次分配前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框中，那么重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销。初始进程驻留集为空。当前系统空闲页框链表中页框号依次为 32、15、21、41。进程 P 依次访问的 <虚拟页号，访问时刻> 是 <1,1>、❤️,2>、<0,4>、<0,6>、<1,11>、<0,13>、<2,14>。请回答下列问题。

（1）访问 <0,4> 时，对应的页框号是什么？说明理由。
（2）访问 <1,11> 时，对应的页框号是什么？说明理由。
（3）访问 <2,14> 时，对应的页框号是什么？说明理由。
（4）该策略是否适合于时间局部性好的程序？说明理由。

解答：

（1）
<0,4> 缺页，从空闲链取 21，所以页框号为 21。

（2）
<1,11> 时，页 1 曾在时刻 1 访问过，其页框 32 可能已被回收放入空闲链。根据策略，若该页还在空闲页框中，则重新放回驻留集。所以页框号为 32。

（3）
<2,14> 缺页，从空闲链头部取 41，所以页框号为 41。

（4）
适合。因为该策略会保留最近访问过的页面，对时间局部性好的程序能减少缺页。

知识点： 页面置换、局部性。

---

第46题（8分）

题目： 某文件系统空间的最大容量为 4TB（1TB=2⁴⁰B），以磁盘块为基本分配单位。磁盘块大小为 1KB。文件控制块(FCB)包含一个 512B 的索引表区。请回答下列问题：

（1）假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号，索引表项中块号最少占多少字节？可支持的单个文件最大长度是多少字节？
（2）假设索引表区采用如下结构：第 0~7 字节采用 <起始块号,块数> 格式表示文件创建时预分配的连续存储空间，其中起始块号占 6B，块数占 2B；剩余 504 字节采用直接索引结构，一个索引项占 6B，那么可支持的单个文件最大长度是多少字节？为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。

解答：

（1）
4TB / 1KB = 2³² 块，块号至少 32 位 = 4B。
索引表区 512B，直接索引项数 = 512 / 4 = 128。
最大文件长度 = 128 × 1KB = 128KB。

（2）
起始块号 6B，块数 2B，连续空间最大块数 = 2¹⁶ - 1 = 65535。
剩余 504B，每项 6B，共 504 / 6 = 84 项。
最大长度 = (65535 + 84) × 1KB = 65619KB。
合理值：起始块号 5B，块数 3B。因为 4TB 需要 42 位，5B=40 位不够，6B=48 位足够。块数 3B=24 位可表示更多块，使文件更大。

知识点： 文件索引、FCB、文件最大长度。

---

第47题（9分）

题目： 某主机的 MAC 地址为 00-15-C5-C1-5E-28，IP 地址为 10.2.128.100（私有地址）。下图（a）是网络拓扑，图（b）是该主机进行 Web 请求的 1 个以太网数据帧前 80B 的十六进制及 ASCII 码内容。请参考图中的数据回答以下问题：

（1）Web 服务器的 IP 地址是什么？该主机的默认网关的 MAC 地址是什么？
（2）该主机在构造图（b）所示的数据帧时，使用什么协议确定目的 MAC 地址？封装该协议请求报文的以太网帧的目的 MAC 地址是什么？
（3）假设 HTTP/1.1 协议以持续的非流水线方式工作，一次请求—响应时间为 RTT，rfc.html 页面引用了 5 个 JPEG 小图像，则从发出如图（b）所示的 Web 请求开始到浏览器收到全部内容为止，需要多少个 RTT？
（4）该帧所封装的 IP 分组经过路由器 R 转发时，需修改 IP 分组头中的哪些字段？

解答：

（1）
Web 服务器 IP 从 IP 分组目的地址字段读取（图中为 64.170.98.32）。
默认网关 MAC 从以太网帧目的 MAC 地址字段读取（图中为 00-15-C5-C1-5E-28 或其他）。

（2）
使用 ARP 协议。
ARP 请求报文的以太网帧目的 MAC 地址为广播地址 FF-FF-FF-FF-FF-FF。

（3）
HTTP/1.1 持续非流水线：请求页面 1 个 RTT，收到响应；然后依次请求 5 个图像，每个 1 个 RTT，共 5 个 RTT。
总共 1 + 5 = 6 个 RTT。

（4）
经过路由器转发时，需修改：

• 源 IP 地址（若 NAT）
• 目的 IP 地址（通常不变）
• TTL 减 1
• 首部校验和
• 可能还有标识、标志、片偏移（若分片）

知识点： 以太网帧、ARP、HTTP、IP 转发。

---

结语

以上为 2012 年全国硕士研究生招生考试计算机学科专业基础试题（408）的详细解析。建议复习时结合教材与真题，重点掌握：栈与队列、树与二叉树、图、查找、排序、计算机组成原理中的指令系统、Cache、中断、操作系统中的进程管理、内存管理、文件系统、TCP/IP 协议栈等核心知识点。祝备考顺利！