2010年12月考研的408试题，本篇为大题部分，小题见上一篇。

声明：

• 0x和0b分别表示十六进制和二进制数，其余为十进制数。
• exp()和log()分别是以2为底的指数和对数，exp10()以10为底。
• 乘除号用最朴素的×÷，分数用/，参与计算的英文字母变量用手写体。
• {}里的斜体为补充文字，另外对原题一些容易误会的文字做了修改。
• 图片使用亿图图示绘制。

二、综合应用：

第41~47题，共70分。

「41」（8分）、

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

问答：

1️⃣写出图G的邻接矩阵A。

1、

2️⃣画出有向带权图G。

2、

3️⃣求图G的关键路径，并计算该关键路径的长度？

3、按照关键路径的算法，起点是0号终点是5号，先从起点到终点算出各事件最早发生时间，再从终点到起点算出各事件最晚发生时刻，

vertex_earliest
[0] = 0;
[1] = 4;
[2] = max(6, 4+5) = 9;
[3] = 9 + 4 = 13;
[4] = 9 + 3 = 12;
[5] = max(13+3, 12+3) = 16;

vertex_latest
[5] = 16;
[4] = 16 - 3 = 13;
[3] = 16 - 3 = 13;
[2] = min(13-3, 13-4) = 9;
[1] = 9 - 5 = 4;
[0] = min(9-6, 4-4) = 0;

接下来算出各边代表的活动的最早和最晚发生时刻，

edge_earliest
<0, 1> = <0, 2> = 0;
<1, 2> = 4;
<2, 3> = <2, 4> = 9;
<3, 5> = 13;
<4, 5> = 12;

edge_latest
<4, 5> = 16 - 3 = 13;
<3, 5> = 16 - 3 = 13;
<2, 4> = 13 - 3 = 10;
<2, 3> = 13 - 4 = 9;
<2, 1> = 9 - 5 = 4;
<2, 0> = 9 - 6 = 3;
<1, 0> = 4 - 4 = 0;

满足edge_latest<u,v>=edge_earliest<u,v>的边就是关键路径，0→1→2→3→5，长度为4+5+4+3=16。

「42」（15分）、

一个长度为L{L为正整数}的升序序列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++编程实现，关键之处给出简要注释。

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

1、假设长度都为L。暴力也能得分，用归并排序合并两序列，直接定位中位数。或者用双指针节省空间，p和q初始分别指向A[0]和B[0]，循环L次比较A[p]和B[q]，谁小谁往右移，最后A[p]和B[q]中的小者就是所求中位数。
还有一种较优解，类似二分查找，先得出A和B的中位数a和b，①若a=b，则a或b即为所求中位数，算法结束；②若a<b，则舍弃A左半边，舍弃B右半边，要求舍弃长度一样以保证AB还是等长的；③若a>b，则舍弃A右半边，舍弃B左半边，要求舍弃长度一样以保证AB还是等长的；在保留的两个子序列中重复过程①②③，直到两序列皆只剩1个元素为止，小者就是所求中位数。

2、

// 双指针法
int FindMedian(int[] A, int[] B, int L)
{
    int p = 0, q = 0;
    for (int l = 0; l < L; l++)
      if (A[p] < B[q]) p++;
      else q++;
    return A[p] < B[q] ? A[p] : B[q];
}

// 二分查找法
int FindMedian(int[] A, int[] B, int L)
{
    int Astart = 0, Bstart = 0, Alast = L - 1, Blast = L - 1;
    int Amid, Bmid; // start last 指向闭区间的左右端点 mid 为中位
    while (Astart != Alast || Bstart != Blast)
    {
        Amid = (Astart + Alast) / 2；
        Bmid = (Bstart + Blast) / 2;
        if (A[Amid] == B[Bmid]) return A[Amid]; // 满足①
        else if (A[Amid] < B[Bmid])             // ②
        {
            Astart = Amid + ((Astart + Alast) % 2);
            // 对2取余为1代表A有偶数个元素 要把Amid连同左边舍弃
            Blast = Bmid; // 把B右边舍弃
        }
        else                                    // ③
        {
            Alast = Amid + ((Astart + Alast) % 2);
            // A有偶数个元素 不要把Amid舍弃
            Bstart = Bmid; 
        }
    }
    return A[Astart] < B[Bstart] ? A[Astart] : B[Bstart];
}

3、双指针法，时间复杂度𝜪(L)，空间复杂度𝜪(1)；二分查找法，时间复杂度𝜪(log(L))，空间复杂度𝜪(1)。
有兴趣可以做下相关的力扣第4题👉寻找两个正序数组的中位数。

「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的值分别是多少，用十进制表示？

1、2、x是134的原码0x86，y是246的原码0xF6，m是0x86以补码解释-122，n是0xF6以补码解释-9，z1是0x86-0xF6=0x86+0x0A=0x90以原码解释144，z2是0x86+0xF6=0x7C{上溢}以原码解释124，m是0x86以补码解释-122，n是0xF6以补码解释-9，k1是0x90以补码解释-112，k2是0x7C以补码解释124；R1=R3=0x86，R2=R4=0xF6，R5=R7=0x90，R6=R8=0x7C。

3️⃣上述程序段涉及无符号整数加／减、带符号整数加／减运算，这四种运算能否利用同一个
加法器辅助电路实现？

