这是本节的多页打印视图。点击此处打印.

408历年真题

本节包含历年 408 真题，希望可以为你带来帮助！

1: 2009 年 408 真题
2: 2010 年 408 真题
3: 2011 年 408 真题
4: 2012 年 408 真题
5: 2013 年 408 真题
6: 2014 年 408 真题
7: 2015 年 408 真题
8: 2016 年 408 真题
9: 2017 年 408 真题
10: 2018 年 408 真题
11: 2019 年 408 真题
12: 2020 年 408 真题
13: 2021 年 408 真题
14: 2022 年 408 真题
15: 2023 年 408 真题
16: 2024 年 408 真题
17: 2025 年 408 真题
18: 2026 年 408 真题
19: 408 其他资源

1 - 2009 年 408 真题

选择题

选择题答案速对

No.	Ans	No.	Ans	No.	Ans	No.	Ans	No.	Ans
1	B	2	C	3	D	4	B	5	C
6	B	7	A	8	D	9	A	10	B
11	C	12	D	13	D	14	C	15	D
16	C	17	A	18	A	19	D	20	B
21	D	22	A	23	D	24	D	25	C
26	A	27	C	28	B	29	A	30	A
31	B	32	A	33	B	34	B	35	C
36	A	37	D	38	D	39	C	40	A

数据结构

1

为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。

正确答案：B
缓冲区的概念出现在操作系统的设备管理中，其特点是先进先出。缓冲区的作用是解决主机与打印机之间速度不匹配的问题，而不应改变打印数据的顺序。若用栈，先进入缓冲区的数据则要排队到最后才能打印，显然不符题意，故选 B。

2

设栈 S 和队列 Q 的初始状态均为空，元素 a, b, c, d, e, f, g 依次进入栈 S 。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是 b, d, c, f, e, a, g，则栈 S 的容量至少是（）。

正确答案：C

由于队列的特点是先进先出，即栈 S 的出栈顺序就是队 Q 的出队顺序。故本题只需注意栈的特点是先进后出。出入栈的详细过程见下表。

序号	说明	栈内	栈外	序号	说明	栈内	栈外
1	a 入栈	A		8	e 入栈	ae	bdc
2	b 入栈	Ab		9	f 入栈	aef	bdc
3	b 出栈	A	b	10	f 出栈	ae	bdcf
4	c 入栈	Ac	b	11	e 出栈	a	bdcfe
5	d 入栈	Acd	b	12	a 出栈		bdcfea
6	d 出栈	Ac	bd	13	g 入栈	g	bdcfea
7	c 出栈	A	bdc	14	g 出栈		bdcfeag

栈内的最大深度为 3，故栈 S 的容量至少是 3。

【另解】元素的出栈顺序是 b,d,c,f,e,a,g，可推出进栈出栈顺序为 Push(S,a), Push(S,b), Pop(S,b), Push(S,c), Push(S,d), Pop(S,d), Pop(S,c), Push(S,e), Push(S,f), Pop(S,f), Pop(S,e), Pop(S,a), Push(S,g), Pop(S,g)。假设初始所需容量为 0，每做一次 Push 进行一次“+1”操作，每做一次 Pop 进行一次“-1”操作，记录容量的最大值为 3，所以选 C。

3

给定二叉树如右图所示。设 N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树。若遍历后的结点序列是 3，1，7，5，6，2，4，则其遍历方式是（）。

正确答案：D
分析遍历后的结点序列，可以看出根结点是在中间访问，而右子树结点在左子树之前，即遍历的方式是 RNL。本题考查的遍历方法并不是二叉树的 3 种基本遍历方式，对于考生而言，重要的是要掌握遍历的思想。

4

下列二叉排序树中，满足平衡二叉树定义的是（）。

正确答案：B
根据 AVL 的定义有，任意结点的左、右子树高度差的绝对值不超过 1。而其余 3 个选项均可以找到不符合该条件的结点。在做题过程中，如果答案不太明显，可以把每个非叶结点的平衡因子都写出来再进行判断。

5

已知一棵完全二叉树的第 6 层（设根为第 1 层）有 8 个叶结点，则该完全二叉树的结点个数最多是（）。

正确答案：C
完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层有叶结点。第 6 层有叶结点则完全二叉树的高度可能为 6 或 7，显然树高为 7 时结点更多。若第 6 层上有 8 个叶结点，则前六层为满二叉树，而第 7 层缺失了 8×2=16 个叶结点，故完全二叉树的结点个数最多为

(2^{7} - 1) - 16 = 111

个结点。

6

将森林转换为对应的二叉树，若在二叉树中，结点 u 是结点 v 的父结点的父结点，则在原来的森林中，u 和 v 可能具有的关系是（）。

I. 父子关系

II. 兄弟关系

III. u 的父结点与 v 的父结点是兄弟关系

正确答案：B

森林与二叉树的转换规则为“左孩子右兄弟”。在最后生成的二叉树中，父子关系在对应森林关系中可能是兄弟关系或原本就是父子关系。

情形 I：若结点 V 是结点 u 的第二个孩子结点，在转换时，结点 V 就变成结点 u 第一个孩子的右孩子，符合要求。

情形 II：结点 u 和 V 是兄弟结点的关系，但二者之中还有一个兄弟结点 k, 则转换后，结点 V 就变为结点 k 的右孩子，而结点 k 则是结点 u 的右孩子，符合要求。

情形 III: 若结点 u 的父结点与 v 的父结点是兄弟关系，则转换后，结点 u 和 v 分别在两者最左父结点的两棵子树中，不可能出现在同一条路径中。

【逆向法】由题意可知 u 是 v 的父结点的父结点，如下图所示有 4 种情况：

根据树与二叉树的转换规则，将这 4 种情况转换成树种结点的关系。(1) 在原来的树中 u 是 v 的父结点的父结点； (2) 在树中 u 是 v 的父结点； (3) 在树中 u 是 v 的父结点的兄弟； (4) 在树中 u 与 v 是兄弟关系。由此可知 I 和 II 正确。

7

下列关于无向连通图特性的叙述中，正确的是（）。

I. 所有顶点的度之和为偶数

II. 边数大于顶点个数减 1

III. 至少有一个顶点的度为 1

正确答案：A
每条边都连接了两个结点，在计算顶点的度之和时每条边在它的两个端点上各被计算一次，故所有顶点的度之和为边数的两倍，一定是偶数，I 正确。n 个顶点、n-1 条边可以构成无向连通图，比如树，II 错误。顶点数 N≥3 的无向完全图中每个顶点的度均为 N-1≥2，不存在度为 1 的顶点，III 错误（注意举反例时必须取 N≥3：N=2 的完全图

K_{2}

两个顶点的度恰好都是 1，不能作为反例）。

8

下列叙述中，不符合 m 阶 B 树定义要求的是（）。

正确答案：D
选项 A、B 和 C 都是 B-树的特点，而选项 D 则是 B+ 树的特点。注意区别 B-树和 B+ 树各自的特点。

9

已知关键字序列 5，8，12，19，28，20，15，22 是小根堆（最小堆），插入关键字 3，调整后得到的小根堆是（）。

正确答案：A

根据关键字序列得到的小根堆的二叉树形式如下图所示。

插入关键字 3 时，先将其放在小顶堆的末端，如图 (2) 所示。再将该关键字向上进行调整，得到的结果如图 (3) 所示。所以，调整后的小顶堆序列为 3, 5, 12, 8, 28, 20, 15, 22, 19。

10

若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（）。

正确答案：B
本题考查各种内部排序算法的特点。对于冒泡排序和选择排序，每一趟都能确定一个元素的最终位置，而题目中，前 2 个元素和后 2 个元素均不是最小或最大的 2 个元素并按序排列。选项 D 中的 2 路归并排序，第一趟排序结束都可以得到若干个有序子序列，而此时的序列中并没有两两元素有序排列。插入排序在每趟排序后能确定前面的若干元素是有序的，而此时第二趟排序后，序列的前三个元素是有序的，符合其特征。

组成原理

11

冯•诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU 区分它们的依据是（）。

正确答案：C
虽然在冯诺依曼结构中指令和数据都是以二进制形式存放在存储器中，但 CPU 可以根据指令周期的不同阶段来区分是指令还是数据，通常在取指阶段取出的是指令，在执行阶段取出的是数据。本题容易误选 A，需要清楚的是，CPU 只有在确定取出的是指令之后，才会将其操作码送去译码，因此，不可能依据译码的结果来区分指令和数据。

12

一个 C 语言程序在一台 32 位机器上运行。程序中定义了三个变量 x，y 和 z，其中 x 和 z 是 int 型，y 为 short 型。当 x=127，y=-9 时，执行赋值语句 z=x+y 后，x、y 和 z 的值分别是：

正确答案：D

C 语言中的整型数据为补码表示，int 为 32 位，short 为 16 位，故 x、y 转换成十六进制为 0000007FH、FFF7H。执行 z=x+y 时，由于 x 是 int 型，y 为 short 型，需将短字长数据转换成长字长数据，称之为“符号扩展”。由于 y 的符号位为 1，故在 y 的前面添加 16 个 1，即可将 y 上升为 it 型，其十六进制形式为 FFFFFFF7H。最后执行加法，即 O0OO007FH+FFFFFFF7H=00000076H，其中最高位的进位 1 自然丢弃。故选 D。

【排除法】对于 x 的值，4 个选项都一样，无须计算；z=x+y=127-9=118>0，前 4 个字节必然全 0，排除 BC；只需算出 y=-9 的值即可，其十六进制形式为 FFF7H，排除 A。

【提示】解题时，应先排除明显错误的选项，然后再推敲剩下的选项。

13

浮点数加、减运算过程一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为 5 位和 7 位（均含 2 位符号位）。若有两个数 X=2⁷×29/32，Y=2⁵×5/8，则用浮点加法计算 X+Y 的最终结果是（）。

正确答案：D

本题考查浮点数加减。X 的浮点数格式为 00,111;00,11101（分号前为阶码，分号后为尾数），Y 的浮点数格式为 00,101;00,10100。然后根据浮点数的加法步骤进行运算。

第一步：对阶。X、Y 阶码相减，即 00,111-00,101 = 00,111+11,0111 = 00,010，可知 X 的阶码比 Y 的阶码大 2（这一步可直接目测）。根据小阶向大阶看齐的原则，将 Y 的阶码加 2，尾数右移 2 位，将 Y 变为 00,111；00,00101。

第二步：尾数相加。即 00,11101+00,00101 = 01,00010，尾数相加结果符号位为 01，故需右规。

第三步：规格化。将尾数右移 1 位，阶码加 1，得 X+Y 为 01,000;00,10001。

第四步：判溢出。阶码符号位为 01，说明发生溢出。

本题容易误选选项 B、C, 这是因为选项 B、C 本身并没有计算错误，只是它们不是最终结果，选项 B 少了第 3 步和第 4 步，选项 C 少了第 4 步。

【偷懒法】本题也可以直接用数学知识对原数进行计算，然后将计算的结果转换成浮点数的格式。X+Y = $29/32 \times 2^{7} + 5/8 \times 2^{5} = 29/32 \times 2^{7} + 5/32 \times 2^{7} = (29/32 + 5/32) \times 2^{7} = 34/32 \times 2^{7} = 17/32 \times 2^{8}$ ，阶码用补码表示，数值位 3 位，最大只能表示 7，即 X+Y 的结果的阶码 8 超出了该浮点数的表示范围，故溢出。

14

某计算机的 Cache 共有 16 块，采用 2 路组相联映射方式（即每组 2 块）。每个主存块大小为 32 字节，按字节编址。主存 129 号单元所在主存块应装入到的 Cache 组号是（）。

正确答案：C
由于 Cache 共有 16 块，采用 2 路组相联，因此共分为 8 组，组号为 0,1,2，…，7。主存的某一字块按模 8 映射到 Cache 某组的任一字块中，即主存的第 0,8，l6,…字块可以映射到 Cache 第 0 组的任一字块中。每个主存块大小为 32 字节，故 129 号单元位于第 4 块主存块（注意是从 0 开始），因此将映射到 Cache 第 4 组的任一字块中。

15

某计算机主存容量为 64KB，其中 ROM 区为 4KB，其余为 RAM 区，按字节编址。现要用 2K×8 位的 ROM 芯片和 4K×4 位的 RAM 芯片来设计该存储器，则需要上述规格的 ROM 芯片数和 RAM 芯片数分别是（）。

正确答案：D
本题考查主存容量的扩展。首先确定 ROM 的个数，ROM 区为 4KB, 选用 2K×8 位的 ROM 芯片，需要 4Kx8 / 2K×8 =2 片，采用字扩展方式：RAM 区为 60KB, 选用 4Kx4 位的 RAM 芯片，需要 60K×8 /4K×4 = 30 片，采用字和位同时扩展方式。

16

某机器字长 16 位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第一字节为操作码字段，第二字节为相对位移量字段。假定取指令时，每取一个字节 PC 自动加 1。若某转移指令所在主存地址为 2000H，相对位移量字段的内容为 06H，则该转移指令成功转移后的目标地址是（）。

正确答案：C

相对寻址 EA = (PC)+A，首先要求的是取指令后 PC 的值。转移指令由两个字节组成，每取一个字节 PC 值自动加 1，因此取指令后 PC 值为 2000H+2H = 2002H, 故 EA = (PC)+A = 2002H+06H = 2008H。

【易错点】本题易误选 A 或 B。选项 A 没有考虑 PC 值的自动更新，选项 B 虽然考虑了 PC 值要自动更新，但没有注意到该转移指令是一条两字节指令，PC 值仅仅“+1”而不是“+2”。

17

下列关于 RISC 的叙述中，错误的是（）。

正确答案：A
相对于 CISC，RISC 的特点是指令条数少；指令长度固定，指令格式和寻址种类少：只有取数/存数指令访问存储器，其余指令的操作均在寄存器之间进行；CPU 中通用寄存器多；大部分指令在一个或者小于一个机器周期内完成；以硬布线逻辑为主，不用或者少用微程序控制。选项 B、C、D 都是 RISC 的特点，选项 A 是错误的，因为 RISC 的速度快，所以普遍采用硬布线控制器，而非微程序控制器。

18

某计算机的指令流水线由四个功能段组成，指令流经各功能段的时间（忽略各功能段之间的缓存时间）分别为 90 ns、80 ns、70 ns、和 60 ns，则该计算机的 CPU 时钟周期至少是（）。

正确答案：A
流水线的时钟周期应以最长的执行时间为准，否则用时长的流水段的功能将不能正确完成。

19

相对于微程序控制器，硬布线控制器的特点是（）。

正确答案：D
微程序控制器采用了“存储程序”的原理，每条机器指令对应一个微程序，因此修改和扩充容易，灵活性好，但每条指令的执行都要访问控制存储器，所以速度慢。硬布线控制器采用专门的逻辑电路实现，其速度主要取决于逻辑电路的延迟，因此速度快，但修改和扩展困难，灵活性差。

20

假设某系统总线在一个总线周期中并行传输 4 字节信息，一个总线周期占用 2 个时钟周期，总线时钟频率为 10MHz，则总线带宽是（）。

正确答案：B
总线带宽是指单位时间内总线上传输数据的位数，通常用每秒钟传送信息的字节数来衡量，单位 Bs。由题意可知，在 1 个总线周期（=2 个时钟周期）内传输了 4 字节信息，时钟周期=1/10MHz=0.1μs，故总线带宽为 4B/(2×0.1μs)=4B/(0.2×10⁻⁶s)=20MB/s。

21

假设某计算机的存储系统由 Cache 和主存组成，某程序执行过程中访存 1000 次，其中访问 Cache 缺失（未命中）50 次，则 Cache 的命中率是（）。

正确答案：D
命中率 = Cache 命中次数/总访问次数。需要注意的是看清题，题中说明的是缺失 50 次，而不是命中 50 次，仔细审题是做对题的第一步。

22

下列选项中，能引起外部中断的事件是（）。

正确答案：A
外部中断指的是 CPU 执行指令以外的事件产生的中断，通常是指来自 CPU 与内存以外的中断。A 中键盘输入属于外部事件，每次键盘输入 CPU 都需要执行中断以读入输入数据，所以能引起外部中断。B 中除数为 0 属于异常，也就是内中断，发生在 CPU 内部。C 中浮点运算下溢将按机器零处理，不会产生中断。而 D 访存缺页属于 CPU 执行指令时产生的中断，也不属于外部中断。所以能产生外部中断的只能是输入设备键盘。

操作系统

23

单处理机系统中，可并行的是（）。

Ⅰ. 进程与进程 Ⅱ. 处理机与设备 Ⅲ. 处理机与通道 Ⅳ. 设备与设备

正确答案：D
在单处理机系统（不包含多核的情况）中，同一时刻只能有一个进程占用处理机，因此进程之间不能并行执行。通道是独立于 CPU 的控制输入／输出的设备，两者可以并行，显然，设备与设备之间也是可以并行的。

24

下列进程调度算法中，综合考虑进程等待时间和执行时间的是（）。

正确答案：D
在最高响应比优先算法中，选出响应比最高的进程投入执行，响应比 R 定义如下：响应比 R = (等待时间＋执行时间) / 执行时间。它综合考虑了每个进程的等待时间和执行时间，对于同时到达的长进程和短进程，短进程会优先执行，以提高系统吞吐量；而长进程的响应比可以随等待时间的增加而提高，不会产生进程无法调度的情况。

25

某计算机系统中有 8 台打印机，由 K 个进程竞争使用，每个进程最多需要 3 台打印机。该系统可能会发生死锁的 K 的最小值是（）。

正确答案：C
这种题用到组合数学中鸽巢原理的思想。考虑最极端情况，因为每个进程最多需要 3 台打印机，如果每个进程已经占有了 2 台打印机，那么只要还有多的打印机，总能满足一个进程达到 3 台的条件，然后顺利执行，所以将 8 台打印机分给 K 个进程，每个进程有 2 台打印机，这个情况就是极端情况，K 为 4。

26

分区分配内存管理方式的主要保护措施是（）。

正确答案：A
每个进程都拥有自己独立的内存空间，若一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界，因此需要进行界地址保护，即当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生地址越界中断。

27

