2011 年 408 真题

1） 上三角矩阵 A[6][6]中，第 1 行至第 5 行主对角线上方的元素个数分别为 5, 4, 3, 2, 1, 由此可以画出压缩存储数组中的元素所属行的情况，如下图所示。

用 “ 平移” 的思想，将前 5 个、后 4 个、后 3 个、后 2 个、后 1 个元素，分别移动到矩阵对 角线 (“0”) 右边的行上。图 G 的邻接矩阵 A 如下所示。

$$ A = \begin{bmatrix} 0 & 4 & 6 & \infty & \infty & \infty \\ \infty & 0 & 5 & \infty & \infty & \infty \\ \infty & \infty & 0 & 4 & 3 & \infty \\ \infty & \infty & \infty & 0 & \infty & 3 \\ \infty & \infty & \infty & \infty & 0 & 3 \\ \infty & \infty & \infty & \infty & \infty & 3 \end{bmatrix} $$

2） 据上面的邻接矩阵，画出有向带权图 G, 如下图所示。

(3) 按照算法，先计算各个事件的最早发生时间，计算过程如下：

$ve(0) = 0$;

$ve(1) = ve(0) + a_{0→1} = 4$;

$ve(2) = max ( ve(0) + a_{0→1}, ve(1) + a_{1→2} ) = max(6, 4 + 5) = 9$;

$ve(3) = ve(2) + a_{2→3} = 9 + 4 = 13$;

$ve(4) = ve(2) + a_{2→4} = 9 + 3 = 12$;

$ve(5) = max(ve(3) + a_{3→5}, ve(4) + a_{4→5}) = max(16,15) = 16$;

接下来求各个时间的最迟发生时间，计算过程如下：

$vl(5) = ve(5) = 16$;

$vl(4) = vl(5) - a_{4→5} = 16 - 3 = 13$;

$vl(3) = vl(5) - a_{3→5} = 16 - 3 = 13$;

$vl(2) = min(vl(3) - a_{2→3}, vl(4) - a_{2→4}) = min(9, 10) = 9$;

$vl(1) = vl(2) -a_{1→2} = 4$;

$vl(0) = min(vl(2) - a_{0→2}, vl(1) - a_{0→1}) = min(3, 0) = 0$;

即 ve() 和 vl() 数组如下表所示。

接下来计算所有活动的最早和最迟发生时间 e() 和 l()：

$e(a_{0→1}) = e(a_{0→2}) = ve(0) = 0$;

$e(a_{1→2}) = ve(1) = 4$;

$e(a_{2→3}) = e(a_{2-4}) = ve(2) = 9$;

$e(a_{3→5}) = ve(3) = 13$;

$e(a_{4→5}) = ve(4) = 12$;

$l(a_{4→5}) = vl(5)-a_{4-5} = 16-3 = 13$;

$l(a_{3→5}) = vl(5)-a_{3-5} = 16-3 = 13$;

$l(a_{2→4}) = vl(4)-a_{2-4} = 13-3 = 10$;

$l(a_{2→3}) = vl(3)-a_{2-3} = 13-4 = 9$;

$l(a_{1→2}) = vl(2)-a_{1-2} = 9-5 = 4$;

$l(a_{0→2}) = vl(2)-a_{0-2} = 9-6 = 3$;

$l(a_{0→1}) = vl(1)-a_{0-1} = 4-4 = 0$;

e() 和 l() 数组与它们的差值如下表所示。

满足 l() - e() = 0 的路径就是关键路径，所以关键路径为 a_{0→1}、a_{1→2}、a_{2→3}、a_{3→5},如下图所示（粗线表示），长度为 $4+5+4+3=16$。

(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)范围内。