3、能。无／带符号整数的加／减运算，都能转为取补、加法实现。

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

带符号整数加／减运算的溢出判断规则为：加法器两输出端数的符号相同，但输出端数的符号变了，则判定为溢出。易知k2的计算会发生溢出。

「44」（12分）、

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

问答：

1️⃣虚拟地址共有几位，哪几位表示虚页号？物理地址共有几位，哪几位表示页框号？

1、页面大小4KB说明在页面号和页框号中页内偏移都占去了后log(4K)=12位。虚拟地址共log(16M)=24位，前12位为虚页号，物理地址共log(1M)=20位，前8位为页框号。

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

2、Cache采用直接映射方式时，物理地址应被划分为3段：[主存字块标记｜Cache块号标记｜块内地址]，块内地址log(32)=5位，Cache块号标记log(8)=3位，主存字块标记20-5-3=12位。

3️⃣虚拟地址0x001C60所在的页面是否在主存中？若在主存中，则该虚拟地址对应的物理地址是什么？访问该地址时是否Cache命中？

3、由1️⃣中对虚拟地址访问Page时的分析，该虚拟地址在0x001=1号页，看表1可知：1号页有效，在主存中，对应物理地址是0x06C60。由2️⃣中对物理地址访问Cache时的分析，0x06C60=0b00000100110001100000，其物理地址将映射到Cache的0b011=3号块，看表2可知：3号块有效，然而高12位的主存字块标记0x04C≠0x105，Cache未命中。

4️⃣假定为该机配置一个四路组相联的TLB共可存放8个页表项，若其当前内容的十六进制如题44-表3所示，则此时虚拟地址0x024BAC所在的页面是否存在主存中？

4、TLB被分为8÷4=2组，该虚拟地址在0x024号页，该页号将映射到TLB的0x024%2=0号组，且被标记为0x24÷2=0x12，看表3可知：0号组中存在有效位=1、标记=0x12的项，即该虚拟地址所在页面在内存中。

「45」（8分）、

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

cobegin {
    process customer[i]
    {
        /* 取号机领一个号 */
        /* 等待叫号 */
        /* 获取服务 */
    }
    process bankteller
    {
        while (TRUE)
        {
            /* 叫号 */
            /* 为顾客提供服务 */
        }
    }
} coend

问：

请添加必要的信号量和PV操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。

答：

PV操作大题，确定信号量是关键。首先，互斥信号量mutex控制客户对取号机的使用。同步信号量empty控制座位向一位顾客反馈有空位，同步信号量full控制座位向营业员反馈有顾客在座，还有一个同步信号量service控制顾客在等待营业员的叫号和服务。

semaphore mutex = 1;
semaphore empty = 10;
semaphore full = 0;
semaphore service = 0;
cobegin {
    process customer[i]
    {
        P(empty);
        P(mutex);
        /* 取号机领一个号 */
        V(mutex);
        V(full);
        P(service); // 等待叫号
        /* 获取服务 */
    }
    process bankteller
    {
        while (TRUE)
        {
            P(full);
            V(empty);
            V(service); // 叫号
            /* 为顾客提供服务 */
        }
    }
} coend

难想到的就是顾客等待叫号和营业员叫号被藏在对service的PV操作里了。

「46」（7分）、

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

问答：

1️⃣在连续、链式、索引三种文件的数据块组织方式中，哪种更合适？为定位文件数据块，需要FCB中设计哪些相关描述字段？

1、在磁盘中，用连续存放的方式最合适，寻道时间短。FCB要有（起始块号，块数）。

2️⃣为快速找到文件，对于FCB，是集中存储好，还是与对应的文件数据块存储在一起好？

2、FCB单独集中起来存储好，这样在随机访问一个文件名时，不需要一步步去找该文件的FCB，可以直接从FCB集中块里找，减少磁盘I/O次数。

「47」（9分）、

某主机的MAC地址为00-15-C5-C1-5E-28，IP地址为10.2.128.100{私有地址}。题47-图1是网络拓扑，题47-表2是该主机进行Web请求的1个以太网帧前80B的十六进制及ASCII码内容，题47-表3是以太网帧的组成，题47-表4是IP分组头的组成。

问答：

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

1、以太网帧的数据部分是IP分组，读表2，两个十六进制数就是一字节，仔细数一下就能得出Web请求的目的MAC地址、目的IP地址在表2蓝色标出，源MAC地址、源IP地址在表2红色标出。0x.40.aa.62.20=64.170.98.32，00-21-27-21-57-EE。

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

2、主机事先知道默认网关的IP地址，由IP地址获取MAC地址的是：地址解析协议ARP。ARP请求报文以广播形式发送，即目的MAC地址是：FF-FF-FF-FF-FF-FF。

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

3、HTTP/1.1持续的非流水线方式工作，服务器响应HTTP请求后一段时间内会保持与客户端的连接。html是纯文本，JPEG图像需要由rfc.html中给的超链接再次获取，故共需6个RTT收到全部内容。

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

4、IP分组转往因特网需将内网私有IP地址转换为NAT路由器的一个全球IP地址，源IP地址字段由10.2.128.100改为101.12.123.15；生存时间TTL减1；重新计算校验和。若IP分组的长度超过输出链路的MTU，则总长度字段、标志字段、片偏移字段也要发生变化。