一个分段存储管理系统中，地址长度为 32 位，其中段号占 8 位，则最大段长是（）。

正确答案：C
段式管理的逻辑地址分为段号和位移量两部分，段内位移的最大值就是最大段长。地址长度为 32 位，段号占 8 位，则位移量占 32-8=24 位，故最大段长为

2^{24}

B。

28

下列文件物理结构中，适合随机访问且易于文件扩展的是（）。

正确答案：B
文件的物理结构包括连续、链式、索引三种，其中链式结构不能实现随机访问，连续结构的文件不易于扩展。因此随机访问且易于扩展是索引结构的特性。

29

假设磁头当前位于第 105 道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为 35，45，12，68，110，180，170，195，采用 SCAN 调度（电梯调度）算法得到的磁道访问序列是（）。

正确答案：A
SCAN 算法类似电梯的工作原理。首先，当磁头从 105 道向序号增加的方向移动时，便会按照从小到大的顺序服务所有大于 105 的磁道号 (110,170,180,195)；往回移动时又会按照从大到小的顺序进行服务 (68, 45,35, 12)。

30

文件系统中，文件访问控制信息存储的合理位置是（）。

正确答案：A
为了实现“按名存取”，在文件系统中为每个文件设置用于描述和控制文件的数据结构，称之为文件控制块 (FCB )。在文件控制块中，通常包含以下三类信息，即基本信息、存取控制信息及使用信息。

31

设文件 F1 的当前引用计数值为 1，先建立 F1 的符号链接（软链接）文件 F2，再建立 F1 的硬链接文件 F3，然后删除 F1。此时，F2 和 F3 的引用计数值分别是（）。

正确答案：B

符号链接是一个单独的文件，创建时它的引用计数值为 1；建立硬链接时，源文件引用计数值加 1。删除文件时，删除操作对于符号链接是不可见的，这并不影响文件系统，当以后再通过符号链接访问时，发现文件不存在，直接删除符号链接；但对于硬链接则不可以直接删除，引用计数值减 1, 若值不为 0, 则不能删除此文件，因为还有其他硬链接指向此文件。

当建立 F2 时，Fl 和 F2 的引用计数值都为 1。当再建立 F3 时，Fl 和 F3 的引用计数值就都变成了 2。当后来删除 Fl 时，F3 的引用计数值为 2-1 = 1, F2 的引用计数值一直不变。

32

程序员利用系统调用打开 I/O 设备时，通常使用的设备标识是（）。

正确答案：A
设备管理具有设备独立性的特点，操作系统以系统调用方式来请求某类设备时，使用的是逻辑设备名。而在程序实际执行时，将逻辑设备名转换为对应的物理设备名。

计算机网络

33

在 OSI 参考模型中，自下而上第一个提供端到端服务的层次是（）。

正确答案：B
传输层提供应用进程间的逻辑通信（通过端口号），即端到端的通信。而数据链路层负责相邻结点之间的通信，这个结点包括了交换机和路由器等数据通信设备，这些设备不能称为端系统。网络层负责主机到主机的逻辑通信。因此选 B。

34

在无噪声情况下，若某低通通信链路的带宽为 3kHz，采用 4 个相位，每个相位具有 4 种振幅的 QAM 调制技术，则该通信链路的最大数据传输速率是（）。

正确答案：B
采用 4 个相位，每个相位有 4 种幅度的 QAM 调制方法，每个信号可以有 16 种变化，传输 4bit 的数据。根据奈奎斯特定理，信息的最大传输速率为 2×3k×4=24kbps。

35

数据链路层采用后退 N 帧（GBN）协议，发送方已经发送了编号为 0~7 的帧。当计时器超时时，若发送方只收到 0、2、3 号帧的确认，则发送方需要重发的帧数是（）。

正确答案：C
在回退 N 帧中，当接收方检测到某个帧出错后，则简单地丢弃该帧及其后所有的后续帧，发送方超时后需重传该数据帧及其后续的所有帧。这里应注意，连续 ARQ 协议中，接收方一般采用累积确认的方式，即接收方对按序到达的最后一个分组发送确认，因此本题中收到 3 的确认帧就表示编号为 0,1,2,3 的帧已接收，而此时发送方未收到 1 号帧的确认只能代表确认帧在返回的过程中丢失了，而不代表 1 号帧未到达接收方。因此需要重传的帧为编号是 4,5,6， 7 的帧。

36

以太网交换机进行转发决策时使用的 PDU 地址是（）。

正确答案：A
交换机实质上是一个多端口网桥，工作在数据链路层，数据链路层使用物理地址进行转发，而转发到目的地通常是使用目的地址。因此 POU 地址是目的物理地址。

37

在一个采用 CSMA/CD 协议的网络中，传输介质是一根完整的电缆，传输速率为 1Gbps，电缆中的信号传播速度是 200 000km/s。若最小数据帧长度减少 800 比特，则最远的两个站点之间的距离至少需要（）。

正确答案：D

本题考查 CSMA/CD 的限制条件。若最短帧长减少，而数据传输速率不变，则需要使冲突域的最大距离变短来实现碰撞窗口的减少。碰撞窗口是指网络中收发结点间的往返时延，因此假设需要减少的最小距离为 S, 则可以得到如下公式（注意单位的转换）：

减少的往返时延=减少的发送时延，即 $2 \times [s / (2 \times 1 0^{8})] = 800/ (1 \times 1 0^{9})$ 。即，由于帧长减少而缩短的发送时延，应等于由于距离减少而缩短的传播时延的 2 倍。

可得 s=80, 即最远的两个站点之间的距离最少需要减少 80m。

【注意】CSMA/CD 的碰撞窗口 = 2 倍传播时延，报文发送时间 » 碰撞窗口。

38

主机甲与主机乙之间已建立一个 TCP 连接，主机甲向主机乙发送了两个连续的 TCP 段，分别包含 300 字节和 500 字节的有效载荷，第一个段的序列号为 200，主机乙正确接收到两个段后，发送给主机甲的确认序列号是（）。

正确答案：D
返回的确认序列号是接收端期待收到对方下一个报文段数据部分的第一个字节的序号，因此乙在正确接收到两个段后，返回给甲的确认序列号是 200+ 300 + 500 = 1000。

39

一个 TCP 连接总是以 1KB 的最大段长发送 TCP 段，发送方有足够多的数据要发送。当拥塞窗口为 16KB 时发生了超时，如果接下来的 4 个 RTT（往返时间）时间内的 TCP 段的传输都是成功的，那么当第 4 个 RTT 时间内发送的所有 TCP 段都得到肯定应答时，拥塞窗口大小是（）。

正确答案：C
在发生超时后，慢开始门限 ssthresh 变为 16KB/2 = 8KB，拥塞窗口变为 1KB。在接下来的 3 个 RTT 内，执行慢开始算法，拥塞窗口大小依次为 2KB、4KB、8KB，由于慢开始门限 ssthresh 为 8KB，因此之后转而执行拥塞避免算法，即拥塞窗口开始“加法增大”。因此第 4 个 RTT 结束后，拥塞窗口的大小为 9KB。

40

FTP 客户和服务器间传递 FTP 命令时，使用的连接是（）。

正确答案：A
对于 FTP 文件传输，为了保证可靠性，选择 TCP 协议，排除 C、D。FTP 的控制信息是带外传送的，也即 FTP 使用了一个分离的控制连接来传送命令，故选 A。

解答题

数据结构

41

带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：

① 设最短路径初始时仅包含初始顶点，令当前顶点 u 为初始顶点；

② 选择离 u 最近且尚未在最短路径中的一个顶点 v，加入到最短路径中，修改当前顶点 u=v；

③ 重复步骤②，直到 u 是目标顶点时为止。

请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。

42

已知一个带有表头结点的单链表，结点结构为：| data | link |

假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点（k 为正整数）。若查找成功，算法输出该结点的 data 域的值，并返回 1；否则，只返回 0。要求：

(1) 描述算法的基本设计思想；

(2) 描述算法的详细实现步骤；

(3) 根据设计思想和实现步骤，采用程序设计语言描述算法（使用 C、C++ 或 Java 语言实现），关键之处请给出简要注释。

1）算法的基本设计思想：

问题的关键是设计一个尽可能高效的算法，通过链表的一趟遍历，找到倒数第 k 个结点的位置。算法的基本设计思想：定义两个指针变量 p 和 q，初始时均指向头结点的下一个结点（链表的第一个结点）。p 指针沿链表移动，当 p 指针移动到第 k 个结点时，q 指针开始与 p 指针同步移动；当 p 指针移动到最后一个结点时，q 指针所指示结点为倒数第 k 个结点。以上过程对链表仅进行一遍扫描。

2）算法的详细实现步骤：

count=0，p 和 q 指向链表表头结点的下一个结点；
若 p 为空，转 5；
若 count 等于 k，则 q 指向下一个结点；否则，count=count+l;
p 指向下一个结点，转 2：
若 count 等于 k，则查找成功，输出该结点的 data 域的值，返回 1；否则，说明 k 值超过了线性表的长度，查找失败，返回 0；
算法结束。

3）算法实现

int FindElement(Node *head, int k) {
  Node *p1 = head;
  Node *p2 = head;
  for (int i = 0; i < k; i++) {
    p1 = p1->link;
    if (p1 == NULL) {
      return 0;
    }
  }
  // p1 != NULL
  while (p1 != NULL) {
    p1 = p1->link;
    p2 = p2->link;
  }
  printf("%d\n", p2->data);
  return 1;
}

提示：算法程序题，如果能够写出数据结构类型定义，正确的算法思想都会至少给一半以上分数，如果能用伪代码写出自然更好，比较复杂的地方可以直接用文字表达。

【评分说明】① 若所给出的算法采用一遍扫描方式就能得到止确结果，可给满分 15 分：若采用两遍或多遍扫描才能得到正确结果的，最高给 10 分；若采用递归算法得到正确结果的，最高给 10 分；若实现算法的空间复杂度过高（使用了大小与 k 有关的辅助数组），但结果正确，最高给 10 分；若实现的算法的空间复杂度过高（使用了大小与 k 有关的辅助数组），但结果正确，最高给 10 分。

②若在算法基本思想描述和算法步骤描述中因文学表达没有非常清晰地反映出算法的思路，但在算法实现中能够清晰看出算法思想和步骤且正确，按照 () 的标准给分。

③若考生的答案中算法基本思想描述、算法步骤描述或算法实现中部分正确，可酌情给分。

组成原理

43

某计算机的 CPU 主频为 500MHz，CPI 为 5（即执行每条指令平均需 5 个时钟周期）。假定某外设的数据传输率为 0.5MB/s，采用中断方式与主机进行数据传送，以 32 位为传输单位，对应的中断服务程序包含 18 条指令，中断服务的其他开销相当于 2 条指令的执行时间。请回答下列问题，要求给出计算过程。

(1) 在中断方式下，CPU 用于该外设 I/ O 的时间占整个 CPU 时间的百分比是多少？

(2) 当该外设的数据传输率达到 5M B/s 时，改用 DMA 方式传送数据。假定每次 DMA 传送块大小为 5000B，且 DMA 预处理和后处理的总开销为 500 个时钟周期，则 CPU 用于该外设 I/ O 的时间占整个 CPU 时间的百分比是多少？（假设 DMA 与 CPU 之间没有访存冲突）

44

某计算机字长 16 位，采用 16 位定长指令字结构，部分数据通路结构如下图所示，图中所有控制信号为 1 时表示有效、为 0 时表示无效。例如控制信号 MDRinE 为 1 表示允许数据从 DB 打入 MDR，MDRin 为 1 表示允许数据从内总线打入 MDR。假设 MAR 的输出一直处于使能状态。加法指令“ADD (R1)，R0”的功能为 (R0)+((R1)) → (R1)，即将 R0 中的数据与 R1 的内容所指主存单元的数据相加，并将结果送入 R1 的内容所指主存单元中保存。

下表给出了上述指令取指和译码阶段每个节拍（时钟周期）的功能和有效控制信号，请按表中描述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号。

时钟	功能	有效控制信号
C1	MAR ← (PC)	PCout, MARin
C2	MDR ← M(MAR) PC ← (PC) + 1	MemR, MDRinE, PC+1
C3	IR ← (MDR)	MDRout, IRin
C4	指令译码	无

题干已给出取值和译码阶段每个节拍的功能和有效控制信号，我们应以弄清楚取指阶段中数据通路的信息流动作为突破口，读懂每个节拍的功能和有效控制信号。然后应用到解题思路中，包括划分执行步骤、确定完成的功能、需要的控制信号。

先分析题干中提供的示例（本部分解题时不做要求）：

取指令的功能是根据 PC 的内容所指主存地址，取出指令代码，经过 MDR，最终送至 R。这部分和后面的指令执行阶段的取操作数、存运算结果的方法是相通的。

C1: (PC)→MAR

在读写存储器前，必须先将地址（这里为 PC）送至 MAR。

C2: M(MAR)→MDR, (PC)+1→PC

读写的数据必须经过 DR，指令取出后 PC 自增 1。

C3: (MDR)→IR

然后将读到 MDR 中指令代码送至 IR 进行后续操作。

指令 “ADD(R1),R0” 的操作数一个在主存中，一个在寄存器中，运算结果在主存中。根据指令功能，要读出 R1 的内容所指的主存单元，必须先将 R1 的内容送至 MAR，即 (R1)→MAR。而读出的数据必须经过 MDR，即 M(MAR)→MDR。

因此，将 R1 的内容所指主存单元的数据读出到 MDR 的节拍安排如下：

C5: (R1)→MAR

C6: M(MAR)→MDR

ALU 一端是寄存器 A，MDR 或 R0 中必须有一个先写入 A 中，如 MDR。

C7: (MDR)→A

然后执行加法操作，并将结果送入寄存器 AC。

C8: (A)+(R0)→AC

之后将加法结果写回到 R1 的内容所指主存单元，注意 MAR 中的内容没有改变。

C9: (AC)→MDR

C10: (MDR)→M(MAR)

有效控制信号的安排并不难，只需看数据是流入还是流出，如流入寄存器 X 就是 Xin，流出寄存器 X 就是 Xout。还需注意其他特殊控制信号，如 PC+1、Add 等。

于是得到参考答案如下：

时钟	功能	有效控制信号
C5	MAR ← (R1)	R1out, MARin
C6	MDR ← M(MAR)	MemR, MDRinE
C7	A ← (MDR)	MDRout, Ain
C8	AC ← (A) + (R0)	R0out, Add, ACin
C9	MDR ← (AC)	ACout, MDRin
C10	M(MAR) ← (MDR)	MDRoutE, MemW

本题答案不唯一，如果在 C6 执行 M(MAR)→MDR 的同时，完成 (R0) → A（即选择将 (R0) 写入 A），并不会发生总线冲突，这种方案可节省 1 个节拍，见下表：

时钟	功能	有效控制信号
C5	MAR ← (R1)	R1out, MARin
C6	MDR ← M(MAR), A ← (R0)	MemR, MDRinE, R0out, Ain
C7	AC ← (MDR) + (A)	MDRout, Add, ACin
C8	MDR ← (AC)	ACout, MDRin
C9	M(MAR) ← (MDR)	MDRoutE, MemW

操作系统

45

三个进程 $P_{1}$ 、 $P_{2}$ 、 $P_{3}$ 互斥使用一个包含 $N (N > 0)$ 个单元的缓冲区。 $P_{1}$ 每次用 produce() 生成一个正整数并用 put() 送入缓冲区某一空单元中； $P_{2}$ 每次用 getodd() 从该缓冲区中取出一个奇数并用 countodd() 统计奇数个数； $P_{3}$ 每次用 geteven() 从该缓冲区中取出一个偶数并用 counteven() 统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。

46

请求分页管理系统中，假设某进程的页表内容如下表所示：

页号	页框（Page Frame）号	有效位（存在位）
0	101H	1
1		0
2	254H	1

页面大小为 4KB，一次内存的访问时间是 100ns，一次快表（TLB）的访问时间是 10ns，处理一次缺页的平均时间 10⁸ ns（已含更新 TLB 和页表的时间），进程的驻留集大小固定为 2，采用最近最少使用置换算法 (LRU) 和局部淘汰策略。假设

① TLB 初始为空；

② 地址转换时先访问 TLB，若 TLB 未命中，再访问页表（忽略访问页表之后的 TLB 更新时间）；

③ 有效位为 0 表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。

设有虚地址访问序列 2362H、1565H、25A5H，请问：

(1) 依次访问上述三个虚地址，各需多少时间？给出计算过程。

(2) 基于上述访问序列，虚地址 1565H 的物理地址是多少？请说明理由。

计算机网络

47

某网络拓扑如下图所示，路由器 R1 通过接口 E1、E2 分别连接局域网 1、局域网 2，通过接口 L0 连接路由器 R2，并通过路由器 R2 连接域名服务器与互联网。R1 的 L0 接口的 IP 地址是 202.118.2.1；R2 的 L0 接口的 IP 地址是 202.118.2.2，L1 接口的 IP 地址是 130.11.120.1，E0 接口的 IP 地址是 202.118.3.1；域名服务器的 IP 地址是 202.118.3.2。

R1 和 R2 的路由表结构为：

(1) 将 IP 地址空间 202.118.1.0/24 划分为 2 个子网，分别分配给局域网 1、局域网 2，每个局域网需分配的 IP 地址数不少于 120 个。请给出子网划分结果，说明理由或给出必要的计算过程。

(2) 请给出 R1 的路由表，使其明确包括到局域网 1 的路由、局域网 2 的路由、域名服务器的主机路由和互联网的路由。

(3) 请采用路由聚合技术，给出 R2 到局域网 1 和局域网 2 的路由。

(1) CIDR 中的子网号可以全 0 或全 1，但主机号不能全 0 或全 1。

因此若将 IP 地址空间 202.118.1.0/24 划分为 2 个子网，且每个局域网需分配的 IP 地址个数不少于 120 个，子网号至少要占用一位。

由 $2^{6} - 2 < 120 < 2^{7} - 2$ 可知，主机号至少要占用 7 位。

由于源 IP 地址空间的网络前缀为 24 位，因此主机号位数 + 子网号位数 = 8。

综上可得主机号位数为 7，子网号位数为 1。

