二、综合应用题：41～47小题，共70分。请将答案写在答题纸指定位置上。
41.(8 分)已知有 6 个顶点(顶点编号为 0～5)的有向带权图 G，其邻接矩阵 A 为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。4 6 &infin &infin &infin 5 &infin &infin &infin 4 3 &infin &infin 3 3
要求：
(1)写出图 G 的邻接矩阵 A。
(2)画出有向带权图 G。
(3)求图 G 的关键路径，并计算该关键路径的长度。
解答：
(1)图G的邻接矩阵 A 如下所示。(图暂缺)
(2)有向带权图 G 如下图所示。(图暂缺)
(3)关键路径为 0à1à2à3à5(如下图所示粗线表示)，长度为 4+5+4+3=16。
42.(15分)一个长度为 L(L&ge1)的升序序列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 的中位数过程如下：
1)若 a=b，则 a 或 b 即为所求中位数，算法结束。
2)若 a
度相等
3)若 a>b，则舍弃序列 A 中较大的一半，同时舍弃序列 B 中较小的一半，要求舍弃的在保留的两个升序序列中，重复过程 1)、2)、3)，直到两个序列中只含一个元素时为止，较小者即为所求的中位数。
(2)(暂缺)
(3)算法的时间复杂度为 O(log2n)，空间复杂度为 O(1)。
43.(11 分)假定在一个 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)计算机内部如何判断带符号整数加/减运算的结果是否发生溢出?上述程序段中，哪些带符号整数运算语句的执行结果会发生溢出?
解答：
(1) R1=134=86H, R5=90H, R6=7CH
134=1000 0110B=86H x-y=1000 0110B-1111 0110B=1001 0000B=90H x+y=1000
0110B+1111 0110B=0111 1100B(溢出)
(2)m=-122,k1=-112
m=1000 0110B，做高位为符号位，则 m 的原码为 1111 1010B=-122n=1111 0110Bn 的原码为 1000 1001=-10k1=m-n=-112。
(3)无符号数和有符号数都是以补码的形式存储，加减运算没有区别(不考虑溢出情况时)，只是输出的时候若是有符号数的最高位是符号位。减法运算求[-x]补的时候，是连同符号位一起按位取反末位加 1，但是如果有溢出情况，这两者是有区别的，所以可以利用同一个加法器实现，但是溢出判断电路不同。
(4)判断方法是如果最高位进位和符号位的进位不同，则为溢出“int k2=m+n”会溢出三种方法可以判断溢出，双符号位、最高位进位、符号相同操作数的运算后与原操作数的符号不同则溢出
44.(12分)某计算机存储器按字节编址，虚拟(逻辑)地址空间大小为16MB，主存(物理)地址空间大小为 1MB，页面大小为 4KBCache 采用直接映射方式，共 8 行主存与 Cache 之间交换的块大小为 32B。系统运行到某一时刻时，页表的部分内容和 Cache的部分内容分别如题 44-a 图、题 44-b 图所示，图中页框号及标记字段的内容为十六进制形式。
题 44-a 图 页表的部分内容
请回答下列问题。
题 44-b 图 Cache 的部分内容
(1)虚拟地址共有几位，哪几位表示虚页号?物理地址共有几位，哪几位表示页框号(物理页号)?
(2)使用物理地址访问 Cache 时，物理地址应划分成哪几个字段?要求说明每个字段的位数及在物理地址中的位置。
(3)虚拟地址 001C60H 所在的页面是否在主存中?若在主存中，则该虚拟地址对应的物理地址是什么?访问该地址时是否 Cache ?要求说明理由。
(4)假定为该机配置一个 4 路组相联的 TLB 共可存放 8 个页表项，若其当前内容(十六进制)如题 44-c 图所示，则此时虚拟地址 024BACH 所在的页面是否存在主存中?要求说明理由.
解答：
题 44-c 图 TLB 的部分内容
(1)24 位、前 12 位20 位、前 8 位。16M=224 故虚拟地址 24 位，4K=212，故页内地址 12 位，所以虚页号为前 12 位1M=220故物理地址 20 位，20-12=8，故前 8 位为页框号。
(2)
主存字块标记(12bit)、cache 字块标记(3bit)、字块内地址(5bit)物理地址 20 位，其中，块大小为 32B=25B 故块内地址 5 位cache 共 8 行，8=23，故字块标记为 3 位20-5-2=12，故主存字块标记为12位。
(3) 在主存中，04C60H, 不，没有 04C 的标记字段001C60H 中虚页号为 001H=1，查页表知其有效位为 1，在内存中该物理地址对应的也表项中，页框号为 04H 故物理地址为 04C60H物理地址 04C60H 在直接映射方式下，对应的行号为 4，有效位为 1 但是标记位为 064H&ne04CH 故不。
(4)在，012 的那个标记是对的。
思路： 标记11位组地址 1 位页内地址 12 位，前 12 位为 0000 0010 0100，组地址位为0，第0组中存在标记为 012 的页，其页框号为 1F，故 024BACH 所在的页面存在主存中。
45.(8 分)某银行提供 1 个服务窗口和 10 个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，经过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：7分)某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题。
(1)在连续、链式、索引三种文件的数据块组织方式中，哪种更合适?要求说明理由。为定位文件数据块，需要 FCB 中设计哪些相关描述字段?
(2)为快速找到文件，对于 FCB，是集中存储好，还是与对应的文件数据块连续存储好?要求说明理由。
解答：
(1) 连续更合适,因为一次写入不存在插入问题,连续的数据块组织方式完全可以满足一次性写入磁盘。同时连续文件组织方式减少了其他不必要的空间开销，而连续的组织方式顺序查找读取速度是最快的。
(2)FCB集中存储好。目录是存在磁盘上的，所以检索目录的时候需要访问磁盘，速度很慢集中存储是将文件控制块的一部分数据分解出去，存在另一个数据结构中，而在目录中仅留下文件的基本信息和指向该数据结构的指针，这样一来就有效地缩短减少了目录的体积，减少了目录在磁盘中的块数，于是检索目录时读取磁盘的次数也减少，于是就加快了检索目录的次数。
题 47-a 图是网络拓扑，题 47-b 图是该主机进行 Web 请求的 1 个以太网数据帧前 80 个
0000 00 21 27 21 51 ee 00 15 c5 c1 5e 28 08 00 45 00 .!|!Q... ..^(..E.
0010 01 ef 11 3b 40 00 80 06 ba 9d 0a 02 80 64 40 aa ...:@... .....d@.
0020 62 20 04 ff 00 50 e0 e2 00 fa 7b f9 f8 05 50 18 b ...P.. .....P.
0030 fa f0 1a c4 00 00 47 45 54 20 2f 72 66 63 2e 68 ......GE T /rfc.h
0040 74 6d 6c 20 48 54 54 50 2f 31 2e 31 0d 0a 41 63 tml HTTP /1.1..Ac
题 47-b 图 以太网数据帧(前 80 字节)请参考图中的数据回答以下问题。
(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 图所示。
6B 6B 2B 46-1500B 4B
目的 MAC 地址
源 MAC 地址 类型 数 据
题 47-c 图 以太网帧结构
CRC
解答：
(1)(暂缺)
(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 是数据帧的字节计数，不属于以太网数据帧的内容。