原因：同样可以用归并排序后的序列来验证，归并排序后必然有形如 $\cdots a \cdots b \cdots$ 的序列出现， 中位数必出现在(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 中较小的一半，要求舍弃的长度 相等。

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

(1) 134 = 128 + 6 = 1000 0110B,所以 x 的机器数为 1000 0110B,故 R1 的内容为 86H。

246 = 255 - 9 = 1111 0110B,所以 y 的机器数为 1111 0110B。

x-y: 1000 0110 + 0000 1010 = (0)1001 0000,括弧中为加法器的进位，故 R5 的内容为 90H。

x+y: 1000 0110 + 1111 0110 = (1)0111 1100,括弧中为加法器的进位，故 R6 的内容为 7CH。

(2) m 的机器数与 x 的机器数相同，皆为 86H=1000 0110B,解释为带符号整数 m（用补码 表示）时，其值为-1111010B = -122。

m-n 的机器数与 x-y 的机器数相同，皆为 90H=1001 0000B,解释为带符号整数 k1（用 补码表示）时，其值为-1110000B = -112。

(3) 能。n 位加法器实现的是模 $2^n$ 无符号整数加法运算。对于无符号整数 a 和 b, a + b 可以直接用加法器实现，而 a-b 可用 a 加 b 的补数实现，即 a - b = a + [-b]_{补}(mod 2^n), 所以 n 位无符号整数加/减运算都可在 n 位加法器中实现。

由于带符号整数用补码表示，补码加/减运算公式为 $[a+b]{补} = [a]{补} + [b]{补} (mod 2^n)$, $[a-b]{补} = [a]{补} + [-b]{补} (mod 2^n)$ 所以 n 位带符号整数加/减运算都可在 n 位加法器中实现。

(4) 带符号整数加/减运算的溢出判断规则为：若加法器的两个输入端（加法）的符号相同， 且不同于输出端（和）的符号，则结果溢出，或加法器完成加法操作时，若次高位的进位和最高 位的进位不同，则结果溢出。

最后一条语句执行时会发生溢出。因为 10000110+11110110=(1)01111100，括弧中为加法器 的进位，根据上述溢出判断规则，可知结果溢出。或因为 2 个带符号整数均为负数，它们相加之 后，结果小于 8 位二进制所能表示的最小负数。

1）存储器按字节编址，虚拟地址空间大小为 16B=24B,故虚拟地址为 24 位；页面大小 为 $4KB = 2^{12}B$,故高 12 位为虚页号。主存地址空间大小为 $1MB = 22B$,故物理地址为 20 位；由于页内地址为 12 位，故高 8 位为页框号。

2）由于 Cache 采用直接映射方式，所以物理地址各字段的划分如下。

| Tag 标记 | Cache 行号 | 块内偏移 |

块大小为 32B，所以块内偏移为 5 位；Cache 共 8 行，故 Cache 行号为 3 位，标记字段为 20-5-3=12 位。

3）虚拟地址 001C60H 的前 12 位为虚页号，即 001H,查看 001H 处的页表项，其对应的 效位为 1，故虚拟地址 001C60H 所在的页面在主存中。页表 001H 处的页框号为 04H,与页内偏 移（虚拟地址后 12 位）拼接成物理地址为 04C60H.物理地址 04C60H=00000100110001100000B, 主存块只能映射到 Cache 的第 3 行（即第 011B 行），由于该行的有效位=1，标记（值为 105H)≠ 04CH（物理地址高 12 位），故不命中。

4）由于 TLB 采用四路组相联，故 TLB 被分为 8/4=2 个组，因此虚页号中高 11 位为 TLB 标记、最低 1 位为 TLB 组号。虚拟地址 024BACH=000000100100101110101100B,虚页号为 000000100100B,TLB 标记为 00000010010B（即 012H),TLB 组号为 0B,因此，该虚拟地址 所对应物理页面只可能映射到 TLB 的第 0 组。组 0 中存在有效位=1、标记=012H 的项，因此 访问 TLB 命中，即虚拟地址 024BACH 所在的页面在主存中。

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);           // 叫号
        为顾客服务；
    }
}

1）在磁盘中连续存放（采取连续结构），磁盘寻道时间更短，文件随机访问效率更高；在 FCB 中加入的字段为：《起始块号，块数》或者《起始块号，结束块号》。

2）将所有的 FCB 集中存放，文件数据集中存放。这样在随机查找文件名时，只需访问 FCB 对应的块，可减少磁头移动和磁盘/O 访问次数。

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

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

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

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

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

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