因此子网的划分结果为子网 1：202.118.1.0/25，子网 2：202.118.1.128/25。

地址分配方案：子网 1 分配给局域网 1，子网 2 分配给局域网 2；或子网 1 分配给局域网 2，子网 2 分配给局域网 1。

(2) 由于局域网 1 和局域网 2 分别与路由器 R1 的 E1、E2 接口直接相连，因此在 R1 的路由表中，目的网络为局域网 1 的转发路径是直接通过接口 E1 转发的，目的网络为局域网 2 的转发路径是直接通过接口 E1 转发的。由于局域网 1、2 的网络前缀均为 25 位，因此它们的子网掩码均为 255.255.255.128。

R1 专门为域名服务器设定了一个特定的路由表项，因此该路由表项中的子网掩码应为 255.255.255.255（只有和全 1 的子网掩码相与才能完全保证和目的 P 地址一样，从而选择该特定路由）。对应的下一跳转发地址是 202.118.2.2，转发接口是 L0。

R1 到互联网的路由实质上相当于一个默认路由，默认路由一般写为 0/0，即目的地址为 0.0.0.0，子网掩码为 0.0.0.0。对应的下一跳转发地址是 202.118.2.2，转发接口是 L0。

综上可得到路由器 R1 的路由表如下。

若子网 1 分配给局域网 1，子网 2 分配给局域网 2，见下表。

目的网络 IP 地址	子网掩码	下一跳 IP 地址	接口
202.118.1.0	255.255.255.128		E1
202.118.1.128	255.255.255.128		E2
202.118.3.2	255.255.255.255	202.118.2.2	L0
0.0.0.0	0.0.0.0	202.118.2.2	L0

若子网 1 分配给局域网 2, 子网 2 分配给局域网 1, 见下表。

目的网络 IP 地址	子网掩码	下一跳 IP 地址	接口
202.118.1.128	255.255.255.128		E1
202.118.1.0	255.255.255.128		E2
202.118.3.2	255.255.255.255	202.118.2.2	L0
0.0.0.0	0.0.0.0	202.118.2.2	L0

(3) 局域网 1 和局域网 2 的地址可以聚合为 202.118.1.0/24，而对于路由器 R2 来说，通往局域网 1 和局域网 2 的转发路径都是从 L0 接口转发，因此采用路由聚合后，路由器 R2 到局域网 1 和局域网 2 的路由，见下表：

目的网络IP地址	子网掩码	下一跳IP地址	接口
202.118.1.0	255.255.255.0	202.118.2.1	L0

2 - 2010 年 408 真题

选择题

选择题答案速对

No.	Ans	No.	Ans	No.	Ans	No.	Ans	No.	Ans
1	D	2	C	3	D	4	C	5	B
6	A	7	C	8	B	9	B	10	D
11	A	12	D	13	B	14	B	15	D
16	A	17	D	18	B	19	A	20	D
21	A	22	D	23	A	24	C	25	B
26	A	27	D	28	B	29	B	30	C
31	C	32	B	33	C	34	C	35	D
36	C	37	B	38	D	39	A	40	A

数据结构

1

若元素 a, b, c, d, e, f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。

正确答案：D

本题考查入栈出栈序列。

选项 A 可由 in,in,in,in,out,out,in,out,out,in,ot,out 得到；
选项 B 可由 in,in,in,out,out,in,out,out,in,out,in,out 得到；
选项 C 可由 in,in,out,in,out,out,in,in,out,in,out,out 得到；
选项 D 可由 in,out,in,in,in,in,in,out,out,out,out,out 得到，

但题意要求不允许连续三次退栈操作，故 D 不可能得到。

【另解】先进栈的元素后出栈，进栈顺序为 a,b,c,d,e,f，故连续出栈时的序列必然是按字母表逆序的，若出栈序列中出现了长度大于等于 3 的连续逆序子序列，侧为不符合要求的出栈序列。

2

某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，若元素 a, b, c, d, e 依次入此队列后再进行出队操作，则不可能得到的出队序列是（）。

正确答案：C

本题的队列实质是输出受限的双端队列（两端入队、一端出队）。
依次入队的元素为 a、b、c、d、e，各选项的可行性及对应入队方案如下：

A 可行
a 左入（或右入） → b 左入 → c 右入 → d 右入 → e 右入
队列状态（队首→队尾）：b, a, c, d, e
出队序列：b, a, c, d, e ✅
B 可行
a 左入（或右入） → b 左入 → c 右入 → d 左入 → e 右入
队列状态：d, b, a, c, e
出队序列：d, b, a, c, e ✅
D 可行
a 左入（或右入） → b 左入 → c 左入 → d 右入 → e 左入
队列状态：e, c, b, a, d
出队序列：e, c, b, a, d ✅
C 不可能
不管 a 从左还是右入队，b 紧接着入队后一定与 a 相邻。
要得到 d, b, c, a, e，d 必须第一个出队，所以 d 只能从队首方向插入，处于 a、b 的外侧。
当 d 出队、接着 b 出队后，队列中只剩 a（及其后可能入队的元素）。
此时无论 c 是在 b 出队前还是之后入队，从两端插入都无法使 c 出现在 b 和 a 之间，也就无法形成 b, c, a 的出队顺序。
因此该序列不可能。 ❌

3

下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（）。

正确答案：D
题中所给二叉树的后序序列为 d,b,c,a。结点 d 无前驱和左子树，左链域空，无右子树，右链域指向其后继结点 b；结点 b 无左子树，左链域指向其前驱结点 d；结点 c 无左子树，左链域指向其前驱结点 b，无右子树，右链域指向其后继结点 a。故选 D。

4

在下图所示的平衡二叉树中，插入关键字 48 后得到一棵新平衡二叉树。在新平衡二叉树中，关键字 37 所在结点的左、右子结点中保存的关键字分别是（）。

正确答案：C

插入 48 以后，该 AVL 根结点的平衡因子由 -1 变为 -2, 在最小不平衡子树根结点的右子树 (R) 的左子树 (L) 中插入新结点引起的不平衡属于 RL 型平衡旋转，需要做两次旋转操作（先右旋后左旋）。

调整后，关键字 37 所在结点的左、右子结点中保存的关键字分别是 24、53。

5

在一棵度数为 4 的树 T 中，若有 20 个度为 4 的结点，10 个度为 3 的结点，1 个度为 2 的结点，10 个度为 1 的结点，则树 T 的叶结点个数是（）。

正确答案：B
设树中度为 i（i=0,1,2,3,4）的结点数分别为

N_{i}

, 树中结点总数为 N，则树中各结点的度之和等于 N-1，即

N = 1 + N_{1} + 2 N_{2} + 3 N_{3} + 4 N_{4} = N_{0} + N_{1} + N_{2} + N_{3} + N_{4}

，根据题设中的数据，即可得到

N_{0} = 82

,即树 T 的叶结点的个数是 82。

6

对 n (n≥2) 个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是（）。

正确答案：A
哈夫曼树为带权路径长度最小的二叉树，不一定是完全二叉树。哈夫曼树中没有度为 1 的结点，B 正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左、右子树构造一棵新的二叉树，C 正确；哈夫曼树中任一非叶结点 P 的权值为其左、右子树根结点权值之和，其权值不小于其左、右子树根结点的权值，在与结点 P 的左、右子树根结点处于同一层的结点中，若存在权值大于结点 P 权值的结点 Q，则结点 Q 的兄弟结点中权值较小的一个应该与结点 P 作为左、右子树构造新的二叉树。综上可知，哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。

7

若无向图 G=(V,E) 中含有 7 个顶点，要保证图 G 在任何情况下都是连通的，则需要的边数最少是（）。

正确答案：C
要保证无向图 G 在任何情况下都是连通的，即任意变动图 G 中的边，G 始终保持连通，首先需要 G 的任意 6 个结点构成完全连通子图 G1，需 n(n-1)/2 = 6×(6-1)/2 = 15 条边，然后再添条边将第 7 个结点与 G1 连接起来，共需 16 条边。

8

对下图进行拓扑排序，可以得到不同拓扑序列的个数是（）。

正确答案：B

拓扑排序的过程如下图所示：

可以得到 3 个不同的拓扑序列，分别为 abced、abecd、aebcd。

9

已知一个长度为 16 的顺序表 L，其元素按关键字有序排列。若采用折半查找法查找一个 L 中不存在的元素，则关键字的比较次数最多是（）。

正确答案：B
折半查找在查找成功时进行的关键字比较次数最多为

⌊ l o g_{2} n ⌋ + 1

，即判定树的高度；折半查找法在查找不成功时进行的关键字比较次数最多为

⌊ l o g_{2} n ⌋ + 1

。题中

n = 16

,因此最多比较

⌊ l o g_{2} 16 ⌋ + 1 = 5

次。也可以画出草图求解。

10

采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（）。

正确答案：D

快速排序的递归次数与元素的初始排列有关。若每次划分后分区比较平衡，则递归次数少；若划分后分区不平衡，则递归次数多。但快速排序的递归次数与分区处理顺序无关，即先处理较长的分区或先处理较短的分区都不影响递归次数。

此外，可以形象地把快速排序的递归调用过程用一个二叉树描述，先处理较长或较短分区，可以想象为交换某一递归结点处的左右子树，这并不会影响树中的分支数。

11

对一组数据 (2，12，16，88，5，10) 进行排序，若前三趟排序结果如下：

第一趟排序结果：2，12，16，5，10，88

第二趟排序结果：2，12，5，10，16，88

第三趟排序结果：2，5，10，12，16，88

则采用的排序方法可能是（）。

正确答案：A

本题考查内部排序的特征，题中所给的三趟排序过程中，每一趟排序是从前往后依次比较，使最大值“沉底”，符合冒泡排序的特点。

看第一趟可知仅有 88 被移到最后。

如果是希尔排序，则 12,88,10 应变为 10,12,88。因此排除希尔排序。
如果是归并排序，则长度为 2 的子序列是有序的。因此可排除归并排序。
如果是基数排序，则 16,5,10 应变为 10,5,16。因此排除基数排序。

提示：对于此类题，先看备选项的排序算法有什么特征，再看题目中的排序过程是否符合这一特征，从而得出答案。一般先从选项中的简单排序方法（插入排序、起泡排序、选择排序）开始判断，若简单排序方法不符合，再判断排序方法（希尔排序、快速排序、堆排序、归并排序）。

组成原理

12

下列选项中，能缩短程序执行时间的措施是（）。

I. 提高 CPU 时钟频率

II.优化数据通路结构

III. 对程序进行编译优化

正确答案：D

CPU 主频越高，完成指令的一个执行步骤所用的时间就越短，执行指令的速度越快，I 正确。数据通路的功能是实现 CPU 内部的运算器和寄存器以及寄存器之间的数据交换，优化数据通路结构，可以有效提高计算机系统的吞吐量，从而加快程序的执行，II 正确。计算机程序需要先转化成机器指令序列才能最终得到执行，通过对程序进行编译优化可以得到更优的指令序列，从而使得程序的执行时间也越短，III 正确。

【另解】定量分析：CPU 执行时间 = (程序指令条数×每条指令时钟周期数)/时钟频率。提高时钟频率显然可以缩短 CPU 执行时间；编译优化可能减少程序的指令数或优化指令结构；优化数据通路结构可能减少时钟周期，即提高时钟频率，故选 D。

13

假定有 4 个整数用 8 位补码分别表示 r1=FEH，r2=F2H，r3=90H，r4=F8H，若将运算结果存放在一个 8 位寄存器中，则下列运算中会发生溢出的是（）。

正确答案：B

本题的真正意图是考查补码表示的表示范围，而不是补码的乘法运算。若采用补码乘法规则计算出 4 个选项，是费力不讨好的做法，而且极容易出错。

8 位补码所能表示的整数范围为 -128~+127。将 4 个数全部转换为十进制：r1=-2，r2=-14，r3=-112，r4=-8，得 r2×r3=1568，远超出了表示范围，发生溢出。

14

假定变量 i、f 和 d 的数据类型分别为 int，float 和 double（int 用补码表示，float 和 double 分别用 IEEE754 单精度和双精度浮点数格式表示），已 i=785，f=1.5678e3，d=1.5e100。若在 32 位机器中执行下列关系表达式，则结果为 “真” 的是（）。

I. i == (int)(float)i II. f == (float)(int)f

III. f == (float)(double)f IV. (d+f)-d == f

正确答案：B

本题考查不同长度的类型转换，题中三种数据类型的精度从低到高为 int → float → double。

变量说明：

i = 785（int）：32 位整数，用补码表示。
f = 1.5678e3 = 1567.8（float）：32 位 IEEE754 单精度浮点数。
d = 1.5e100（double）：64 位 IEEE754 双精度浮点数。

对于 I. i == (int)(float)i

i 是整数 785。
(float)i 会把整数 785 转为浮点数 —— 精度足够准确表示 785。
再 (int)(float)i 转回整数，仍然是 785。

✅ 结果：真

对于 II. f == (float)(int)f

f = 1567.8，转换为 (int)f 得到 1567（小数部分被截断）。
再转回 (float)(int)f 得到 1567.0。
显然：1567.8 ≠ 1567.0

❌ 结果：假

对于 III. f == (float)(double)f

f 是 float（32 位），被转为 double（64 位）后，再强转回 float。
由于 double 转 float 的精度缩减回原始，值不变。
所以整体等价于 f == f。

✅ 结果：真

对于 IV. (d + f) - d == f

d = 1.5e100（极大），f = 1567.8（非常小，相比于 d）。
d + f ≈ d（因为 f 精度在 d 这个数量级上被吞掉，f 被舍入掉）。
所以 (d + f) - d ≈ 0，不等于 f

❌ 结果：假

所以 正确答案：I、III，答案选择 B。

15

假定用若干个 2kx4 位的芯片组成一个 8kx8 位的存储器，则地址 0B1FH 所在芯片的最小地址是（）。

正确答案：D

本题考查主存容量的扩展，用 2Kx4 位的芯片组成一个 8Kx8 位存储器，共需 8 片 2Kx4 位的芯片，分为 4 组，每组由 2 片 2Kx4 位的芯片并联组成 2Kx8 位的芯片，各组芯片的地址分配如下：

第一组（2 个芯片并联）：0000H ~ 07FFH
第二组（2 个芯片并联）：0800H ~ 0FFFH
第三组（2 个芯片并联）：1000H ~ 17FFH
第四组（2 个芯片并联）：1800H ~ 1FFFH

地址 OBIFH 所在的芯片属于第二组，故其所在芯片的最小地址为 0800H。

16

下列有关 RAM 和 ROM 的叙述中，正确的是（）。

I. RAM 是易失性存储器，ROM 是非易失性存储器

II. RAM 和 ROM 都采用随机存取方式进行信息访问

III. RAM 和 ROM 都可用作 Cache

IV. RAM 和 ROM 都需要进行刷新

正确答案：A
RAM（分为 DRAM 和 SRAM）断电后会失去信息，而 ROM 断电后不会丢失信息，它们都采用随机存取方式（注意，采用随机存取方式的存储器并不一定就是随机存储器）。Cache 一般采用高速的 SRAM 制成，而 ROM 只可读，不能用作 Cache，III 错误。DRAM 需要定期刷新，而 ROM 不需要刷新，故 IV 错误。

17

下列命中组合情况中，一次访存过程中不可能发生的是（）。

正确答案：D

Cache 中存放的是主存的一部分副本，TLB（快表）中存放的是 Page（页表）的一部分副本。在同时具有虚拟页式存储器（有 TLB）和 Cache 的系统中，CPU 发出访存命令，先查找对应的 Cache 块。

若 Cache 命中，则说明所需内容在 Cache 内，其所在页面必然已调入主存，因此 Page 必然命中，但 TLB 不一定命中。
若 Cache 不命中，并不能说明所需内容未调入主存，和 TLB、Page 命中与否没有联系。但若 TLB 命中，Page 也必然命中；而当 Page 命中，TLB 则未必命中，故 D 不可能发生。

【提示】本题看似既涉及虚拟存储器又涉及 Cache，实际上这里并不需要考虑 Cache 命中与否。因为一旦缺页，说明信息不在主存，那么 TLB 中就一定没有该页表项，所以不存在 TLB 命中、Page 缺失的情况，也根本谈不上访问 Cache 是否命中。

18

下列寄存器中，汇编语言程序员可见的是（）。

正确答案：B

读者首先必须明白“汇编程序员可见”的含义，即汇编语言程序员通过汇编程序可以对某个寄存器进行访问。汇编程序员可以通过指定待执行指令的地址来设置 PC 的值，如转移指令、子程序调用指令等。而 R、MAR、MDR 是 CPU 的内部工作寄存器，程序员无法直接获取和设置它们的值，也无法直接对它们进行其他操作，所以对程序员不可见。

【提示】①指令寄存器 R 中的内容总是根据 PC 所取出的指令代码。②在 CPU 的专用寄存器中，只有 PC 和 PSWR 是汇编程序员可见的。

19

下列选项中，不会引起指令流水线阻塞的是（）。

正确答案：A

采用流水线方式，相邻或相近的两条指令可能会因为存在某种关联，后一条指令不能按照原指定的时钟周期运行，从而使流水线断流。有三种相关可能引起指令流水线阻塞：①结构相关，又称资源相关；②数据相关；③控制相关，主要由转移指令引起。

数据旁路转发，其主要思想是不必待某条指令的执行结果送回到寄存器，再从寄存器中取出该结果，作为下一条指令的源操作数，而是直接将执行结果送到其他指令所需要的地方，这样可以使流水线不发生停顿。

20

下列选项中的英文缩写均为总线标准的是（）。

正确答案：D
常见总线标准有：ISA、EISA、VESA、PCI、PCI-Express、AGP、USB、RS-232C 等。A 中的 CRT 是纯平显示器；B 中的 CPI 是每条指令的时钟周期数；C 中的 RAM 是半导体随机存储器、MIPS 是每秒执行多少百万条指令数。

21

单级中断系统中，中断服务程序内的执行顺序是（）。

I 保护现场 II 开中断

III 关中断 IV 保存断点

V 中断事件处理 VI 恢复现场 VII 中断返回

正确答案：A

