2016 年 408 真题
本节正在编写中，敬请期待。
选择题
数据结构
1
已知表头元素为 c 的单链表在内存中的存储状态如下表所示。现将 f 存放于 1014H 处并插入单链表，若 f 在逻辑上位于 a 和 e 之间，则 a,e,f 的”链表地址“依次是（ ）。
根据存储状态，单链表的结构如下图所示。
其中“链接地址”是指结点 next 所指的内存地址。当结点 f 插入后， a 指向 f, f 指向 e, e 指向 b 。显然 a 、 e 和 f 的“链接地址”分别是 f、 b 和 e 的内存地址，即 1014H 、 1004H 和 1010H 。
2
已知一个带有表头结点的双向循环链表 L,结点结构为 prev|data|next，prev 和 next 分别是指向其直接前驱和直接后继结点的指针。现要删除指针 p 所指的结点，正确的语句序列是（ ）。
此类题的解题思路万变不离其宗，无论是链表的插入还是删除都必须保证不断链。
3
设有下图所示的火车车轨，入口到出口之间有 n 条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。现有编号为 1-9 的 9 列列车，驶入的次序依次是 8, 4, 2, 5, 3, 9, 1, 6, 7。若期望驶出的次序依次为 1~9，则 n 至少是（ ）。
在确保队列先进先出原则的前提下。根据题意具体分析：入队顺序为 8,4, 2, 5, 3, 9, 1, 6, 7, 出队顺序为 1~9 。入口和出口之间有多个队列 （n 条轨道），且每个队列（轨道）可容纳多个元 素（多列列车）。如此分析：显然先入队的元素必须小千后入队的元素（如果 8 和 4 入同一队列， 8 在前 4 在后，那么出队时只能是 8 在前 4 在后），这样 8 入队列 1, 4 入队列 2, 2 入队列 3, 5 入队列 2 （按照前面的原则“大的元素在小的元素后面”也可以将 5 入队列 3, 但这时剩下的元 素 3 就必须放到一个新的队列里面，无法确保”至少“，本应该是将 5 入队列 2, 再将 3 入队列 3, 不增加新队列的情况下，可以满足题意“至少”的要求）， 3 入队列 3, 9 入队列 1, 这时共 占了 3 个队列，后面还有元素 1, 直接再占用一个新的队列 4, 1 从队列 4 出队后，剩下的元素 6 和 7 或者入队到队列 2 或者入队到队列 3( 为简单起见我们不妨设 n 个队列的序号分别为 1, 2, …, n), 这样就可以满足题目的要求。综上，共占用了 4 个队列。当然还有其他的入队出队的情况， 请考生们自己推演。但要确保满足： O 队列中后面的元素大千前面的元素；@确保占用最少（即 满足题目中的“至少")的队列。
4
有一个 100 阶的三对角矩阵 M ，其元素 mi,j(1≤i≤100,1≤j≤100) 按行优先依次压缩存入下标从 0 开始的一维数组 N 中。元素 m30,30 在数组 N 中的下标是（ ）。
采用压缩存储， 将 3 条对角线上的元素按行优先方式存放在一 维数组 B 中，且 $a_{1,1}$ 存放于 B[0] 中， 其存储形式如下所示：
可以计算矩阵 A 中 3 条对角线上的元素 $a_{i,j}$ ($1 \le i,j \le n, |i-j| \le 1$) 在一维数组 B 中存放的下标为 k = 2i + j - 3。
解法一 ：针对该题，仅需将数字逐一代入公式里面即可：k=2x30+30-3 = 87, 结果为 87。
解法二：观察上图的三对角矩阵不难发现， 第一行有两个元素， 剩下的在元素 $m_{30, 30}$ 所在 行之前的 28 行（注意下标 $1 \le i \le 100$、$1 \le j \le 100$）中每行都有 3 个元素， 而 $m_{30, 30}$ 之前仅有一个元素 $m_{30, 29}$, 那么不难发现元素 $m_{30,30}$ 在数组 N 中的下标是：2+28x3+2-1 = 87。
5
若森林 F 有 15 条边、25 个结点，则 F 包含树的个数是（ ）。
解法一：树有一个很重要的性质：在 n 个结点的树中有 n-1 条边，“那么对于每棵树，其结点数比边数多 1”。题中的森林中的结点数比边数多 10（即 25-15=10），显然共有 10 棵树。
解法二：若考生再仔细分析可发现，此题也是考察图的某些方面的性质：生成树和生成森林。此时对于图的生成树有一个重要的性质：若图中顶点数为 n，则它的生成树含有 n-1 条边。对比解法一中树的性质，不难发现两种解法都利用到了“树中结点数比边数多 1”的性质，接下来的分析如解法一。
6
下列选项中，不是下图深度优先搜索序列的是（）
对于本题，只需按深度优先遍历的策略进行遍历即可。对千选项 A: 先访问 $V_1$, 然后访问 与 $V_1$ 邻接且未被访问的任一顶点（满足的有 $V_2$、$V_3$ 和 $V_5$）, 此时访问 $V_5$, 然后从 $V_5$ 出发，访 问与 $V_5$ 邻接且未被访问的任一顶点（满足的只有 $V_4$）, 然后从 $V_4$ 出发， 访问与 $V_4$ 邻接且未被 访问的任一顶点（满足的只有 $V_3$），然后从 $V_3$ 出发，访问与 $V_3$ 邻接且未被访问的任一顶点（满足的只有$V_2$）, 结束遍历。选项 B 和 C 的分析方法与选项 A 相同，不再赘述。对千选项 D, 首 先访问 $V_1$ , 然后从 $V_1$ 出发， 访问与 $V_1$ 邻接且未被访问的任一顶点（满足的有 $V_2$ 、$V_3$ 和 $V_5$）, 然后从 $V_2$ 出发， 访问与 $V_2$ 邻接且未被访问的任一顶点（满足的只有 $V_5$）, 按规则本应该访问 $V_5$, 但选项 D 却访问 $V_3$, 因此 D 错误。
7
若将 n 个顶点 e 条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是（）
根据拓扑排序的规则， 输出每个顶点的同时还要删除以它为起点的边， 这样对各顶点和边都要进行遍历， 故拓扑排序的时间复杂度为 $O(n+e)$。
8
使用迪杰斯特拉（Djkstra）算法求下图中从顶点 1 到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是（ ）。
根据 Dijkstra 算法， 从顶点 1 到其余各顶点的最短路径如下表所示。
9
在有 n(n>1000)个元素的升序数组 A 中查找关键字 x。查找算法的伪代码如下所示。
k = 0;
while (k < n 且 A[k] < x) k = k + 3;
if (k < n 且 A[k] == x) 查找成功；
else if (k - 1 < n 且 A[k - 1] == x) 查找成功；
else if (k - 2 < n 且 A[k - 2] == x) 查找成功；
else 查找失败；
本算法与折半查找算法相比，有可能具有更少比较次数的情形是（）
此题为送分题。 该程序采用跳跃式的顺利查找法查找升序数组中的 X, 显然是 x 越靠前， 比较次数才会越少。
10
B+ 树不同于 B 树的特点之一是（）
由于 B+树的所有叶结点中包含了全部的关键字信息，且叶结点本身依关键字从小到大顺序 链接， 可以进行顺序查找， 而 B 树不支持顺序查找 （只支持多路查找）。
11
对 10TB 的数据文件进行排序，应使用的方法是（）
外部排序指待排序文件较大， 内存一次性放不下， 需存放在外部介质中。 外部排序通常采用归并排序法。 选项 A、 B、C 都是内部排序的方法。
组成原理
12
将高级语言源程序转换为机器目标代码文件的程序是（ ）。
翻译程序是指把高级语言源程序转换成机器语言程序（目标代码）的软件。 翻译程序有两 种： 一种是编译程序， 它将高级语言源程序一次全部翻译成目标程序， 每次执行程序时， 只要 执行目标程序， 因此， 只要源程序不变， 就无须重新编译。 另 一种是解释程序， 它将源程序的 一条语旬翻译成对应的机器目标代码， 并立即执行， 然后翻译下一条源程序语句并执行， 直至 所有源程序语句全部被翻译并执行完。 所以解释程序的执行过程是翻译一句执行一句， 并 且不 会生成目标程序。汇编程序也是一种语言翻译程序，它把汇编语言源程序翻译为机器语言程序。 汇编语言是一种面向机器的低级语言， 是机器语言的符号表示， 与机器语言一一对应。
13
有如下 C 语言程序段
short si = -32767;unsigned short usi = si;
执行上述两条语句后，usi 的值为（ ）。
结合题干及选项可知，short 为 16 位。 因 C 语言中的数据在内存中为补码表示形式，si 对 应的补码二进制表示为： 1000 0000 0000 0001B, 最前面的一位 “1” 为符号位， 表示负数， 即 -32767。 由 signed 型转化为等长 unsigned 型数据时， 符号位成为数据的一部分， 也就是说，负 数转化为无符号数（即正数），其数值将发生变化。Usi 对应的补码二进制表示与 si 的表示相同， 但表示正数， 为 32769。
14
某计算机字长为 32 位，按字节编址，采用小端 (Little Endian) 方式存放数据，假定有一个 double 型变量，其机器数表示为 1122 3344 5566 7788H 存放在 0000 8040H 开始的连续存储单元中，则存储单 0000 8046H 中存放的是（ ）。
大端方式： 一个字中的高位字节(Byte)存放在内存中这个字区域的低地址处。 小端方式： 一个字中的低位字节(Byte)存放在内存中这个字区域的低地址处。 依此分析， 各字节的存储 分配如下表所示。
从而存储单元 0000 804 6H 中存放的是 22H。
15
有如下 C 语言程序段：
for (k = 0; k < 1000; k++)
a[k] = a[k] + 32;
若数组 a 以及变量 k 均为 int 型，int 型数据占 4B，数据 Cache 采用直接映射方式，数据区大小是 1KB，块大小是 16B，该程序段执行前 Cache 为空，则该程序段执行过程中，访问数组 a 的 Cache 的缺失率是（ ）。
分析语旬"a[k]=a[k] + 32": 首先读取 a[k]需要访问一次 a[k], 之后将结果赋值给 a[k]需要 访问一次，共访问两次。第一次访问 a[k]未命中，并将该字所在的主存块调入 Cache 对应的块 中，对于该主存块中的 4 个整数的两次访问中只在访问第一次的第一 个元素时发生缺失，其他 的 7 次访问中全部命中，故该程序段执行过程中访问数组 a 的 Cache 缺失率约为 1/8（即 1 2.5%）。
16
某存储器容量为 64KB，按字节编址，地址 4000H～5FFFH 为 ROM 区，其余为 RAM 区。若采用 8K×4 位的 SRAM 芯片进行设计，则需要该芯片的数量是（ ）。
SFFF-4 000+1= 2000H, 即 ROM 区容量为 $2^{13}$ B= 8 KB(2000H = $2 \times 16^{3} = 2^{13}$), RAM 区容量 为 56KB(64KB-8KB=56KB), 则需要 8 Kx4 位的 SRAM 芯片的数量为 14(56KB/8Kx4 位=14 )。
17
某指令格式如下所示。
其中 M 为寻址方式，I 为变址寄存器编号，D 为形式地址。若采用先变址后间址的寻址方式，则操作数的有效地址是（ ）。
变址寻址中， 有效地址 EA 等于指令字中的形式地址 D 与变址寄存器 I 的内容相加之和， 即 EA= (I)+ D。间接寻址是相对于直接寻址而言的，指令的地址字段给出的形式地址不是操作 数的真正地址，而是操作数地址的地址，即 EA=(D)。从而该 操作数的有效地址是((I)+ D)。
18
某计算机主存空间为 4GB，字长为 32 位，按字节编址，采用 32 位定长指令字格式，若指令按字边界对齐存放，则程序计数器 (PC) 和指令寄存器 (IR) 的位数至少分别是（ ）。
程序计数器(PC)给出下一 条指令字的访存地址（指令在内存中的地址），取决于存储器 的字数( 4 GB/32bit= 230), 故程序计数器(PC) 的位数至少是 30 位；指令寄存器 CIR)用于 接收取得的指令，取决于指令字长( 32 位），故指令寄存器 CIR) 的位数至少为 32 位。
19
在无转发机制的五段基本流水线中，下列指令序列存在数据冒险的指令对是（ ）。
I1: add R1, R2, R3; (R2)+(R3)→R1
I2: add R5, R2, R4; (R2)+(R4)→R5
I3: add R4, R5, R3; (R5)+(R3)→R4
I4: add R5, R2, R6; (R2)+(R6)→R5
数据冒险，即数据相关， 指在一个程序中存在必须等前一条指令执行完才能执行后一条指 令的情况，则 这两条指令即为数据相关。当多条指令重叠处理时就会发生冲突。首先这两条指 令发生写后读 相关，并且两条指令在流水线中执行情况（发生数据冒险）如下表所示：
指令 12 在时钟 5 时将结果写入寄存器(R5), 但指令 13 在时钟 3 时读 寄存器(R5)。本来 指令 12 应先写入 R5, 指令 13 后读 R5, 结果变成指令 13 先读 R5, 指令 12 后写入 R5, 因而发 生数据冲突。
20
单周期处理器中所有指令的指令周期为一个时钟周期。下列关干单周期处理器的叙述中，错误的是（ ）。
单周期处理器即指所有指令的指令周期为一个时钟周期，D 正确。因为每条指令的 CPI 为 I, 要考虑比较慢的指令， 所以处理器 的时钟频率较低，B 正确。单总线结构将 CPU、主存、1/0 设备都挂在一组总线上，允许 1/0 设备之间、1 /0 设备与主存之间直接交换信息，但多个部件只 能争用唯一的总线， 且不支持并发传送操作。单周期处理器并不是可以采用单总线结构数据通 路，故 A 错误。控制信号即指 PC 中的内容，PC 用来存放当前欲执行指令的地址， 可以自动 +1 以形成下一 条指令的地址。在指令执行过程中控制信号不变化。
21
下列关干单周期处理器的叙述中，错误的是（ ）。
初看可能会觉得 A 正确，并行总线传输通常比串行总线传输 速度快，但这不是绝对的。在 实际时钟频率比较低的情况下，并行总线因为可以同时传输若干比特，速率确实比串行总线快。 但是， 随着技术的发展，时钟频率越来越高， 并行导线之间的相互干扰越来越严重， 当时钟频 率提高到一 定程度时，传输的数据已经无法恢复。而串行总线因为导线少，线间干扰容易控制， 反而可以通过不断提高时钟频率来提高传输速率，A 错误。总线复用是指一种信号线在不同的 时间传输不 同的信息。可以使用较少的线路传输更多的信息，从而节省了空间和成本。故 B 正 确。 突发（猝发）传输是在一个总线周期中，可以传输多个存储地址连续的数据， 即 一 次传输 一 个地址和一 批地址连续的数据，C 正确。分离事务通信即总线复用的一种，相比单一的传输 线路可以提高总线的利用率，D 正确。
22
异常是指令执行过程中在处理器内部发生的特殊事件，中断是来自处理器外部的请求事件。下列关于中断或异常情况的叙述中，错误的是（ ）。
中断是指来自 CPU 执行指令以外事件的发生，如设备发出的 1/0 结束中断，表示设备输入／ 输出处理已经完成，希望处理机能够向设备发出下一个输入／输出请求，同时让完成输入／输出后 的程序继续运行。时钟中断，表示一 个固定的时间片已到，让处理机处理计时、启动定时运行 的任务等。这一类中断通常是与当前程序运行无关的事件， 即它们与当前处理机运行的程序无 关。 异常也称内中断、例外或陷入(Trap), 指源自 CPU 执行指令内部的事件，如程序的非法 操作码、地址越界、算术溢出、虚存系统的缺页以及专门的陷入指令等引起的事件。A 错误。
操作系统
23
下列关于批处理系统的叙述中，正确的是（ ）
Ⅰ.批处理系统允许多个用户与计算机直接交互
Ⅱ.批处理系统分为单道批处理系统和多道批处理系统
Ⅲ.中断技术使得多道批处理系统和 I/O 设备可与 CPU 并行工作
批处理系统中，作业执行时用户无法干预其运行，只能通过事先编制作业控制说明书来间 接干预，缺少交互能力，也因此才发展出分时系统，I 错误。批处理系统按发展历程又分为单道 批处理系统、多道批处理系统，II 正确。多道程序设计技术允许同时把多个程序放入内存， 并 允许它们交替在 CPU 中运行，它们共享系统中的各种硬、软件资源， 当 一道程序因 1/0 请求而 暂停运行时，CPU 便立即转去运行另 一道程序，即多道批处理系统的 1/0 设备可与 CPU 并行工 作，这都是借助于中断技术实现的，III 正确。
24
某单 CPU 系统中有输入和输出设备各 1 台，现有 3 个并发执行的作业，每个作业的输入、计算和输出时间均分别为 2ms，3ms 和 4ms，且都按输入、计算和输出的顺序执行，则执行完 3 个作业需要的时间最少是（）。
这类调度题目最好画图。因 CPU、输入设备、输出设备都只有一 个，因此各操作步骤不能 重叠，画出运行时的甘特图后就能清楚地看到不同作业间的时序关系，如下表所示。
25
系统中有 3 个不同的临界资源 R1、R2 和 R3，被 4 个进程 p1、p2、p3 及 p4 共享。各进程对资源的需求为：p1 申请 R1 和 R2，p2 申请 R2 和 R3，p3 申请 R1 和 R3，p4 申请 R2。若系统出现死锁，则处于死锁状态的进程数至少是（ ）。
对于本题，先满足一个进程的资源需求，再看其他进程是否能出现死锁状态。因为 p4 只申 请一个资源， 当将 R2 分配给 p4 后，p4 执行完后将 R2 释放，这时使得系统满足死锁的条件是 R1 分配给 p1，R2 分配给 p2，R3 分配给 p3 （或者 R2 分配给 p1，R3 分配给 p2，R1 分配给 p3）。 穷举 其他情况如 p1 申请的资源 R1 和 R2, 先都分配给 p1, 运行完并释放占有的资源后，可以分别将 R1、R2 和 R3 分配给 p3、p4 和 p2，也满足系统死锁的条件。各种情况需要使得处于死锁状态的 进程数至少为 3。
26
某系统采用改进型 CLOCK 置换算法，页表项中字段 A 为访问位，M 为修改位。A=0 表示页最近没有被访问，A=1 表示页最近被访问过。M=0 表示页没有被修改过，M=1 表示页被修改过。按 (A, M) 所有可能的取值，将页分为四类：(0, 0)、(1, 0)、(0, 1) 和 (1, 1)，则该算法淘汰页的次序为（ ）。
改进型的 CLOCK 置换算法执行的步骤如下：
27
使用 TSL (Test and Set Lock) 指令实现进程互斥的伪代码如下所示。
do {
...
while (TSL(&lock));
critical section;
lock = FALSE;
...
} while (TRUE);
下列与该实现机制相关的叙述中，正确的是（ ）。
当进程退出临界区时置 lock 为 FALSE, 会负责唤醒处于就绪状态的进程，A 错误。若等待 进入临界区的进程会一直停留在执行 while(TSL(&lock))的循环中，不会主动放弃 CPU, B 正确。 让权等待， 即当进程不能进入临界区时， 应立即释放处理器， 防止进程忙等待。 通过 B 选项的 分析中发现上述伪代码并不满足 “ 让权等待 ” 的同步准则，C 错误。 若 while(TSL(&lock))在关 中断状态下执行， 当 TSL(&lock)一直为 true 时， 不再开中断，则系统可能会因此终止，D 错误。
28
某进程的段表内容如下所示。
当访问段号为 2、段内地址为 400 的逻辑地址时，进行地址转换的结果是（ ）。
分段系统的逻辑地址 A 到物理地址 E 之间的地址变换过程如下。
题目中段号为 2 的段长为 300, 小于段内地址为 400, 故发生越界异常， D 正确。
29
某进程访问页面的序列如下所示。
若工作集的窗口大小为 6，则在 t 时刻的工作集为（ ）。
在任一时刻 t, 都存在一个集合， 它包含所有最近 k 次（该题窗口大小为 6） 内存访问所访 问过的页面。这个集合 w(k, t)就是工作集。该题中最近 6 次访问的页面分别为 6,0, 3, 2, 3, 2, 再 去除重复的页面， 形成的工作集为{6,0, 3, 2}。
30
进程 P1 和 P2 均包含并发执行的线程，部分伪代码描述如下所示。
int x = 0;
Thread1()
{
int a;
a = 1; x += 1;
}
Thread2()
{
int a;
a = 2; x += 2;
}
int x = 0;
Thread3()
{
int a;
a = 1; x += 3;
}
Thread4()
{
int b;
b = x; x += 4;
}
下列选项中，需要互斥执行的操作是（ ）。
P1 中对 a 进行赋值，并不影响最终的结果，故 a = l 与 a = 2 不需要互斥执行； a = x 与 b=x 执行先后不影响 a 与 b 的结果， 无须互斥执行； X += 1 与 x+=2 执行先后会影响 x 的结果， 需要互斥执行； P1 中 的 x 和 P2 中的 x 是不同范围中的 X, 互不影响， 不需要互斥执行。
31
下列关于 SPOOLing 技术的叙述中，错误的是（ ）。
SPOOLing 是利用专门的外围控制机，将低速 1/0 设备上的数据传送到高速磁盘上，或者 相反。SPOOLing 的意思是外部设备同时联机操作， 又称为假脱机输入／输出操作， 是操作系 统中采用的一 项将独占设备改造成共享设备的技术。高速磁盘即外存，A 正确。SPOOLing 技 术需要进行输入／输出操作， 单道批处理系统无法满足，B 正确。SPOOLing 技术实现了将独 占设备改造成共享设备的技术，C 正确。设备与输入／输出井之间数据的传送是由系统实现的， D 错误。
32
下列关于管程的叙述中，错误的是（ ）。
管程是由一组数据以及定义在这组数据之上的对这组数据的操作组成的软件模块， 这组操 作能初始化并改变管程中的数据和同步进程。 管程不仅能实现进程间的互斥， 而且能实现进程 间的同步， 故 A 错误、B 正确。 管程具有特性：@局部于管程的数据只能被局部于管程内的过 程所访问；@一个进程只有通过调用管程内的过程才能进入管程访问共享数据；@每次仅允许 一 个进程在管程内执行某个内部过程， 故 C 和 D 正确。
计算机网络
题 33-41 均依据 题 33-41 图 回答
33
在 OSI 参考模型中，R1、Switch、Hub 实现的最高功能层分别是（ ）。
集线器是一个多端口的中继器， 工作在物理层。 以太网交换机是一个多端口的网桥， 工作 在数据链路层。 路由器是网络层设备， 它实现了网络模型的下三层， 即物理层、 数据链路层和 网络层。 题中 Rl、Switch 和 Hub 分别是路由器、 交换机和集线器， 实现的最高层功能分别是 网络层（即 3）、 数据链路层（即 2） 和物理层（即 1）。
34
若连接 R2 和 R3 链路的频率带宽为 8 kHz，信噪比为 30 dB，该链路实际数据传输速率约为理论最大数据传输速率的 50％，则该链路的实际数据传输速率约是（ ）。
香农定理给出了带宽受限且有高斯白噪声干扰的信道的极限数据传输速率， 香衣定理定义 为：信道的极限数据传输速率 = $log_{2}(1 +S/N)$, 单位 bps。其中，$S/N$ 为信噪比， 即信号的平均 功率和噪声的平均功率之比，信噪比= $10log_{10}(S/N)$, 单位 dB, 当 $S/N$=1000 时，信噪比为 30dB, 则该链路的实际数据传输速率约为 $50% \times Wlog_{2}(1 +S/N)$ = $50% \times 8k \times log_{2}(l + 1000)$ =40kbps。
35
若主机 H2 向主机 H4 发送 1 个数据帧，主机 H4 向主机 H2 立即发送一个确认帧，则除 H4 外，从物理层上能够收到该确认帧的主机还有（ ）。
关于物理层、 数据链路层、 网络层设备对于隔离冲突域的总结如下表所示。
交换 机(Switch) 可以隔离冲突域，但集线器(Hub)无法 隔离冲突域，因此从物理层上 能够收到该确认帧的主机仅 H2、H3, 选项 D 正确。
36
若 Hub 再生比特流过程中，会产生 1.535μs 延时，信号传播速度为 200m/μs，不考虑以太网帧的前导码，则 H3 与 H4 之间理论上可以相距的最远距离是（ ）。
因为要解决 “理论上可以相距的最远距离 ” ，所以最远肯定要保证能检测到碰撞，而以太 网规定 最短帧长为 64B, 其中 Hub 为 lOOBase-T 集线器，可知线 路的传输速率为 lOOMbps, 则 单程 传输时延为 64B/l00Mbps/2 = 2.56μs, 又 Hub 再产生比特流的过程中会导致延时 l.535μs, 则单程的传播时延为 2.56μs- l.535μs = l.025μs, 从而 H3 与 H4 之间理论上可以相距的最远距离 为 200m/μsxl.025μs = 205m。
37
假设 R1、R2、R3 采用 RIP 协议交换路由信息，且均已收敛。若 R3 检测到网络 201.1.2.0/25 不可达，并向 R2 通告一次新的距离向量，则 R2 更新后，其到达该网络的距离是（ ）。
因为 R3 检测到网络 201.1.2.0/25 不可达，故将到该网络的距离设置为 16 （距离为 16 表示 不可达） 。 当 R2 从 R3 收到路由信息时，因为 R3 到该网络的距离为 16, 则 R2 到该网络 也不可 达，但此时记录 Rl 可达 （由千 RIP 的特点“ 坏消息传得慢", Rl 并没有收到 R3 发来的路由信 息），Rl 到该网络的距离为 2, 再加上从 R2 到 Rl 的 l 就是 R2 到该网络的距离 3。
38
假设连接 R1、R2 和 R3 之间的点对点链路使用 201.1.3.x/30 地址，当 H3 访问 Web 服务器 S 时，R2 转发出去的封装 HTTP 请求报文的 IP 分组的源 IP 地址和目的 IP 地址分别是（ ）。
由题意知连接 Rl、 R2 和 R3 之间的点对点链路使用 20l.1.3.x/30 地址，其子网掩码为 255.255.255.252, Rl 的一 个接口的 IP 地址为 201.1.3.9, 转换为对应的二进制的后 8 位为 0000 1001 C 由 201.l.3.x/30 知，IP 地址 对应的二进制的后两位为主机号，而 主机号全为 0 表示本网 络本身， 主机号全为 1 表示本网络的广播地址，不用于源 IP 地址或者目的 IP 地址），那么除 201.l.3.9 外，只有 IP 地址为 201.1.3.10 才可以作为源 IP 地址使用（本题为 201.1.3.10)。Web 服务器的 IP 地址为 130.18.10.1, 作为 IP 分组的目的 IP 地址 。 综上可知，选项 D 正确。
39
假设 H1 与 H2 的默认网关和子网掩码均分别配置为 192.168.3.1 和 255.255.255.128，H3 与 H4 的默认网关和子网掩码均分别配置为 192.168.3.254 和 255.255.255.128，则下列现象中可能发生的是（ ）。
从子网掩码可知 Hl 和 H2 处于同 一 网段，H3 和 H4 处于 同 一 网段，分别可以进行正常的 IP 通信，A 和 D 错误。 因为 R2 的 El 接口的 IP 地址为 192.168.3.254, 而 H2 的默认网关为 192.168.3.1, 所以 H2 不能访问 Internet, 而 H4 的默认网关为 192.168.3.254, 所以 H4 可以正常 访问 Internet, B 错误。 由 H1、H2、H3 和 H4 的子网掩码可知 H1、H2 和 H3、H4 处于不 同的 网段， 需通 过路由器才能进行正常的 IP 通信，而这时 H1 和 H2 的默认网关为 192.168.3.l, 但 R2 的 El 接口的 IP 地址为 192.168.3.254, 无法进行通信，从而 Hl 不能与 H3 进行正常的 IP 通 信 。 C 正确。
40
假设所有域名服务器均采用迭代查询方式进行域名解析。当 H4 访问规范域名为 www.abc.xyz.com 的网站时，域名服务器 201.1.1.1 在完成该域名解析过程中，可能发出 DNS 查询的最少和最多次数分别是（ ）。
最少情况下： 当本机 DNS 高速缓存中存有该域名的 DNS 信息时，则不 需要查询任何域名 服务器，这样最少发出 0 次 DNS 查询。最多情况下：因为均采用迭代查询的方式，在最坏的情 况下，需要依次迭代地向本地域名服务器 、根域名服务器(.com)、顶级域名服务器(xyz.com)、 权限域名服务器(abc.xyz.com) 发出 DNS 查询 请求，因此 最多发出 4 次 DNS 查询。
解答题
计算机网络
41
假设题 33～41 图中的 H3 访问 Web 服务器 S 时，S 为新建的 TCP 连接分配了 20 KB (K=1 024) 的接收缓存，最大段长 MSS=1 KB，平均往返时间 RTT=200 ms。H3 建立连接时的初始序号为 100，且持续以 MSS 大小的段向 S 发送数据，拥塞窗口初始阈值为 32 KB；S 对收到的每个段进行确认，并通告新的接收窗口。假定 TCP 连接建立完成后，S 端的 TCP 接收缓存仅有数据存入而无数据取出。请回答下列问题。
(1) 在 TCP 连接建立过程中，H3 收到的 S 发送过来的第二次握手 TCP 段的 SYN 和 ACK 标志位的值分别是多少？确认序号是多少？
(2) H3 收到的第 8 个确认段所通告的接收窗口是多少？此时 H3 的拥塞窗口变为多少？H3 的发送窗口变为多少？
(3) 当 H3 的发送窗口等于 0 时，下一个待发送的数据段序号是多少？H3 从发送第 1 个数据段到发送窗口等于 0 时刻为止，平均数据传输速率是多少（忽略段的传输延时）？
(4) 若 H3 与 S 之间通信已经结束，在 t 时刻 H3 请求断开该连接，则从 t 时刻起，S 释放该连接的最短时间是多少？
数据结构
42
如果一棵非空 $k$ （ $k \ge 2$ ） 叉树 $T$ 中每个非叶结点都有 $k$ 个孩子，则称 $T$ 为正则 $k$ 叉树。请回答下列问题并给出推导过程。
(1) 若 $T$ 有 $m$ 个非叶结点，则 $T$ 中的叶结点有多少个？
(2) 若 $T$ 的高度为 $h$ （单结点的树 $h=1$ ），则 $T$ 的结点数最多为多少个？最少为多少个？
43
已知由 n(n≥2) 个正整数构成的集合 A={ak|0≤k<n} ，将其划分为两个不相交的子集 A1 和 A2 ，元素个数分别是 n1 和 n2 ， A1 和 A2 中元素之和分别为 S1 和 S2 。设计一个尽可能高效的划分算法，满足 |n1−n2| 最小且 |S1−S2| 最大。要求：
(1) 给出算法的基本设计思想。
(2) 根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释。
(3) 说明你所设计算法的时间复杂度和空间复杂度。
组成原理
44
假定 CPU 主频为 50MHz，CPI 为 4。设备 D 采用异步串行通信方式向主机传送 7 位 ASCII 字符，通信规程中有 1 位奇校验位和 1 位停止位，从 D 接收启动命令到字符送入 I/O 端口需要 0.5ms。请回答下列问题，要求说明理由。
(1) 每传送一个字符，在异步串行通信线上共需传输多少位？在设备 D 持续工作过程中，每秒钟最多可向 I/O 端口送入多少个字符？
(2) 设备 D 采用中断方式进行输入/输出，示意图如下∶
I/O 端口每收到一个字符申请一次中断，中断响应需 10 个时钟周期，中断服务程序共有 20 条指令，其中第 15 条指令启动 D 工作。若 CPU 需从 D 读取 1000 个字符，则完成这一任务所需时间大约是多少个时钟周期？CPU 用于完成这一任务的时间大约是多少个时钟周期？在中断响应阶段 CPU 进行了哪些操作？
45
某计算机采用页式虚拟存储管理方式，按字节编址，虚拟地址为 32 位，物理地址为 24 位，页大小为 8KB；TLB 采用全相联映射；Cache 数据区大小为 64KB，按 2 路组相联方式组织，主存块大小为 64B。存储访问过程的示意图如下。
请回答下列问题。
(1) 图中字段 A～G 的位数各是多少？TLB 标记字段 B 中存放的是什么信息？
(2) 将块号为 4099 的主存块装入到 Cache 中时，所映射的 Cache 组号是多少？对应的 H 字段内容是什么？
(3) Cache 缺失处理的时间开销大还是缺页处理的时间开销大？为什么？
(4) 为什么 Cache 可以采用直写 (Write Through) 策略，而修改页面内容时总是采用回写 (Write Back) 策略？
操作系统
46
某进程调度程序采用基于优先数 (priority) 的调度策略，即选择优先数最小的进程运行，进程创建时由用户指定一个 nice 作为静态优先数。为了动态调整优先数，引入运行时间 cpuTime 和等待时间 waitTime，初值均为 0。进程处于执行态时，cpuTime 定时加 1，且 waitTime 置 0；进程处于就绪态时，cpuTime 置 0，waitTime 定时加 1。请回答下列问题。
(1) 若调度程序只将 nice 的值作为进程的优先数，即 priority=nice，则可能会出现饥饿现象，为什么？
(2) 使用 nice、cpuTime 和 waitTime 设计一种动态优先数计算方法，以避免产生饥饿现象，并说明 waitTime 的作用。
47
某磁盘文件系统使用链接分配方式组织文件，簇大小为 4KB。目录文件的每个目录项包括文件名和文件的第一个簇号，其他簇号存放在文件分配表 FAT 中。
(1) 假定目录树如下图所示，各文件占用的簇号及顺序如下表所示，其中 dir、dir1 是目录，file1、file2 是用户文件。请给出所有目录文件的内容。
(2) 若 FAT 的每个表项仅存放簇号，占 2 个字节，则 FAT 的最大长度为多少字节？该文件系统支持的文件长度最大是多少？
(3) 系统通过目录文件和 FAT 实现对文件的按名存取，说明 file1 的 106、108 两个簇号分别存放在 FAT 的哪个表项中。
(4) 假设仅 FAT 和 dir 目录文件已读入内存，若需将文件 dir/dir1/file1 的第 5000 个字节读入内存，则要访问哪几个簇？