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 & 0 \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 中较小的一半，要求舍弃的长度 相等。

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

2）算法实现

float mergeMedian(int a[], int b[], int n) {
  int i = 0;
  int j = 0;
  // n-1 = i+j
  while (i + j < n-1) {
    if (a[i] <= b[j]) {
      i++;
    } else {
      j++;
    }
  }
  // 在归并数组中下标为 n-1, n 的两个元素
  int prev, next;
  if (a[i] <= b[j]) {
    prev = a[i];
    if (i == n-1) {
      next = b[j];
    } else {
      next = min(a[i+1], b[j]);
    }
  } else {
    prev = b[j];
    if (j == n-1) {
      next = a[i];
    } else {
      next = min(b[j+1], a[i]);
    }
  }
  return 1.0 * (prev + next) / 2;
}

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

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 的补码，结果对 2 的 n 次方取模。因此，n 位无符号整数的加法和减法运算都可以通过 n 位加法器实现。

由于带符号整数使用补码表示，其加减法遵循的公式是：a + b 的补码等于 a 的补码加上 b 的补码，结果对 2 的 n 次方取模；同样，a - b 的补码等于 a 的补码加上 -b 的补码，结果也对 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 对应的块，可减少磁头移动和磁盘 I/O 访问次数。

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.b7.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 头中的字段进行罗列，不给分，其他情况的情给分。