在单级中断中，不允许中断嵌套。中断处理过程为：①关中断；②保存断点；③识别中断源；④保存现场；⑤中断事件处理；⑥恢复现场；⑦开中断；⑧中断返回。其中，①~~③由硬件完成，④~~⑧由中断服务程序完成，故选 A。

【排除法】选项 B、C、D 的第一个任务（保存断点或关中断）都是由中断隐指令完成的，即由硬件直接执行，与中断服务程序无关。

22

假定一台计算机的显示存储器用 DRAM 芯片实现，若要求显示分辨率为 1600*1200，颜色深度为 24 位，帧频为 85HZ，显存总带宽的 50% 用来刷新屏幕，则需要的显存总带宽至少约为（）。

正确答案：D
刷新所需带宽 = 分辨率×色深×帧频 = 1600×1200×24bit×85Hz = 3916.8Mbps，显存总带宽的 50% 用来刷屏，于是需要的显存总带宽为 3916.8Mbps/0.5 = 7833.6Mbps ≈ 7834Mbps。

操作系统

23

下列选项中，操作系统提供给应用程序的接口是（）。

正确答案：A
操作系统提供的接口主要有两类：命令接口和系统调用。系统调用是能完成特定功能的子程序，当应用程序请求操作系统提供某种服务时，便调用具有相应功能的系统调用。库函数则是高级语言中提供的与系统调用对应的函数（也有些库函数与系统调用无关），目的是隐藏访管指令的细节，使系统调用更为方便、抽象。但要注意，库函数属于用户程序而非系统调用，是系统调用的上层。

24

下列选项中，导致创建新进程的操作是（）。

I.用户登录成功 II.设备分配 III.启动程序执行

正确答案：C
引起进程创建的事件有：用户登录、作业调度、提供服务、应用请求等。I. 用户登录成功后，系统要为此创建一个用户管理的进程，包括用户桌面、环境等。所有的用户进程会在该进程下创建和管理。II. 设备分配是通过在系统中设置相应的数据结构实现的，不需要创建进程。III. 启动程序执行是典型的引起创建进程的事件。

25

设与某资源关联的信号量初值为 3，当前值为 1。若 M 表示该资源的可用个数，N 表示等待该资源的进程数，则 M、N 分别是（）。

正确答案：B
信号量表示相关资源的当前可用数量。当信号量 K>0 时，表示还有 K 个相关资源可用，所以该资源的可用个数是 1。而当信号量 K<0 时，表示有 |K| 个进程在等待该资源。由于资源有剩余，可见没有其他进程等待使用该资源，故进程数为 0。

26

下列选项中，降低进程优先级的合理时机是（）。

正确答案：A
进程时间片用完，可降低其优先级以让别的进程被调度进入执行状态。B 选项中进程刚完成 I/O，进入就绪队列等待被处理机调度，为了让其尽快处理 I/O 结果，故应提高优先权。C 选项中进程长期处于就绪队列，为不至于产生饥饿现象，也应适当提高优先级。D 选项中进程的优先级不应该在此时降低，而应在时间片用完后再降低。

27

进程 $P_{0}$ 和 $P_{1}$ 的共享变量定义及其初值为

boolean flag[2];
int turn = 0;
flag[0] = FALSE;
flag[1] = FALSE;

若进程 $P_{0}$ 和 $P_{1}$ 访问临界资源的类 C 伪代码实现如下：

进程 P0


void P0() {
    while (TRUE) {
        flag[0] = TRUE;
        turn = 1;
        while (flag[1] && (turn == 1));
        临界区；
        flag[0] = FALSE;
    }
}

进程 P1


void P1() {
    while (TRUE) {
        flag[1] = TRUE;
        turn = 0;
        while (flag[0] && (turn == 0));
        临界区；
        flag[1] = FALSE;
    }
}

则并发执行进程 $P_{0}$ 和 $P_{1}$ 时产生的情形是（）。

正确答案：D

这是 Peterson 算法的实际实现，保证进入临界区的进程合理安全。该算法为了防止两个进程为进入临界区而无限期等待，设置变量 u，表示不允许进入临界区的编号，每个进程在先设置自己标志后再设置 u 标志，不允许另一个进程进入，这时，再同时检测另一个进程状态标志和不允许进入表示，这样可以保证当两个进程同时要求进入临界区时只允许一个进程进入临界区。保存的是较晚的一次赋值，因此较晚的进程等待，较早的进程进入。先到先入，后到等待，从而完成临界区访问的要求。

其实这里可以想象为两个人进门，每个人进门前都会和对方客套一句“你先走”。如果进门时没别人，就当和空气说句废话，然后大步登门入室；如果两人同时进门，就互相请先，但各自只客套一次，所以先客套的人请完对方，就等着对方请自己，然后光明正大地进门。

28

某基于动态分区存储管理的计算机，其主存容量为 55MB（初始为空闲），采用最佳适配 (Best Fit) 算法，分配和释放的顺序为：分配 15MB、分配 30MB、释放 15MB、分配 8MB、分配 6MB，此时主存中最大空闲分区的大小是（）。

正确答案：B

最佳适应算法是指每次为作业分配内存空间时，总是找到能满足空间大小需要的最小的空闲分区给作业，可以产生最小的内存空闲分区，如下图所示。

29

某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为 $2^{10}$ B，页表项大小为 2B，逻辑地址结构为 | 页目录号 | 页号 |页内偏移量 |。逻辑地址空间大小为 $2^{16}$ 页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是（）。

正确答案：B
页大小为

2^{10}

B，页表项大小为 2B，故一页可以存放

2^{9}

个页表项，逻辑地址空间大小为

2^{16}

页，即共需

2^{16}

个页表项，则需要

2^{16} / 2^{9} = 2^{7} = 128

个页面保存页表项，即页目录表中包含表项的个数至少是

128

。

30

设文件索引结点中有 7 个地址项，其中 4 个地址项是直接地址索引，2 个地址项是一级间接地址索引，1 个地址项是二级间接地址索引，每个地址项大小为 4B，若磁盘索引块和磁盘数据块大小均为 256B，则可表示的单个文件最大长度是（）。

正确答案：C
每个磁盘索引块和磁盘数据块大小均为 256B，每个磁盘索引块有 256/4=64 个地址项。因此，4 个直接地址索引指向的数据块大小为 4×256B;2 个一级间接索引包含的直接地址索引数为 2×(256/4)，即其指向的数据块大小为 2×(256/4)×256B。1 个二级间接索引所包含的直接地址索引数为 (256/4)×(256/4)，即其所指向的数据块大小为 (256/4)×(256/4)×256B。即 7 个地址项所指向的数据块总大小为 4×256+2×(256/4)×256+(256/4)×(256/4)×256=1082368B=1057KB。

31

设置当前工作目录的的主要目的是（）。

正确答案：C
当一个文件系统含有多级目录时，每访问一个文件，都要使用从树根开始到树叶为止、包括各中间结点名的全路径名。当前目录又称工作目录，进程对各个文件的访问都相对于当前目录进行，而不需要从根目录一层一层的检索，加快了文件的检索速度。选项 A 和 B 都与相对目录无关；选项 D，文件的读/写速度取决于磁盘的性能。

32

本地用户通过键盘登录系统时，首先获得键盘输入信息的程序是（）。

正确答案：B
键盘是典型的通过中断 I/O 方式工作的外设，当用户输入信息时，计算机响应中断并通过中断处理程序获得输入信息。

计算机网络

33

下列选项中，不属于网络体系结构所描述的内容是（）。

正确答案：C
计算机网络的各层及其协议的集合称为体系结构，分层就涉及对各层功能的划分，因此 A、B、D 正确。体系结构是抽象的，它不包括各层协议的具体实现细节。《计算机网络》中在讲解网络层次时，仅有讲各层的协议和功能，而内部实现细节没有提及。内部实现细节是由具体设备厂家来确定的。

34

在下图所示的采用 “存储-转发” 方式的分组交换网络中，所有链路的数据传输速率为 100 Mbps，分组大小为 1000 B，其中分组头大小为 20 B。若主机 H1 向主机 H2 发送一个大小为 980 000 B 的文件，则在不考虑分组拆装时间和传播延迟的情况下，从 H1 发送开始到 H2 接收完为止，需要的时间至少是（）。

正确答案：C

本题考查交换机存储转发的交换方式。分组大小为 1000B，其中分组头大小为 20B，则分组携带的数据大小为 980B，文件长度为 980000B，需拆分为 1000 个分组，加上头部后，每个分组大小为 1000B，总共需要传送的数据量大小为 1MB。由于所有链路的数据传输速度相同，因此文件传输经过最短路径时所需时间最少，最短路径经过 2 个分组交换机。

当 $t = 1 M \times 8/ (100 M b p s) = 80 m s$ 时，H1 发送完最后一个比特。

当 H1 发送完最后一个分组时，该分组需要经过 2 个分组交换机的转发，在 2 次转发完成后，所有分组均到达 H2。每次转发的时间为 $t_{0} = 1 K \times 8/ (100 M b p s) = 0.08 m s$ 。

所以，在不考虑分组拆装时间和传播延迟的情况下，当 $t = 80 m s + 2 t_{0} = 80.16 m s$ 时，H2 接收完文件，即所需的时间至少为 80.16ms。

35

某自治系统采用 RIP 协议，若该自治系统内的路由器 R1 收到其邻居路由器 R2 的距离矢量中包含信息<net1,16>，则可能得出的结论是 ( )。

正确答案：D
R1 在收到信息并更新路由表后，若需要经过 R2 到达 net1，则其跳数为 17，由于距离为 16 表示不可达，因此 R1 不能经过 R2 到达 net1，R2 也不可能到达 net1。B、C 错误，D 正确。而题目中并未给出 R1 向 R2 发送的信息，因此 A 也不正确。

36

若路由器 R 因为拥塞丢弃 IP 分组，则此时 R 可向发出该 IP 分组的源主机发送的 ICMP 报文类型是（）。

正确答案：C
ICMP 差错报文报文有 5 种：终点不可达、源点抑制、时间超过、参数问题、改变路由（重定向），其中源点抑制是当路由器或主机由于拥塞而丢弃数据报时，就向源点发送源点抑制报文，使源点知道应当把数据报的发送速率放慢。

37

某网络的 IP 地址空间为 192.168.5.0/24，采用定长子网划分，子网掩码为 255.255.255.248，则该网络中的最大子网个数、每个子网内的最大可分配地址个数分别是（）。

正确答案：B
由于该网络的 IP 地址为 192.168.5.0/24，网络号为前 24 位，后 8 位为子网号 + 主机号。子网掩码为 255.255.255.248，第 4 个字节 248 转换成二进制为 11111000，因此后 8 位中，前 5 位用于子网号，在 CIDR 中可以表示

2^{5} = 32

个子网；后 3 位用于主机号，除去全 0 和全 1 的情况，可以表示

2^{3} - 2 = 6

个主机地址。

38

下列网络设备中，能够抑制广播风暴的是（）。

I. 中继器 II. 集线器 III. 网桥 IV. 路由器

正确答案：D

参考网络设备对比，中继器和集线器工作在物理层，既不隔离冲突域也不隔离广播域。为了解决冲突域的问题，人们利用网桥和交换机来分隔互联网的各个网段中的通信量，建立多个分离的冲突域，但当网桥和交换机接收到一个未知转发信息的数据帧时，为了保证该帧能被目的结点正确接收，将该帧从所有的端口广播出去，可以看出网桥和交换机的冲突域等于端口个数，广播域为 1。路由器工作在网络层，既隔离冲突域，也隔离广播域。

【提示】广播风暴产生于网络层，因此只有网络层设备才能抑制。链路层设备和物理层设备对网络层的数据包是透明传输，对是否为广播报文是不可知的。

39

主机甲和主机乙之间已建立了一个 TCP 连接，TCP 最大段长度为 1000 字节。若主机甲的当前拥塞窗口为 4000 字节，在主机甲向主机乙连续发送两个最大段后，成功收到主机乙发送的第一个段的确认段，确认段中通告的接收窗口大小为 2000 字节，则此时主机甲还可以向主机乙发送的最大字节数是（）。

正确答案：A
发送窗口大小的上限值取接收方窗口和拥塞窗口这两个值中较小的一个，于是此时发送方的发送窗口为 min{4000,2000}=2000B。由于发送方还没有收到第二个最大段的确认，所以此时甲还可以向乙发送的最大字节数为 2000-1000=1000B。

40

如果本地域名服务器无缓存，当采用递归方法解析另一网络某主机域名时，用户主机、本地域名服务器发送的域名请求消息数分别为（）。

正确答案：A
当采用递归查询时，如果主机所询问的本地域名服务器不知道被查询域名的 IP 地址，那么本地域名服务器就以 DNS 客户的身份，向其他根域名服务器继续发出查询请求报文，而不是让该主机自己进行下一步的查询。因此，这种方法用户主机和本地域名服务器发送的域名请求条数均为 1 条。因此选 A。

解答题

数据结构

41

将关键字序列 ⟨7,8,30,11,18,9,14⟩ 散列存储到散列表中。散列表的存储空间是一个下标从 0 开始的一维数组，散列函数为 H(key)=(key×3)mod7 ，处理冲突采用线性探测再散列法，要求装填（载）因子为 0.7 。

(1) 请画出所构造的散列表。

(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。

key	7	8	30	11	18	9	14
H(key)	0	3	6	5	5	6	0

地址	0	1	2	3	4	5	6	7	8	9
关键词	7	14		8		11	30	18	9

key	7	8	30	11	18	9	14
次数	1	1	1	1	3	3	2

H(key)	0	1	2	3	4	5	6
次数	3	2	1	2	1	5	4

42

设将 $n$ ( $n > 1$ ) 个整数存放到一维数组 R 中。试设计一个在时间和空间两方面都尽可能高效的算法。将 R 中保存的序列循环左移 $p (0 < p < N$ ) 个位置，即将 R 中的数据由 $< x_{0}, x_{1}, \dots, x_{n - 1} >$ 变换为 $< x_{p}, x_{p + 1}, \dots, x_{n - 1}, x_{0}, x_{1}, \dots, x_{p - 1} >$ 。要求：

(1) 给出算法的基本设计思想。

(2) 根据设计思想，采用 C 或 C++ 或 Java 语言描述，关键之处给出注释。

(3) 说明你所设计算法的时间复杂度和空间复杂度。

组成原理

43

某计算机字长为 16 位，主存地址空间大小为 128KB，按字编址。采用单字长指令格式，指令各字段定义如下：

转移指令采用相对寻址方式，相对偏移量用补码表示，寻址方式定义如下：

Ms/Md	寻址方式	助记符	含义
000B	寄存器直接	Rn	操作数 = (Rn)
001B	寄存器间接	(Rn)	操作数 = ((Rn))
010B	寄存器间接、自增	(Rn)+	操作数 = ((Rn)), (Rn) + 1 → Rn
011B	相对	D(Rn)	转移目标地址 = (PC) + (Rn)

请回答下列问题：

(1) 该指令系统最多可有多少条指令？该计算机最多有多少个通用寄存器？存储器地址寄存器（MAR）和存储器数据寄存器（MDR）至少各需要多少位？

(2) 转移指令的目标地址范围是多少？

(3) 若操作码 0010B 表示加法操作（助记符为 add），寄存器 R4 和 R5 的编号分别为 100B 和 101B，R4 的内容为 1234H，R5 的内容为 5678H，地址 1234H 中的内容为 5678H，地址 5678H 中的内容为 1234H，则汇编语言为“add (R4), (R5)+”（逗号前为源操作数，逗号后为目的操作数）对应的机器码是什么（用十六进制表示）？该指令执行后，哪些寄存器和存储单元中的内容会改变？改变后的内容是什么？


字段	OP	Ms	Rs	Md	Rd
内容	0010	001	100	010	101
说明	add	寄存器间接	R4	寄存器间接，自增	R5

44

某计算机的主存地址空间大小为 256MB，按字节编址。指令 Cache 和数据 Cache 分离，均有 8 个 Cache 行，每个 Cache 行大小为 64B，数据 Cache 采用直接映射方式。现有两个功能相同的程序 A 和 B，其伪代码如下所示：


// 程序 A
int a[256][256];
.....
int sum_array1()
{
  int i, j, sum=0;
  for (i=0; i<256; i++)
    for (j=0; j<256; j++)
      sum += a[i][j];
  return sum;
}


// 程序 B
int a[256][256];
.....
int sum_array2()
{
  int i, j, sum=0;
  for (j=0; j<256; j++)
    for (i=0; i<256; i++)
      sum += a[i][j];
  return sum;
}

假定 int 类型数据用 32 位补码表示，程序编译时 i，j，sum 均分配在寄存器中，数组 a 按行优先方式存放，其首地址为 320（十进制数）。请回答下列问题，要求说明理由或给出计算过程。

(1) 若不考虑用于 cache 一致性维护和替换算法的控制位，则数据 Cache 的总容量为多少？

(2) 数组元素 a[0][31] 和 a[1][1] 各自所在的主存块对应的 Cache 行号分别是多少（Cache 行号从 0 开始）？

(3) 程序 A 和 B 的数据访问命中率各是多少？哪个程序的执行时间更短？

1）每个 Cache 行对应一个标记项，如下所示：

| 有效位 | 脏位 | 替换控制位 | 标记位 |

不考虑用于 Cache 一致性维护和替换算法的控制位。地址总长度为 28 位（ $2^{28} = 256$ M），块内地址 6 位（ $2^{6} = 64$ ），Cache 块号 3 位（ $2^{3} = 8$ ），故 Tag 的位数为 28-6-3=19 位，还需使用一个有效位，故题中数据 Cache 行的结构如下图所示。

数据 Cache 共有 8 行，因此数据 Cache 的总容量为 $8 \times (64 + 20/8)$ B= 532B。

2）数组 a 在主存的存放位置及其与 Cache 之间的映射关系如下图所示。

数组按行优先方式存放，首地址为 320，数组元素占 4 字节。a[0][31] 所在的主存块对应的 Cache 行号为 $(320 + 31 \times 4) /64 = 6$ ；a[1][1] 所在的主存块对应的 Cache 行号为 $(320 + 256 \times 4 + 1 \times 4) /64%8 = 5$ 。

3）数组 a 的大小为 $256 \times 256 \times 4 B = 2^{18}$ B, 占用 $2^{18} /64 = 2^{12}$ 个主存块，按行优先存放，程序 $A$ 逐行访问数组，共需访问的次数为 $2^{16}$ 次，未命中次数为 $2^{12}$ 次（即每个字块的第一个数未命中），因此程序 $A$ 的命中率为 $(2^{16} - 2^{12}) / 2^{16} \times 100% = 93.75%$ 。

【另解】数组 a 按行存放，程序 A 按行存取。每个字块中存放 16 个 int 型数据，除访问的第一个不命中，随后的 15 个全都命中，访问全部字块都符合这一规律，且数组大小为字块大小的整数倍，故程序 A 的命中率为 15/16=93.75%。

程序 B 逐列访问数组 a，Cache 总容量为 64Bx8=512B，数组 a 一行的大小为 1KB，正好是 Cache 容量的 2 倍，可知不同行的同一列数组元素使用的是同一个 Cache 单元，故逐列访问每个数据时，都会将之前的字块置换出，也即每次访问都不会命中，命中率为 0。由于从 Cache 读数据比从主存读数据快很多，所以程序 A 的执行比程序 B 快得多。

注意：本题考查 Cache 容量计算，直接映射方式的地址计算，以及命中率计算（注意：行优先遍历与列优先遍历命中率差别很大）。

操作系统

45

假设计算机系统采用 CSCAN（循环扫描）磁盘调度策略，使用 2KB 的内存空间记录 16384 个磁盘块的空闲状态。

(1) 请说明在上述条件如何进行磁盘块空闲状态的管理。

(2) 设某单面磁盘的旋转速度为 6000rpm，每个磁道有 100 个扇区，相邻磁道间的平均移动的时间为 1ms。若在某时刻，磁头位于 100 号磁道处，并沿着磁道号增大的方向移动（见下图），磁道号的请求队列为 50, 90, 30, 120，对请求队列中的每个磁道需读取 1 个随机分布的扇区，则读完这个扇区点共需要多少时间？需要给出计算过程。

(3) 如果将磁盘替换为随机访问的 Flash 半导体存储器（如 U 盘、SSD 等），是否有比 CSCAN 更高效的磁盘调度策略？若有，给出磁盘调度策略的名称并说明理由；若无，说明理由。

被访问的下一个磁道号	移动距离（磁道数）
120	20
30	90
50	20
90	40

46

设某计算机的逻辑地址空间和物理地址空间均为 64KB，按字节编址。若某进程最多需要 6 页（Page）数据存储空间，页的大小为 1KB，操作系统采用固定分配局部置换策略为此进程分配 4 个页框（Page Frame）。在时刻 260 前该进程访问情况见下表（访问位即使用位）。

页号	页框号	装入时刻	访问位
0	7	130	1
1	4	230	1
2	2	200	1
3	9	260	1

当该进程执行到时刻 260 时，要访问逻辑地址为 17CAH 的数据。请回答下列问题：

(1) 该逻辑地址对应的页号是多少？

(2) 若采用先进先出 (FIFO) 置换算法，该逻辑地址对应的物理地址？要求给出计算过程。

(3) 采用时钟 (CLOCK) 置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程（设搜索下一页的指针按顺时针方向移动，且指向当前 2 号页框，示意图如下图）。

计算机网络

47

某局域网采用 CSMA/CD 协议实现介质访问控制，数据传输速率为 10 Mbps，主机甲和主机乙之间的距离为 2 km，信号传播速度是 200 000 km/s。请回答下列问题，要求说明理由或写出计算过程。

(1) 若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测到冲突时刻止，最短需经过多长时间？最长需经过多长时间（假设主机甲和主机乙发送数据过程中，其他主机不发送数据）？

(2) 若网络不存在任何冲突与差错，主机甲总是以标准的最长以太网数据帧（1518 字节）向主机乙发送数据，主机乙每成功收到一个数据帧后立即向主机甲发送一个 64 字节的确认帧，主机甲收到确认帧后方可发送下一个数据帧。此时主机甲的有效数据传输速率是多少（不考虑以太网的前导码）？

3 - 2011 年 408 真题

选择题

选择题答案速对

No.	Ans	No.	Ans	No.	Ans	No.	Ans	No.	Ans
1	A	2	B	3	B	4	C	5	C
6	D	7	A	8	C	9	D	10	A
11	B	12	D	13	A	14	B	15	D
16	A	17	C	18	D	19	C	20	C
21	D	22	C	23	B	24	A	25	D
26	B	27	D	28	D	29	A	30	C
31	B	32	C	33	A	34	B	35	B
36	D	37	D	38	C	39	C	40	B

数据结构

1

设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（）。

x = 2;
while (x < n / 2)
    x = 2 * x;

正确答案：A
在程序中，执行频率最高的语句为 x = x * 2，设该语句总共执行了 T(n) 次，则

2^{T (n) + 1} \leq n /2

，故

T (n) = l o g_{2} (n /2) - 1 = l o g_{2} n - 2

，得

T (n) = O (l o g_{2} n)

。

2

元素 a，b，c，d，e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，知道所有元素都出栈，则在所有可能的出现序列中，以元素 d 开头的序列个数是（）。

正确答案：B
本题考察入栈出栈序列，d 为第 1 个出栈元素，则 d 之前的元素必定是进栈后在栈中停留。因而出栈顺序必为 d_c_b_a_，e 的顺序不定，在任一 “_” 上都有可能，一共有 4 种可能。

3

已知循环队列存储在一维数组 A[0..n-1]中，且队列非空时 front 和 rear 分别指向队头元素和队尾元素。若初始时队列空，且要求第一个进入队列的元素存储在 A[0]处，则初始时 front 和 rear 的值分别是（）。

正确答案：B
根据题意，第一个元素进入队列后存储在 A[0] 处，此时 front 和 rear 值都为 0。入队时由于要执行 (rear+1) % n 操作，所以如果入队后指针指向 0，则 rear 初值为 n-1，而由于第一个元素在 A[0] 中，插入操作只改变 rear 指针，所以 front 为 0 不变。

4

若一棵完全二叉树有 768 个结点，则该二叉树中叶结点的个数是（）

正确答案：C
根据完全二叉树的性质，最后一个分支结点的序号为

⌊ n /2 ⌋ = ⌊ 768/2 ⌋ = 384

, 故叶子结点的个数为 768 - 384 = 384。

5

若一棵二叉树的前序遍历序列和后序遍历序列分别为 1,2,3,4 和 4,3,2,1，则该二叉树的中序遍历序列不会是（）

正确答案：C
前序序列为根左右，后序序列为左右根，由于前序序列和后序序列刚好相反，故不可能存在一个结点同时存在左右孩子，即二叉树的高度为 4。1 为根结点，由于根结点只能有左孩子（或右孩子），因此，在中序序列中，1 或在序列首或在序列尾，ABCD 皆满足要求。仅考虑以 1 的孩子结点 2 为根结点的子树，它也只能有左孩子（或右孩子），因此，在中序序列中，2 或在序列首或序列尾，ABD 皆满足要求，答案选择 C。

6

已知一棵有 2011 个结点的树，其叶结点个数为 116，该树对应的二叉树中无右孩子的结点个数是（）。

正确答案：D
树转化为二叉树时，树中每一个分支结点的所有子结点中的最右子结点无右孩子，根结点转换后也没有右孩子，因此，对应的二叉树中无右孩子的结点个数＝分支结点数+1 = 2011-116+1 = 1896。通常本题应采用特殊法解，设题意中的树是如右图所示的结构，则对应的二叉树中仅有前 115 个叶结点有右孩子，故无右孩子的结点个数 = 2011-115 = 1896。

7

对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（）。

正确答案：A
在二叉排序树中，左子树结点值小于根结点，右子树结点值大于根结点。在选项 A 中，当查找到 91 后再向 24 查找，说明这一条路径（左子树）之后查找的数都要比 91 小，而后面却查找到了 94（解题过程中，建议配合画图），因此错误。

8

下列关于图的叙述中，正确的是（）。

I. 回路是简单路径

II. 存储稀疏图，用邻接矩阵比邻接表更省空间

III. 若有向图中存在拓扑序列，则该图不存在回路

正确答案：C
第一个顶点和最后一个顶点相同的路径称为回路；序列中顶点不重复出现的路径称为简单路径；回路显然不是简单路径，故 I 错误；稀疏图是边比较少的情况，此时用邻接矩阵的空间复杂度为

O (n^{2})

，必将浪费大量的空间，而邻接表的空间复杂度为

O (n + e)

，应该选用邻接表，故 II 错误。存在回路的有向图不存在拓扑序列，若拓扑排序输出结束后所余下的顶点都有前驱，则说明只得到了部分顶点的拓扑有序序列，图中存在回路，故 III 正确。

9

为提高哈希（Hash）表的查找效率，可以采取的正确措施是（）。

I. 增大装填因子

II. 设计冲突少的哈希函数

III. 处理冲突时避免产生堆积现象

正确答案：D
哈希表的查找效率取决于散列函数、处理冲突的方法和装填因子。显然，冲突的产生概率与装填因子（表中记录数与表长之比）的大小成正比，即装填得越满越容易发生冲突，I 错误。II 显然正确。采用合适的处理冲突的方式避免产生聚集现象，也将提高查找效率，例如用拉链法解决冲突时就不存在聚集现象，用线性探测法解决冲突时易引起聚集现象，III 正确。

10

为实现快速排序算法，待排序序列宜采用的存储方式是（）

正确答案：A
对绝大部分内部排序而言，只适用于顺序存储结构。快速排序在排序的过程中，既要从后向前查找，也要从前向后查找，因此宜采用顺序存储。

11

已知序列 25,13,10,12,9 是大根堆，在序列尾部插入新元素 18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是（）

正确答案：B

插入 18 后，首先将 18 与 10 比较，交换位置，再将 18 与 25 比较，不交换位置。共比较了 2 次，调整的过程如下图所示。

组成原理

12

下列选项中，描述浮点数操作速度指标的是（）。

正确答案：D
MIPS 是每秒执行多少百万条指令，适用千衡量标量机的性能。CPI 是平均每条指令的时钟周期数。IPC 是 CPI 的倒数，即每个时钟周期执行的指令数。MFLOPS 是每秒执行多少百万条浮点数运算，用来描述浮点数运算速度，适用于衡量向量机的性能。

13

float 型数据通常用 IEEE754 单精度浮点数格式表示。若编译器将 float 型变量 x 分配在一个 32 位浮点寄存器 FR1 中，且 x=-8.25，则 FR1 的内容是（）。

正确答案：A

本题题意即考查 IEEE 754 单精度浮点数的表示。先将 x 转换成二进制为 $- 1000.01 = - 1.00001 \times 2^{3}$ ，其次计算阶码 E，根据 IEEE 754 单精度浮点数格式，有 E-127=3，故 E=130，转换成二进制为 1000 0010。最后，根据 IEEE 754 标准，最高位的 “1” 是被隐藏的。

IEEE 754 单精度浮点数格式：数符（1 位）＋阶码（8 位）＋尾数（23 位）。

故，FR1 内容为 1; 1000 0010; 0000 10000 0000 0000 0000 000。

即，1100 0001 0000 0100 0000 0000 0000 0000= C104000H。

本题易误选 D, 未考虑 IEEE 754 标准隐含最高位 1 的情况，偏置值是 128。

14

下列各类存储器中，不采用随机存取方式的是（）。

正确答案：B
随机存取方式是指 CPU 可以对存储器的任一存储单元中的内容随机存取，而且存取时间与存储单元的物理位置无关。选项 A、C、D 均采用随机存取方式，CDROM 即光盘，采用串行存取方式。

15

某计算机存储器按字节编址，主存地址空间大小为 64MB，现用 4M×8 位的 RAM 芯片组成 32MB 的主存储器，则存储器地址寄存器 MAR 的位数至少是（）。

正确答案：D
主存按字节编址，地址空间大小为 64MB，MAR 的寻址范围为 64M =

2^{26}

，故为 26 位。实际的主存容量 32MB 不能代表 MAR 的位数，考虑到存储器扩展的需要，MAR 应保证访问到整个主存地址空间，反过来，MAR 的位数决定了主存地址空间的大小。

16

偏移寻址将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中，不属于偏移寻址方式的是（）。

正确答案：A
间接寻址不需要寄存器，EA = (A)。基址寻址 EA = A + 基址寄存器 BR 内容；相对寻址 EA= A + 程序计数器 PC 内容；变址寻址 EA = A + 变址寄存器 IX 内容。后三者都是将某个寄存器内容与一个形式地址相加而形成有效地址，故选 A。

17

某机器有一个标志寄存器，其中有进位/借位标志 CF、零标志 ZF、符号标志 SF 和溢出标志 OF，条件转移指令 bgt（无符号整数比较大于时转移）的转移条件是 ( )

正确答案：C
本题考察标志寄存器，假设两个无符号整数 A 和 B，bgt 指令会将 A 和 B 进行比较，也就是将 A 和 B 相减。如果 A > B，则 A-B 肯定无进位／借位，也不为 0（为 0 时表示两数相同），故而 CF 和 ZF 均为 0，选 C。其余选项中用到了符号标志 SF 和溢出标志 OF, 显然应当排除。

18

下列给出的指令系统特点中，有利于实现指令流水线的是（）。

Ⅰ. 指令格式规整且长度一致

Ⅱ. 指令和数据按边界对齐存放

Ⅲ. 只有 Load/Store 指令才能对操作数进行存储访问

正确答案：D
指令定长、对齐和仅 Load/Store 指令访存，这 3 个都是 RISC 的特征，指令格式规整且长度一致能大大简化指令译码的复杂度，有利于实现流水线。指令和数据按边界对齐存放能保证在一个存取周期内取到需要的数据和指令，不用多余的延迟等待，也有利于实现流水线。只有 Load/Store 指令才能对操作数进行存储访问使取指令、取操作数操作简化且时间长度固定，能够有效地简化流水线的复杂度。

19

假定不采用 Cache 和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误的是（）。

正确答案：C
由于不采用指令预取技术，每个指令周期都需要取指令，而不采用 Cache 技术，则每次取指令都至少要访问内存一次（当指令字长与存储字长相等且按边界对齐时），A 正确。时钟周期是 CPU 的最小时间单位，每个指令周期一定大于或等于一个 CPU 时钟周期，B 正确。即使是空操作指令，在取指操作后，PC 也会自动加 1，C 错误。由于机器处于“开中断”状态，在每条指令执行结束时都可能被外部中断而打断。

20

在系统总线的数据线上，不可能传输的是（）。

正确答案：C
在取指令时，指令便是在数据线上传输的。操作数显然在数据线上传输。中断类型号用以指出中断向量表的地址，CPU 响应中断请求后，将中断应答信号（INTR）发回到数据总线上，CPU 从数据总线上读取中断类型号后，查找中断向量表，找到相应的中断处理程序入口。而握手（应答）信号属于通信联络控制信号，应在通信总线上传输。

21

某计算机有五级中断 $L_{4} \sim L_{0}$ ，中断屏蔽字为 $M_{4} M_{3} M_{2} M_{1} M_{0}$ ， $M_{i} = 1$ （ $0 \leq i \leq 4$ ）表示对 $L_{i}$ 级中断进行屏蔽。若中断响应优先级从高到低的顺序是 $L_{0} \to L_{1} \to L_{2} \to L_{3} \to L_{4}$ ，且要求中断处理优先级从高到低的顺序是 $L_{4} \to L_{0} \to L_{2} \to L_{1} \to L_{3}$ ，则 $L_{1}$ 的中断处理程序中设置的中断屏蔽字是（）。

正确答案：D
高优先级置 0 表示可被中断，比该中断优先级低（或相等）的置 l 表示不可被中断，

L_{1}

只能屏蔽

L_{3}

和其自身，故

M_{3}

和

M_{1}

置 1，中断屏蔽

M_{4} M_{3} M_{2} M_{1} M_{0} = 01010

。

22

某计算机处理器主频为 50MHz，采用定时查询方式控制设备 A 的 I/O，查询程序运行一次所用的时钟周期数至少为 500。在设备 A 工作期间，为数据不丢失，每秒需对其查询至少 200 次，则 CPU 用于设备 A 的 I/O 的时间占整个 CPU 时间的百分比至少是（）。

正确答案：C
本题考察程序查询 I/O 方式，每秒至少查询 200 次，每次查询至少 500 个时钟周期，总的时钟周期数为 200 × 500 =100000，因此 CPU 用于设备 A 的 I/O 的时间占 CPU 时间比为 100000/50M =0.20%。

操作系统

23

下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（）。

正确答案：B
最高响应比优先是一种综合考虑任务长度和等待时间的调度算法，响应比＝（等待时间＋执行时间）／执行时间。高响应比优先算法在等待时间相同的情况下，作业执行时间越短则响应比越高，满足短任务优先。随着长任务的等待时间增加，响应比也会变大，执行机会也就增大，所以不会发生饥饿现象。先来先服务和时间片轮转不符合短任务优先，非抢占式短任务优先会产生饥饿现象。

24

下列选项中，在用户态执行的是（）。

正确答案：A
缺页处理和时钟中断都属于中断，在内核态执行；进程调度是操作系统内核进程，无须用户干预，在核心态执行；命令解释程序属于命令接口，是四个选项中唯一能面对用户的，它在用户态执行。

25

在支持多线程的系统中，进程 P 创建的若干线程不能共享的是（）。

正确答案：D
进程是资源分配的基本单位，线程是处理机调度的基本单位。因此，进程的代码段、进程打开的文件、进程的全局变量等都是进程的资源，唯有进程中某线程的栈指针是属于线程的，属于进程的资源可以共享，属于线程的栈是独享的，对其他线程透明。

26

用户程序发出磁盘 I/O 请求后，系统的正确处理流程是（）。

正确答案：B

I/O 软件一般从上到下分为四个层次：用户层、与设备无关的软件层、设备驱动程序以及中断处理程序。与设备无关的软件层也就是系统调用的处理程序。

当用户使用设备时，首先在用户程序中发起一次系统调用，操作系统的内核接到该调用请求后请求调用处理程序进行处理，再转到相应的设备驱动程序，当设备准备好或所需数据到达后设备硬件发出中断，将数据按上述调用顺序逆向回传到用户程序中。

27

某时刻进程的资源使用情况如下表所示。

此时的安全序列是（）。

正确答案：D
题应采用排除法，逐个代入分析。当剩余资源分配给

P_{1}

，待

P_{1}

执行完后，可用资源数为 (2,2,1)，此时仅能满足

P_{4}

的需求，排除 A、B；接着分配给

P_{4}

，待

P_{4}

执行完后，可用资源数为 (2,2,2)，此时已无法满足任何进程的需求，排除 C。此外，本题还可以使用银行家算法求解（对于选择题来说，显得过于复杂）。

28

在缺页处理过程中，操作系统执行的操作可能是（）。

I、修改页表

II、磁盘 I/O

III、分配页框

正确答案：D
缺页中断产生后，需要在内存中找到空闲页框并分配给需要访问的页（可能涉及页面置换），之后缺页中断处理程序调用设备驱动程序做磁盘/O，将位于外存上的页面调入内存，调入后需要修改页表，将页表中代表该页是否在内存的标志位（或有效位）置为 1，并将物理页框号填入相应位置，若必要还需修改其他相关表项等。

29

当系统发生抖动 (thrashing) 时，可以采取的有效措施是（）。

I. 撤销部分进程

II. 增加磁盘交换区的容量

III. 提高用户进程的优先级

正确答案：A
在具有对换功能的操作系统中，通常把外存分为文件区和对换区。前者用于存放文件，后者用于存放从内存换出的进程。抖动现象是指刚刚被换出的页很快又要被访问，为此又要换出其他页，而该页又很快被访问，如此频繁地置换页面，以致大部分时间都花在页面置换上，引起系统性能下降。撤销部分进程可以减少所要用到的页面数，防止抖动。对换区大小和进程优先级都与抖动无关。

30

在虚拟内存管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是（）。

正确答案：C

编译后的模块需要经过链接才能装载，而链接后形成的地址才是整个程序的完整逻辑地址空间。以 C 语言为例：C 语言经过预处理 (cpp)→编译 (ccl)→汇编 (as)→链接 (ld) 产生可执行文件。其中链接的前一步，产生了可重定位的二进制的目标文件。C 语言采用源文件独立编译的方法，如程序 main.c，file1.c,file2.c,file1.h,file2.h，在链接的前一步生成了 main.o,file1.o,file2.o，这些目标模块采用的逻辑地址都从 0 开始，但只是相对于该模块的逻辑地址。链接器将这三个文件，libc 和其他的库文件链接成一个可执行文件。链接阶段主要完成了重定位，形成整个程序的完整逻辑地址空间。

例如，file1.o 的逻辑地址为 0~~1023，main.o 的逻辑地址为 0~~1023，假设链接时将 file1.o 链接在 main.o 之后，则重定位之后 file1.o 对应的逻辑地址就应为 1024~2047。

31

某文件占 10 个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析，假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为 100μs，将缓冲区的数据传送到用户区的时间是 50μs，CPU 对一块数据进行分析的时间为 50μs。在单缓冲区和双缓冲区结构下，读入并分析完该文件的时间分别是（）。

正确答案：B
在单缓冲区中，当上一个磁盘块从缓冲区读入用户区完成时，下一磁盘块才能开始读入，也就是当最后一块磁盘块读入用户区完毕时所用时间为 150×10=1500μs，加上处理最后一个磁盘块的时间 50μs，得 1550μs。在双缓冲中，不存在等待磁盘块从缓冲区读入用户区的问题，10 个磁盘块可以连续从外存读入主存缓冲区，加上将最后一个磁盘块从缓冲区送到用户区的传输时间 50μs 以及处理时间 50μs，也就是 100×10+50+50=1100μs。

32

有两个并发执行的进程 P1 和 P2，共享初值为 1 的变量 x。P1 对 x 加 1，P2 对 x 减 1。加 1 和减 1 操作的指令序列分别如下所示。

P1 // 加 1 操作
load R1, x // 取 x 到寄存器 R1 中
inc R1
store x, R1 // 将 R1 的内容存入 x
P2 // 减 1 操作
load R2, x // 取 x 到寄存器 R2 中
dec R2
store x, R2 // 将 R2 的内容存入 x

两个操作完成后，x 的值（）。

正确答案：C
将

P_{1}

中 3 条语句依次编号为 1,2,3；

P_{2}

中 3 条语句依次编号为 4,5,6。依次执行 1,2,3,4,5,6 得结果 1，依次执行 1,2,4,5,6,3 得结果 2，执行 4,5,1,2,3,6 得结果 0。因此结果 -1 不可能得出。

计算机网络

33

TCP/IP 参考模型的网络层提供的是（）。

正确答案：A
TCP/IP 的网络层向上只提供简单灵活的、无连接的、尽最大努力交付的数据报服务。考查 IP 首部，如果是面向连接的，那么应有用于建立连接的字段，但是没有；如果提供可靠的服务，那么至少应有序号和校验和两个字段，但是 IP 分组头中也没有（IP 首部中只是首部校验和）。通常有连接、可靠的应用是由运输层的 TCP 实现的。

34

若某通信链路的数据传输速率为 2400 bps，采用 4 相位调制，则该链路的波特率是（）。

正确答案：B
波特率 B 与数据传输率 C 的关系：

C = Bl o g_{2} N

，

N

为一个码元所取的离散值个数。采用

4

种相位，也即可以表示

4

种变化，故一个码元可携带

l o g_{2} 4 = 2

bit 信息，则该链路的波特率 = 比特率/2 = 1200 波特。

35

数据链路层采用选择重传协议 (SR) 传输数据，发送方已发送了 0～3 号数据帧，现已收到 1 号帧的确认，而 0、2 号帧依次超时，则此时需要重传的帧数是（）。

正确答案：B
在选择性重传中，接收方逐个确认正确接收的分组，不管接收到的分组是否有序，只要正确接收就发送选择 ACK 分组进行确认。因此选择重传协议中的 ACK 分组不再具有累积确认的作用，要特别注意其与 GBN 协议的区别。本题中只收到 1 号帧的确认，0、2 号帧超时，由于对于1 号帧的确认不具累积确认的作用，因此发送方认为接收方没有收到 0、2 号帧，于是重传这两帧。因为 3 号帧计时器并无超时，所以暂时不用重传 3 号帧。

36

下列选项中，对正确接收到的数据帧进行确认的 MAC 协议是（）。

正确答案：D
CSMA/CA 协议是无线局域网标准 802.11 中的协议，它在 CSMA 的基础上增加了冲突避免的功能。ACK 帧是 CSMA/CA 避免冲突的机制之一，也就是说，只有当发送方收到接收方发回的 ACK 帧后才确认发出的数据帧已正确到达目的地。

37

某网络拓扑如下图所示，路由器 R1 只有到达子网 192.168.1.0/24 的路由。为使 R1 可以将 IP 分组正确地路由到图中所有子网，则在 R1 中需要增加的一条路由（目的网络，子网掩码，下一跳）是（）。

正确答案：D

要使 R1 能够正确将分组路由到所有子网，则 R1 中需要有到 192.168.2.0/25 和 192.168.2.128/25 的路由，分别转换成二进制如下：

192.168.2.0: 11000000 10101000 00000010 00000000

192.168.2.128: 11000000 10101000 00000010 10000000

前 24 位都是相同的，于是可以聚合成超网 192.168.2.0/24, 子网掩码为前 24 位，即 255.255.255.0。下一跳是与 R1 直接相连的 R2 的地址，因此是 192.168.1.2。

38

在子网 192.168.4.0/30 中，能接收目的地址为 192.168.4.3 的 IP 分组的最大主机数是（）。

正确答案：C
首先分析 192.168.4.0/30 这个网络，主机号只占 2 位，地址范围为 192.168.4.0-192.168.4.3，主机号全 1 时，即 192.168.4.3 是广播地址，主机号全 0 表示本网络本身，不作为主机地址使用，因此可容纳 4-2=2 个主机。

39

主机甲向主机乙发送一个 (SYN＝1, seq＝11220) 的 TCP 段，期望与主机乙建立 TCP 连接，若主机乙接受该连接请求，则主机乙向主机甲发送的正确的 TCP 段可能是

正确答案：C
本题考查三次握手，在确认报文段中，同步位 SYN 和确认位 ACK 必须都是 1；返回的确认号 seq 是甲发送的初始序号 seq=11220 加 1，即 ack= 11221；同时乙也要选择并消耗一个初始序号 seq，seq 值由乙的TCP 进程任意给出，它与确认号、请求报文段的序号没有任何关系。

40

主机甲与主机乙之间已建立一个 TCP 连接，主机甲向主机乙发送了 3 个连续的 TCP 段，分别包含 300 字节、400 字节和 500 字节的有效载荷，第 3 个段的序号为 900。若主机乙仅正确接收到第 1 和第 3 个段，则主机乙发送给主机甲的确认序号是

正确答案：B
TCP 首部的序号字段是指本报文段数据部分的第一个字节的序号，而确认号是期待收到对方下一个报文段的第一个字节的序号。第三个段的序号为 900，则第二个段的序号为 900-400=500，现在主机乙期待收到第二个段，故发给甲的确认号是 500。

解答题

数据结构

41

已知有 6 个顶点（顶点编号为 0～5）的有向带权图 G ，其邻接矩阵 A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。

要求：

(1) 写出图 G 的邻接矩阵 A 。

(2) 画出有向带权图 G 。

(3) 求图 G 的关键路径，并计算该关键路径的长度。

i	0	1	2	3	4	5
ve(i)	0	4	9	13	12	16
vl(i)	0	4	9	13	13	16

	$a_{0 \to 2}$	$a_{1 \to 2}$	$a_{2 \to 3}$	$a_{2 \to 4}$	$a_{3 \to 5}$	$a_{4 \to 5}$
e()	0	4	9	9	13	12
l()	3	4	9	10	13	13
l-e	3	0	0	1	0	1

42

一个长度为 L（L ≥ 1）的升序序列 S ，处在第 $⌈ L /2 ⌉$ 个位置的数称为 S 的中位数。例如，若序列 S1 = (11,13,15,17,19)，则 S1 的中位数是 15 。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若序列 S2 = (2,4,6,8,20)，则 S1 和 S2 的中位数是 11 。现有两个等长的升序序列 A 和 B ，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 A 和 B 的中位数。要求：

(1) 给出算法的基本设计思想。

(2) 根据设计思想，采用 C 或 C++ 或 Java 语言描述，关键之处给出注释。

(3) 说明你所设计算法的时间复杂度和空间复杂度。

(1) 求两个序列 A 和 B 的中位数最简单的办法就是将两个升序序列进行归并排序，然后求其中位数。这种解法虽可求解，但在时间和空间两方面都不大符合高效的要求，但也能获得部分分值。

根据题目分析，分别求两个升序序列 A 和 B 的中位数，设为 a 和 b。

① 若 $a = b$ ，则 $a$ 或 $b$ 即为所求的中位数。

原因：容易验证，如果将两个序列归并排序，则最终序列中，排在子序列 b 前边的元素为先前两个序列中排在 a 和 b 前边的元素；排在子序列 ab 后边的元素为先前两个序列中排在 a 和 b后边的元素。所以子序列 ab 一定位于最终序列的中间，又因为 a=b，显然 a 就是中位数。

②否则（假设 $a < b$ )，中位数只能出现 (a,b) 范围内。

原因：同样可以用归并排序后的序列来验证，归并排序后必然有形如 $\dots a \dots b \dots$ 的序列出现，中位数必出现在 (a,b) 之间。因此可以做如下处理：舍弃 a 所在序列 A 的较小一半，同时舍弃 b 所在序列 B 的较大一半。在保留两个升序序列中求出新的中位数 a 和 b，重复上述过程，直到两个序列中只含一个元素时为止，则较小者即为所求的中位数。每次总的元素个数变为原来的一半。

算法的基本设计思想如下。

分别求出序列 A 和 B 的中位数，设为 a 和 b，求序列 A 和 B 的中位数过程如下：

① 若 $a = b$ ，则 a 或 b 即为所求中位数，算法结束。

② 若 $a < b$ ，则舍弃序列 A 中较小的一半，同时舍弃序列 B 中较大的一半，要求舍弃的长度相等。

③ 若 $a > b$ ，则舍弃序列 A 中较大的一半，同时舍弃序列 B 中较小的一半，要求舍弃的长度相等。

在保留的两个升序序列中，重复过程①、②、③，直到两个序列中只含一个元素时为止，较小者即为所求的中位数。

2）算法实现

int M_Search(int A[], int B[], int n) {
    int s1 = 0, d1 = n - 1, m1, s2 = 1, d2 = n - 1, m2;
    // 分别表示序列 A 和 B 的首位、末位和中位数
    while (s1 != d1 || s2 != d2) {
        m1 = (s1 + d1) / 2;
        m2 = (s2 + d2) / 2;
        if (A[m1] == B[m2])
            return A[m1];     // 满足条件 1
        if (A[m1] < B[m2]) {  // 满足条件 2
            if ((s1 + d1) % 2 == 0) {
                // 若元素个数为奇数
                s1 = m1;       // 舍弃 A 中间点以后的部分，且保留中间点
                d2 = m2;       // 舍弃 B 中间点以前的部分，且保留中间点
            } else {
                // 元素个数为偶数
                s1 = m1 + 1;   // 舍弃 A 中间点及中间点以后的部分
                d2 = m2;       // 舍弃 B 中间点以前部分，且保留中间点
            }
        } else {  // 满足条件 3
            if ((s1 + d1) % 2 == 0) {
                // 若元素个数为奇数
                d1 = m1;       // 舍弃 A 中间点以前的部分，且保留中间点
                s2 = m2;       // 舍弃 B 中间点以后的部分，且保留中间点
            } else {
                // 元素个数为偶数
                d1 = m1 + 1;   // 舍弃 A 中间点及中间点以前部分
                s2 = m2;       // 舍弃 B 中间点以后的部分，且保留中间点
            }
        }
    }
    return A[s1] < B[s2] ? A[s1] : B[s2];
}

3）时间复杂度 O(n)，空间复杂度 O(1)。

组成原理

43

假定在一个 8 位字长的计算机中运行如下 C 程序段：

unsigned int x=134;
unsigned int y=246;
int m=x;
int n=y;
unsigned int z1=x-y;
unsigned int z2=x+y;
int k1=m-n;
int k2=m+n;

若编译器编译时将 8 个 8 位寄存器 R1～R8 分别分配给变量 x、y、m、n、z1、z2、k1 和 k2。请回答下列问题。（提示：带符号整数用补码表示）

(1) 执行上述程序段后，寄存器 R1、R5 和 R6 的内容分别是什么（用十六进制表示）？

(2) 执行上述程序段后，变量 m 和 k1 的值分别是多少（用十进制表示）？

(3) 上述程序段涉及带符号整数加/减、无符号整数加/减运算，这四种运算能否利用同一个加法器及辅助电路实现？简述理由。

(4) 计算机内部如何判断带符号整数加/减运算的结果是否发生溢出？上述程序段中，哪些带符号整数运算语句的执行结果会发生溢出？

44

某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为 16MB，主存（物理）地址空间大小为 1MB，页面大小为 4KB：Cache 采用直接映射方式，共 8 行：主存与 Cache 之间交换的块大小为 32B。系统运行到某一时刻时，页表的部分内容和 Cache 的部分内容分别如题 44-a 图、题 44-b 图所示，图中页框号及标记字段的内容为十六进制形式。

请回答下列问题∶

(1) 虚拟地址共有几位，哪几位表示虚页号？物理地址共有几位，哪几位表示页框号（物理页号）？

(2) 使用物理地址访问 Cache 时，物理地址应划分成哪几个字段？要求说明每个字段的位数及在物理地址中的位置。

(3) 虚拟地址 001C60H 所在的页面是否在主存中？若在主存中，则该虚拟地址对应的物理地址是什么？访问该地址时是否 Cache 命中？要求说明理由。

(4) 假定为该机配置一个 4 路组相连的 TLB，该 TLB 共可存放 8 个页表项，若其当前内容（十六进制）如题 44-c 图所示，则此时虚拟地址 024BACH 所在的页面是否在主存中？要求说明理由。

操作系统

45

某银行提供 1 个服务窗口和 10 个顾客等待座位。顾客到达银行时，若有空座位，则到取号机领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：

cobegin
{
    process 顾客 i 
    {
        从取号机获得一个号码;
        等待叫号;
        获得服务;
    }

    process 营业员
    {
        while (TRUE) {
            叫号;
            为顾客服务;
        }
    }
}coend

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

1）互斥资源：取号机（一次只一位顾客领号），因此设一个互斥信号量 mutex。

2）同步问题：顾客需要获得空座位等待叫号，当营业员空闲时，将选取一位顾客并为其服务。空座位的有、无影响等待顾客数量，顾客的有、无决定了营业员是否能开始服务，故分别设置信号量 empty 和 full 来实现这一同步关系。另外，顾客获得空座位后，需要等待叫号和被服务。这样，顾客与营业员就服务何时开始又构成了一个同步关系，定义信号量 service 来完成这一同步过程。

semaphore empty   = 10;       // 空座位的数量
semaphore mutex   = 1;        // 互斥使用取号机
semaphore full    = 0;        // 已占座位的数量
semaphore service = 0;        // 等待叫号

process 顾客 i {
    P(empty);                 // 等空位
    P(mutex);                 // 申请使用取号机
    从取号机上取号;
    V(mutex);                 // 取号完毕
    V(fu11);                  // 通知营业员有新顾客
    P(service);               // 等待营业员叫号
    接受服务;
}

process 营业员 {
    while(True) (
        P(fu11);              // 没有顾客则休息
        叫号;
        V(empty);             // 离开座位
        V(service);           // 叫号
        为顾客服务;
    }
}

46

某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题∶

(1) 在连续、链式、索引二种文件的数据块组织方式中。哪种更合适？要求说明理由。为定位文件数据块，需要在 FCB 中设计哪些相关描述字段？

(2) 为快速找到文件，对于 FCB，是集中存储好，还是与对应的文件数据块连续存储好？要求说明理由。

计算机网络

47

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

请参考图中的数据回答以下问题。

(1) Web 服务器的 IP 地址是什么？该主机的默认网关的 MAC 地址是什么？

(2) 该主机在构造题 47-b 图的数据帧时，使用什么协议确定目的 MAC 地址？封装该协议请求报文的以太网帧的目的 MAC 地址是什么？

(3) 假设 HTTP/1.1 协议以持续的非流水线方式工作，一次请求 - 响应时间为 RTT，rfc.html 页面引用了 5 个 JPEG 小图像，则从发出题 47-b 图中的 Web 请求开始到浏览器收到全部内容为止，需要多少个 RTT？

(4) 该帧所封装的 IP 分组经过路由器 R 转发时，需修改 IP 分组头中的哪些字段？

注意：以太网数据帧结构和 IP 分组头结构分别如题 47-c 图、题 47-d 图所示。

1）以太网帧的数据部分是 IP 数据报，只要数出相应字段所在的字节即可。由图可知以太网帧头部有 6+6+2=14 字节，IP 数据报首部的目的 IP 地址字段前有 4×4=16 字节，从帧的第 1 字节开始数 14+16=30 字节，得目的 IP 地址 40.aa.62.20（十六进制），转换成十进制为 64.170.98.32。可知以太网帧的前 6 字节 00-21-27-21-51-ee 是的 MAC 地址，即为主机的默认网关 10.2.128.1 端口的 MAC 地址。

2）ARP 协议于解决 IP 地址到 MAC 地址的映射问题。主机的 ARP 进程在本以太网以广播的形式发送 ARP 请求分组，在以太网上广播时，以太网帧的目的地址为全 1，即 FF-FF-FF-FF-FF-FF。

3）HTTP/1.1 协议以持续的非流水线方式工作时，服务器在发送响应后仍然在一段时间内保持这段连接，客户机在收到前一个请求的响应后才能发出下一个请求。第一个 RTT 用于请求 Web 页面，客户机收到第一个请求的响应后（还有五个请求未发送），每访问一次对象就用去一个 RTT。故共需 1+5=6 个 RTT 后浏览器收到全部内容。

4）源 IP 地址 0a.02.80.64 改为 65.0c.7b.0f；生存时间（TTL）减 1；校验和字段重新计算。私有地址和 Internet 的主机通信时，须由 NAT 路由器进行网络地址转换，把 IP 数据报的源 IP 地址（本题为私有地址 10.2.128.100）转换为 NAT 路由器的一个全球 IP 地址（本题为 101.12.123.15）因此，源 IP 地址字段 0a 02 80 64 变为 65 0c 7b 0f。IP 数据报每经过一个路由器，生存时间 TTL 值就减 1，并重新计算首部校验和。若 IP 分组的长度超过输出链路的 MTU，则总长度字段、标志字段、片偏移字段也要发生变化。

注意：题 47-b 图中每行前 4bit 是数据帧的字节计数，不属于以太网数据帧的内容。

【评分说明】若考生解答时将所有 IP 头中的字段进行罗列，不给分，其他情况的情给分。

4 - 2012 年 408 真题

选择题

选择题答案速对

No.	Ans	No.	Ans	No.	Ans	No.	Ans	No.	Ans
1	B	2	A	3	A	4	B	5	C
6	C	7	C	8	A	9	D	10	A
11	D	12	D	13	B	14	D	15	D
16	A	17	C	18	C	19	C	20	D
21	D	22	B	23	C	24	B	25	B
26	A	27	D	28	A	29	B	30	C
31	A	32	B	33	B	34	C	35	A
36	B	37	C	38	A	39	D	40	D

数据结构

1

求整数 $n (n \geq 0)$ 阶乘的算法如下，其时间复杂度是（）。

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

正确答案：B

本算法是一个递归运算，即算法中出现了调用自身的情形。递归的边界条件是 $\leq 1$ ，每调用一次 fact()，传入该层 fact() 的参数值减 1。采用递归式来表示时间复杂度有

T_{n} = {O (1), n \leq 1 T (n - 1) + 1, n > 1

则 $T (n) = T (n - 1) + 1 = T (n - 2) + 2 = \dots = T (1) + n - 1 = O (n)$ ，故时间复杂度为 $O (n)$ 。

2

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

正确答案：A
表达式求值是栈的典型应用。中缀表达式不仅依赖千运算符的优先级，而且要处理括号。后缀表达式的运算符在表达式的后面且没有括号，其形式已经包含了运算符的优先级。所以从中序转后序需要用运算符进行处理，使其包含运算符优先级的信息，从而转换为后缀表达式的形式。

3

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

正确答案：A
本题考察双序列组合重建二叉树，前序序列和后序序列不能唯一确定一棵二叉树，但可以确定二叉树中结点的祖先关系：当两个结点的前序序列为 XY 与后序序列为 YX 时，则 X 为 Y 的祖先。考虑前序序列 a,e,b,d,c、后序序列 b,c,d,e,a 且，可知 a 为根结点，e 为 a 的孩子结点。此外，a 的孩子结点的前序序列 e,b,d,c、后序序列 b,c,d,e，可知 e 是 bcd 的祖先，故根结点的孩子结点只有 e。故选 A。

4

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

正确答案：B

所有非叶结点的平衡因子均为 1，即平衡二叉树满足平衡的最少结点情况，如下图所示。

对于高度为 N、左右子树的高度分别为 N-1 和 N-2、所有非叶结点的平衡因子均为 1 的平衡二叉树，总结点数的公式为： $C_{N} = C_{N - 1} + C_{N - 2} + 1$ , $C_{1} = 1$ , $C_{2} = 2$ , $C_{3} = 2 + 1 + 1 = 4$ ，可推出 $C_{6} = 20$ 。

5

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

正确答案：C
广度优先遍历需要借助队列实现。邻接表的结构包括：顶点表；边表（有向图为出边表）。当采用邻接表存储方式时，在对图进行广度优先遍历时每个顶点均需入队一次（顶点表遍历），故时间复杂度为

O (n)

，在搜索所有顶点的邻接点的过程中，每条边至少访问一次（出边表遍历），故时间复杂度为

O (e)

，算法总的时间复杂度为

O (n + e)

。

6

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

正确答案：C

对角线以下元素均为零，表明只有顶点 $i$ 到顶点 $j$ ( $i < j$ ) 可能有边，而顶点 $j$ 到顶点 $i$ 一定没有边，即有向图是一个无环图，因此一定存在拓扑序列。对于拓扑序列是否唯一，试举一例：设有向图的邻接矩阵

000100100

则存在两个拓扑序列，因此该图存在可能不唯一的拓扑序列。

结论：对于任一有向图，如果它的邻接矩阵中对角线以下（或以上）的元素均为零，则存在拓扑序列（可能不唯一）。反正，若图存在拓扑序列，却不一定能满足邻接矩阵中主对角线以下的元素均为零，但是可以通过适当地调整结点编号，使其邻接矩阵满足前述性质。

7

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

正确答案：C

从 a 到各顶点的最短路径的求解过程：

顶点	第 1 趟	第 2 趟	第 3 趟	第 4 趟	第 5 趟
b	(a,b)2
c	(a,c)5	(a,b,c)3
d	∞	(a,b,d)5	(a,b,d)5	(a,b,d)5
e	∞	∞	(a,b,c,f)4
f	∞	∞	(a,b,c,e)7	(a,b,c,e)7	(a,b,d,e)6
集合 S	{a,b}	{a,b,c}	{a,b,c,f}	{a,b,c,f,d}	{a,b,c,f,d,e}

后续目标顶点依次为 f, d, e。

【排除法】对于 A，若下一个顶点为 d，路径 a,b,d 的长度5，而 a,b,c,f 的长度仅为4，显然错误。同理可以排除B。将 f 加入集合 S 后，采用上述的方法也可以排除 D。

8

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

Ⅰ．最小生成树的代价唯一

Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中

Ⅲ．使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同

Ⅳ．使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同

正确答案：A
对于 I，最小生成树的树形可能不唯一（这是因为可能存在权值相同的边），但是代价一定是唯一的，I 正确。对于Ⅱ，如果权值最小的边有多条并且构成环状，则总有权值最小的边将不出现在某棵最小生成树中，Ⅱ错误。对于Ⅲ，设 N 个结点构成一个环、环上 N 条边的权值全部相等，则去掉环上任意一条边都得到一棵最小生成树，共 N 棵互不相同，从不同顶点出发执行普里姆算法会得到不同的最小生成树，Ⅲ 错误。对于Ⅳ，当最小生成树唯一时（各边权值互不相同），Prim 算法和 Kruskal 算法得到的最小生成树相同，「总不相同」的绝对化说法不成立，Ⅳ 错误。

9

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

正确答案：D

本题考察 B 树的删除操作。对于上图所示的 3 阶 B 树，被删关键字 78 所在结点在删除前的关键字个数 = 1 = ⌈3/2⌉-1，且其左兄弟结点的关键字个数 = 2 ≥ ⌈3/2⌉，属于“兄弟够借”的情况，则需把该结点的左兄弟结点中最大的关键字上移到双亲结点中，同时把双亲结点中大于上移关键字的关键字下移到要删除关键字的结点中，这样就达到了新的平衡，如下图所示。

10

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

Ⅰ．简单选择排序

Ⅱ．希尔排序

Ⅲ．快速排序

Ⅳ．堆排序

Ⅴ．二路归并排序

正确答案：A

本题考察不同内部排序算法的细节：

对于 I，简单选择排序每次选择未排序列中的最小元素放入其最终位置。
对于 II，希尔排序每次是对划分的子表进行排序，得到局部有序的结果，所以不能保证每一趟排序结束都能确定一个元素的最终位置。
对于 III，快速排序每一趟排序结束后都将枢轴元素放到最终位置。
对于 IV，堆排序属于选择排序，每次都将大根堆的根结点与表尾结点交换，确定其最终位置。
对于 V，二路归并排序每趟对子表进行两两归并从而得到若干个局部有序的结果，但无法确定最终位置。

I、III、IV 正确，本题选择 A。

11

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

正确答案：D
本题考察插入排序，折半插入排序与直接插入排序是将待插入元素插入前面的有序子表，区别是：确定当前记录在前面有序子表中的位置时，直接插入排序是采用顺序查找法，而折半插入排序是采用折半查找法。排序的总趟数取决于元素个数

n

，两者都是

n - 1

趟。元素的移动次数都取决于初试序列，两者相同。使用辅助空间的数量也都是 O(1)。折半插入排序的比较次数与序列初态无关，为

O (n l o g_{2} n)

：直接插入排序的比较次数与序列初态有关，为

O (n) \sim O (n^{2})

。

组成原理

12

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

正确答案：D

程序 A 的运行时间为 100s，除去 CPU 时间 90s，剩余 10s 为 I/O 时间。CPU 提速后运行基准程序 A 所耗费的时间是 T = 90/1.5 + 10 = 70s。

【误区】CPU速度提高50%，则CPU时间减少一半，而误选A。

13

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

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

得到 y 的机器数为（）。

正确答案：B
将一个 16 位 unsigned short 转换成 32 位形式的 unsigned int，因为都是无符号数，新表示形式的高位用 0 填充。16 位无符号整数所能表示的最大值为 65 5 35，其十六进制表示为 FFFFH，故 x 的十六进制表示为 FFFFH - 5H = FFFAH，所以 y 的十六进制表示为 0000 FFFAH。

14

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

正确答案：D
IEEE754 单精度浮点数是尾数用采取隐藏位策略的原码表示，且阶码用移码（偏置值为

127

）表示的浮点数。规格化的短浮点数的真值为：

(- 1)^{S} \times 1. m \times 2^{E - 127}

，

S

为符号位，阶码

E

的取值为

1 \sim 254

（8 位表示），尾数

m

为

23

位，共

32

位；故 float 类型能表示的最大整数是

1.111 \dots 1 \times 2^{254 - 127} = 2^{127} \times (2 - 2^{- 23}) = 2^{128} - 2^{104}

，故选 D。

15

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

struct {
    int a;
    char b;
    short c;
} record;

record.a=273;

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

正确答案：D

尽管 record 大小为 7 个字节（成员 a 有 4 个字节，成员 b 有 1 个字节，成员 c 有 2 个字节），由于数据按边界对齐方式存储，故 record 共占用 8 个字节。record.a 的十六进制表示为 0x00000111，由于采用小端方式存放数据，故地址 0xC008 中内容应为低字节 0x11; record.b 只占 1 个字节，后面的一个字节留空；record.c 占 2 个字节，故其地址为 0xC00E。各字节的存储分配如下图所示。

地址	0xC008	0xC009	0xC00A	0xC00B
内容	record.a.(0x11)	record.a.(0x01)	record.a.(0x00)	record.a.(0x00)
地址	0xC00C	0xC00D	0xC00E	0xC00F
内容	record.b	-	record.c	record.c

16

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

正确答案：A
闪存是 EEPROM 的进一步发展，可读可写，用 MOS 管的浮栅上有无电荷来存储信息。闪存依然是 ROM 的一种，写入时必须先擦除原有数据，故写的速度比读的速度要慢不少（硬件常识）。闪存是一种非易失性存储器，它采用随机访问方式。现在常见的 SSD 固态硬盘，即由Flash 芯片组成。

17

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

正确答案：C

地址映射采用 2 路组相联，则主存地址为 0~1、4~5、8~9 可映射到第 0 组 Cache 中，主存地址为 2~3、6~7 可映射到第 1 组 Cache 中。Cache 置换过程如下表所示。

	走向	0	4	8	2	0	6	8	6	4	8
第0组	块0		0	4	4	8	8	0	0	8	4
	块1	0	4	8	8	0	0	8*	8	4	8*
第1组	块2						2	2	2	2	2
	块3				2	2	6	6	6*	6	6

注：“_” 表示当前访问块，“*” 表示本次访问命中。

注意：在不同的《计算机组成原理》教材中，关于组相联映射的介绍并不相同。通常采用唐朔飞教材中的方式，但本题中采用的是蒋本珊教材中的方式。可以推断两次命题的老师应该不是同一位老师，这也给考生答题带来了困扰。

18

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

正确答案：C
字段直接编码方式将微命令字段分成若干个小字段，互斥性微命令组合在同一字段中，相容性微命令分在不同字段中，每个字段还要留出一个状态，表示本字段不发出任何微命令。5 个互斥类分别包含 7、3、12、5 和 6 个微命令，需要 3、2、4、3 和 3 位，共 15 位。

19

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

正确答案：C
总线频率为 100 MHz，则时钟周期为 10ns。总线位宽与存储字长都是 32 位，故每一个时钟周期可传送一个 32 位存储字。猝发式发送可以连续传送地址连续的数据，故总的传送时间为：传送地址 10ns，传送 128 位数据 40ns，共需 50ns。

20

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

正确答案：D
USB（通用串行总线）的特点有：① 即插即用；② 热插拔；③ 有很强的连接能力，采用菊花链形式将众多外设连接起来；④ 有很好的可扩充性，一个 USB 控制器可扩充高达 127 个外部USB 设备；⑤ 高速传输，速度可达 480Mbps。所以 A、B、C 选项都符合 USB 总线的特点。对于 D, USB 是串行总线，不能同时传输 2 位数据。

21

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

Ⅰ. I/O 接口中的命令字

Ⅱ. I/O 接口中的状态字

Ⅲ. 中断类型号

正确答案：D
根据总线组成，I/O 接口与 CPU 之间的 I/O 总线有数据线、控制线和地址线。控制线和地址线都是单向传输的，从 CPU 传送给 I/O 接口，而 I/O 接口中的命令字、状态字以及中断类型号均是由 I/O 接口发往 CPU 的，故只能通过 I/O 总线的数据线传输。

22

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

Ⅰ. 关中断

Ⅱ. 保存通用寄存器的内容

Ⅲ. 形成中断服务程序入口地址并送 PC

正确答案：B
在响应中断处理流程中，中断隐指令完成的操作包括：①关中断；②保护断点；③引出中断服务程序（形成中断服务程序入口地址并送 PC）,所以只有 I、III 正确。Ⅱ 中的保存通用寄存器的内容是在进入中断服务程序后首先进行的操作。

操作系统

23

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

正确答案：C

本题关键是对 “在用户态发生”（与上题的 “执行” 区分）的理解。

对于 A，系统调用是操作系统提供给用户程序的接口，系统调用发生在用户态，被调用程序在核心态下执行。

对于 B，外部中断是用户态到核心态的 “门”，也发生在用户态，在核心态完成中断过程。

对于 C，进程切换属于系统调用执行过程中的事件，只能发生在核心态。

对于 D，缺页产生后，在用户态发生缺页中断，然后进入核心态执行缺页中断服务程序。

24

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

正确答案：B
子程序调用只需保存程序断点，即该指令的下一条指令的地址；中断调用子程序不仅要保护断点（PC 的内容），而且要保护程序状态字寄存器的内容 PSW。在中断处理中，最重要的两个寄存器是 PC 和 PSWR。

25

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

正确答案：B
在程序装入时，可以只将程序的一部分装入内存，而将其余部分留在外存，就可以自动程序执行。采用连续分配方式时，会使相当一部分内存空间都处于暂时或 “永久” 的空闲状态，造成内存资源的严重浪费，也无法从逻辑上扩大内存容量，因此虚拟内存的实现只能建立在离散分配的内存管理的基础上。有以下三种实现方式：①请求分页存储管理；②请求分段存储管理；③请求段页式存储管理。虚拟存储器容量既不受外存容量限制，也不受内存容量限制，而是由 CPU 的寻址范围决定的。

26

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

正确答案：A
设备管理软件一般分为以下层次：用户层、与设备无关的系统调用处理层、设备驱动程序以及中断处理程序。

27

假设 5 个进程 $P_{0}$ 、 $P_{1}$ 、 $P_{2}$ 、 $P_{3}$ 、 $P_{4}$ 共享三类资源 $R_{1}$ 、 $R_{2}$ 、 $R_{3}$ ，这些资源总数分别为 18、6、22。T0 时刻的资源分配情况如下表所示，此时存在的一个安全序列是（）。

正确答案：D

首先求得各进程的需求矩阵 Need 与可利用资源矢量 Available：

比较 Need 和 Available 可以发现，初始时进程 $P_{1}$ 与 $P_{3}$ 可满足需求，排除 A、C。尝试给 $P_{1}$ 分配资源，则 $P_{1}$ 完成后 Available 将变为 (6,3,6)，无法满足 $P_{0}$ 的需求，排除 B。尝试给 $P_{3}$ 分配资源，则 $P_{3}$ 完成后 Available 将变为 (4,3,7)，该向量能满足其他所有进程的需求。所以，以 $P_{3}$ 开头的所有序列都是安全序列。

28

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

Ⅰ. 若该文件的数据不在内存中，则该进程进入睡眠等待状态

Ⅱ. 请求 read 系统调用会导致 CPU 从用户态切换到核心态

Ⅲ. read 系统调用的参数应包含文件的名称

正确答案：A
对于 I，当所读文件的数据不在内存时，产生中断（缺页中断），原进程进入阻塞状态，直到所需数据从外存调入内存后，才将该进程唤醒。对于 II，read 系统调用通过陷入将 CPU 从用户态切换到核心态，从而获取操作系统提供的服务。对于Ⅲ，要读一个文件首先要用 open 系统调用打开该文件。open 中的参数包含文件的路径名与文件名，而 read 只需要使用 open 返回的文件描述符，并不使用文件名作为参数。read 要求用户提供三个输入参数：①文件描述符 fd；②buf 缓冲区首址；③传送的字节数 n。read 的功能是试图从 fd 所指示的文件中读入 n 个字节的数据，并将它们送至由指针 buf 所指示的缓冲区中。

29

一个多道批处理系统中仅有 $P_{1}$ 和 $P_{2}$ 两个作业， $P_{2}$ 比 $P_{1}$ 晚 5ms 到达，它们的计算和 I/O 操作顺序如下：

$P_{1}$ ：计算 60ms，I/O 80ms，计算 20ms

$P_{2}$ ：计算 120ms，I/O 40ms，计算 40ms

若不考虑调度和切换时间，则完成两个作业需要的时间最少是（）。

正确答案：B

由于 $P_{2}$ 比 $P_{1}$ 晚 5ms 到达， $P_{1}$ 先占用 CPU, 作业运行的甘特图如下所示。

30

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

正确答案：C
选项 A、B、D 显然是可以进行处理机调度的情况。对于 C，当进程处于临界区时，说明进程正在占用处理机，只要不破坏临界资源的使用规侧，是不会影响处理机调度的。比如，通常访问的临界资源可能是慢速的外设（如打印机），如果在进程访问打印机时，不能进行处理机调度，那么系统的性能将是非常差的。

31

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

正确答案：A
在引入线程后，进程依然还是资源分配的基本单位，线程是调度的基本单位，同一进程中的各个线程共享进程的地址空间。在用户级线程中，有关线程管理的所有工作都由应用程序完成，无须内核的干预，内核意识不到线程的存在。

32

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

正确答案：B
对于 A，重排 I/O 请求次序也就是进行 I/O 调度，从而使进程之间公平地共享磁盘访问，减少 I/O 完成所需要的平均等待时间。对于 C，缓冲区结合预读和滞后写技术对于具有重复性及阵发性的 I/O 进程改善磁盘 I/O 性能很有帮助。对于 D，优化文件物理块的分布可以减少寻找时间与延迟时间，从而提高磁盘性能。在一个磁盘上设置多个分区与改善设备/O 性能并无多大联系，相反还会带来处理的复杂和降低利用率。

计算机网络

33

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

正确答案：B
ICMP 报文作为数据字段封装在 IP 分组中，因此，IP 协议直接为 ICMP 提供服务。UDP 和 TCP 都是传输层协议，为应用层提供服务。PPP 协议是链路层协议，为网络层提供服务。

34

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

正确答案：C
此题考查物理层接口特性，过程特性定义各条物理线路的工作过程和时序关系。

35

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

正确答案：A
考虑到局域网信道质量好，以太网采取了两项重要的措施以使通信更简便：① 采用无连接的工作方式；② 不对发送的数据帧进行编号，也不要求对方发回确认。因此，以太网提供的服务是不可靠的服务，即尽最大努力的交付。差错的纠正由高层完成。

36

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

正确答案：B
本题考察回退 N 帧的极限，即求从发送一个帧到接收到这个帧的确认为止的时间内最多可以发送多少数据帧。要尽可能多发帧，应以短的数据帧计算，首先计算出发送一帧的时间：

128 \times 8/ (16 \times 1 0^{3}) = 64

ms；发送一帧到收到确认为止的总时间：

64 + 270 \times 2 + 64 = 668

ms；这段时间总共可以发送

668/64 = 10.4

（帧），发送这么多帧至少需要用

4

位比特进行编号。

37

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

I. 运行路由协议，设置路由表

II. 监测到拥塞时，合理丢弃 IP 分组

III. 对收到的 IP 分组头进行差错校验，确保传输的 IP 分组不丢失

IV. 根据收到的 IP 分组的目的 IP 地址，将其转发到合适的输出线路上

正确答案：C
I 和 V 显然是 IP 路由器的功能。对于Ⅱ，当路由器监测到拥塞时，可合理丢弃 IP 分组，并向发出该 IP 分组的源主机发送一个源点抑制的 ICMP 报文。对于 III，路由器对收到的 IP 分组首部进行差错检验，丢弃有差错首部的报文，但不保证 IP 分组不丢失。对于 IV，这表述的也就是路由器的路由功能。

38

ARP 协议的功能是（）。

正确答案：A
在实际网络的数据链路层上传送数据时，最终必须使用硬件地址，ARP 协议是将网络层的 IP 地址解析为数据链路层的 MAC 地址。

39

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

正确答案：D
子网掩码的第 3 个字节为 11111100，可知前 22 位为子网号、后 10 位为主机号。IP 地址的第 3 个字节为 01001101（下画线为子网号的一部分），将主机号（即后 10 位）全置为 1，可以得到广播地址为 180.80.79.255。

40

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

正确答案：D
SMTP 采用 “推” 的通信方式，在用户代理向邮件服务器及邮件服务器之间发送邮件时，SMTP 客户主动将邮件“推”送到 SMTP 服务器。而 POP3 采用 “拉” 的通信方式，当用户读取邮件时，用户代理向邮件服务器发出请求，“拉”取用户邮箱中的邮件。

解答题

数据结构

41

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

(1) 给出完整的合并过程，并求出最坏情况下比较的总次数。

(2) 根据你的合并过程，描述 $N (N \geq 2)$ 个不等长升序表的合并策略，并说明理由。

42

假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading" 和 “being” 的存储映像如下图所示。

设 str1 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为 | data | next |，请设计一个时间上尽可能高效的算法，找出由 str1 和 str2 所指向两个链表共同后缀的起始位置（如图中字符 i 所在的结点位置 p）。要求：

1）给出算法的基本设计思想。

2）根据设计思想，采用 C 或 C++ 或 Java 语言描述算法，关键之处给出注释。

3）说明你所设计算法的时间复杂度。

顺序遍历两个链表到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另一个链表长 k 个结点，我们先在长链表上遍历 k 个结点，之后同步遍历两个链表，这样就能够保证它们同时到达最后一个结点。由于两个链表从第一个公共结点到链表的尾结点都是重合的，所以它们肯定同时到达第一个公共结点。

算法的基本设计思想：

①分别求出 strl 和 str2 所指的两个链表的长度 m 和 n。

②将两个链表以表尾对齐：令指针 p、q 分别指向 strl 和 str2 的头结点，若 $m \geq n$ ，则使 p 指向链表中的第 m-n+1 个结点；若 $m < n$ ，则使 q 指向链表中的第 n-m+1 个结点，即使指针 p 和 q 所指的结点到表尾的长度相等。

③反复将指针 p 和 q 同步向后移动，并判断它们是否指向同一结点。若 p 和 q 指向同一结点，则该点即为所求的共同后缀的起始位置。

2）算法的 C 语言代码描述：

struct Node {
  int data;
  Node *next;
};

int getLength(Node *h) {
  int length = 0;
  Node *p = h->next;
  while (p) {
    length++;
    p = p->next;
  }
  return length;
}

Node *findCommonSuffix(Node *h1, Node *h2) {
  Node *p1 = h1;
  Node *p2 = h2;
  int m = getLength(h1);
  int n = getLength(h2);
  if (m > n) {
    for (int i = 0; i < m-n; i++) {
      p1 = p1->next;
    }
  } else {
    for (int i = 0; i < n-m; i++) {
      p2 = p2->next;
    }
  }
  while (p1 != p2) {
    p1 = p1->next;
    p2 = p2->next;
  }
  return p1;
}

【评分说明】 ① 若考生所给算法实现正确，且时间复杂度为 O(m+n)，可给 12分；若算法正确，但时间复杂度超过 O(m+n)，则最高可给 9 分。

② 若在算法的基本设计思想描述中因文字表达没有非常清晰反映出算法思路，但在算法实现中能够清晰看出算法思想且正确的，可参照①的标准给分。

③ 若算法的基本设计思想描述或算法实现中部分正确，可参照①中各种情况的相应给分标准酌情给分。

③ 时间复杂度为 O(len1+len2) 或 O(max(len1,len2)), 其中 len1、len2 分别为两个链表的长度。

组成原理

43

假定某计算机的 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) 为了提高性能，主存采用四体低位交叉存储模式，工作时每 1/4 个存储周期启动一个体。若每个体的存储周期为 50ns，则该主存能提供的最大带宽是多少？

44

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

该计算机采用 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 条指令执行过程中， $I_{3}$ 的 ID 段和 $I_{4}$ 的 IF 段被阻塞的原因各是什么？

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

1）x 的机器码为 $[x]_{补}$ = 1111 1101 1111 1111B，即指令执行前 (R1)=FDFFH，右移 1 位后为 1111 1110 1111 1111B，即指令执行后 (R1) = FEFFH。（2 分）

2）每个时钟周期只能有一条指令进入流水线，从第 5 个时钟周期开始，每个时钟周期都会有一条指令执行完毕，故至少需要 4+(5-1)=8 个时钟周期。（2 分）

3） $I_{3}$ 的 ID 段被阻塞的原因：因为 $I_{3}$ 与 $I_{1}$ 和 $I_{2}$ 都存在数据冒险，需等到 $I_{1}$ 和 $I_{2}$ 将结果写回寄存器后， $I_{3}$ 才能读寄存器内容，所以 $I_{3}$ 的 ID 段被阻塞（1 分）。 $I_{4}$ 的 IF 段被阻塞的原因：因为 $I_{4}$ 的前一条指令 $I_{3}$ 在 ID 段被阻塞，所以 $I_{4}$ 的 IF 段被阻塞（1 分）。

注意：要求“按序发射，按序完成”，故 2) 中下一条指令的 IF 必须和上一条指令的 ID 并行，以免因上一条指令发生冲突而导致下一条指令先执行完。

4）因 2*x 操作有左移和加法两种实现，故 x=x*2+a 对应的指令序列为：

I1    LOAD  R1, [x]
I2    LOAD  R2, [a]
I3    SHL   R1       // 或者 ADD R1, R1
I4    ADD   R1, R2
I5    STORE R2, [x]

这 5 条指令在流水线中的执行过程如下表所示：

故 x=x*2+a 语句最少需要 17 个时钟周期。

操作系统

45

某请求分页系统的局部页面置换策略如下：系统从 0 时刻开始扫描，每隔 5 个时间单位扫描一轮驻留集（扫描时间忽略不计），本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次被分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。

假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为 32、15、21、41。进程 P 依次访问的 <虚拟页号，访问时刻> 是：

<1, 1>、<3, 2>、<0, 4>、<0, 6>、<1, 11>、<0, 13>、<2, 14>。请回答下列问题。

(1) 访问<0, 4>时，对应的页框号是什么？

(2) 访问<1, 11>时，对应的页框号是什么？说明理由。

(3) 访问<2, 14>时，对应的页框号是什么？说明理由。

(4) 该策略是否适合于时间局部性好的程序？说明理由。

46

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

(1) 假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号，索引表项中块号最少占多少字节？可支持的单个文件最大长度是多少字节？

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

计算机网络

47

主机 H 通过快速以太网连接 Internet，IP 地址为 192.168.0.8，服务器 S 的 IP 地址为 211.68.71.80。H 与 S 使用 TCP 通信时，在 H 上捕获的其中 5 个 IP 分组如题 47-a 表所示。

No.	Ans	No.	Ans	No.	Ans	No.	Ans	No.	Ans
1	B	2	C	3	D	4	B	5	C
6	B	7	A	8	D	9	A	10	B
11	C	12	D	13	D	14	C	15	D
16	C	17	A	18	A	19	D	20	B
21	D	22	A	23	D	24	D	25	C
26	A	27	C	28	B	29	A	30	A
31	B	32	A	33	B	34	B	35	C
36	A	37	D	38	D	39	C	40	A

No.	Ans	No.	Ans	No.	Ans	No.	Ans	No.	Ans
1	D	2	C	3	D	4	C	5	B
6	A	7	C	8	B	9	B	10	D
11	A	12	D	13	B	14	B	15	D
16	A	17	D	18	B	19	A	20	D
21	A	22	D	23	A	24	C	25	B
26	A	27	D	28	B	29	B	30	C
31	C	32	B	33	C	34	C	35	D
36	C	37	B	38	D	39	A	40	A

No.	Ans	No.	Ans	No.	Ans	No.	Ans	No.	Ans
1	A	2	B	3	B	4	C	5	C
6	D	7	A	8	C	9	D	10	A
11	B	12	D	13	A	14	B	15	D
16	A	17	C	18	D	19	C	20	C
21	D	22	C	23	B	24	A	25	D
26	B	27	D	28	D	29	A	30	C
31	B	32	C	33	A	34	B	35	B
36	D	37	D	38	C	39	C	40	B

No.	Ans	No.	Ans	No.	Ans	No.	Ans	No.	Ans
1	B	2	A	3	A	4	B	5	C
6	C	7	C	8	A	9	D	10	A
11	D	12	D	13	B	14	D	15	D
16	A	17	C	18	C	19	C	20	D
21	D	22	B	23	C	24	B	25	B
26	A	27	D	28	A	29	B	30	C
31	A	32	B	33	B	34	C	35	A
36	B	37	C	38	A	39	D	40	D

No.	Ans	No.	Ans	No.	Ans	No.	Ans	No.	Ans
1	B	2	C	3	D	4	B	5	C
6	B	7	A	8	D	9	A	10	B
11	C	12	D	13	D	14	C	15	D
16	C	17	A	18	A	19	D	20	B
21	D	22	A	23	D	24	D	25	C
26	A	27	C	28	B	29	A	30	A
31	B	32	A	33	B	34	B	35	C
36	A	37	D	38	D	39	C	40	A

No.	Ans	No.	Ans	No.	Ans	No.	Ans	No.	Ans
1	D	2	C	3	D	4	C	5	B
6	A	7	C	8	B	9	B	10	D
11	A	12	D	13	B	14	B	15	D
16	A	17	D	18	B	19	A	20	D
21	A	22	D	23	A	24	C	25	B
26	A	27	D	28	B	29	B	30	C
31	C	32	B	33	C	34	C	35	D
36	C	37	B	38	D	39	A	40	A

No.	Ans	No.	Ans	No.	Ans	No.	Ans	No.	Ans
1	A	2	B	3	B	4	C	5	C
6	D	7	A	8	C	9	D	10	A
11	B	12	D	13	A	14	B	15	D
16	A	17	C	18	D	19	C	20	C
21	D	22	C	23	B	24	A	25	D
26	B	27	D	28	D	29	A	30	C
31	B	32	C	33	A	34	B	35	B
36	D	37	D	38	C	39	C	40	B

No.	Ans	No.	Ans	No.	Ans	No.	Ans	No.	Ans
1	B	2	A	3	A	4	B	5	C
6	C	7	C	8	A	9	D	10	A
11	D	12	D	13	B	14	D	15	D
16	A	17	C	18	C	19	C	20	D
21	D	22	B	23	C	24	B	25	B
26	A	27	D	28	A	29	B	30	C
31	A	32	B	33	B	34	C	35	A
36	B	37	C	38	A	39	D	40	D

No.	Ans	No.	Ans	No.	Ans	No.	Ans	No.	Ans
1	B	2	C	3	D	4	B	5	C
6	B	7	A	8	D	9	A	10	B
11	C	12	D	13	D	14	C	15	D
16	C	17	A	18	A	19	D	20	B
21	D	22	A	23	D	24	D	25	C
26	A	27	C	28	B	29	A	30	A
31	B	32	A	33	B	34	B	35	C
36	A	37	D	38	D	39	C	40	A

No.	Ans	No.	Ans	No.	Ans	No.	Ans	No.	Ans
1	D	2	C	3	D	4	C	5	B
6	A	7	C	8	B	9	B	10	D
11	A	12	D	13	B	14	B	15	D
16	A	17	D	18	B	19	A	20	D
21	A	22	D	23	A	24	C	25	B
26	A	27	D	28	B	29	B	30	C
31	C	32	B	33	C	34	C	35	D
36	C	37	B	38	D	39	A	40	A

No.	Ans	No.	Ans	No.	Ans	No.	Ans	No.	Ans
1	A	2	B	3	B	4	C	5	C
6	D	7	A	8	C	9	D	10	A
11	B	12	D	13	A	14	B	15	D
16	A	17	C	18	D	19	C	20	C
21	D	22	C	23	B	24	A	25	D
26	B	27	D	28	D	29	A	30	C
31	B	32	C	33	A	34	B	35	B
36	D	37	D	38	C	39	C	40	B

No.	Ans	No.	Ans	No.	Ans	No.	Ans	No.	Ans
1	B	2	A	3	A	4	B	5	C
6	C	7	C	8	A	9	D	10	A
11	D	12	D	13	B	14	D	15	D
16	A	17	C	18	C	19	C	20	D
21	D	22	B	23	C	24	B	25	B
26	A	27	D	28	A	29	B	30	C
31	A	32	B	33	B	34	C	35	A
36	B	37	C	38	A	39	D	40	D