2008年12月考研的408试题，次年出考纲时会放出真题，本篇为大题部分，小题见上一篇。

声明：

• ℍ和𝔹分别表示十六进制数和二进制数，否则为十进制数。
• exp()和log()分别是以2为底的指数和对数，exp10()以10为底。
• 乘除号用最朴素的×÷，分数用/，⌊⌋⌈⌉分别是向上向下取整。
• 英文字母变量用的是手写体，题干某些描述较真题有修改。

二、综合应用：

第41～47题，共70分。

№41（10分）

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

①设最短路径初始时仅包含初始顶点，令当前顶点𝑢为初始顶点；
②选择离u最近且尚未在最短路径中的一个顶点𝑣，加入最短路径中，修改当前顶点𝑢=𝑣；
③重复步骤②，直到𝑢是目标顶点为止。

问答：

1️⃣上述方法是否可行？若可行，请证明；否则，请举例说明。

〖𝟙〗不行。这是典型的局部最优非全局最优，举例下图中从0到5的路径：

正确的算法是：求解单源最短路的Dijkstra算法。

№42（15分）

已知一个带有头结点的单链表，结点结构为［data｜link］，假设该链表只给出了头指针head。

在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第𝑘｛𝑘为正整数｝个位置上的结点。若查找成功，输出该结点的data值，并返回1，否则，只返回0。

问答：

1️⃣描述该算法的基本设计思想。

〖𝟙〗前后指针法。定义两个指针变量p,q，初始时均指向头结点的下一个结点，即链表的第一个结点，p先沿链表移动𝑘个结点，然后q跟随p同步移动，当p到达链表最后一个结点时，q所指即是倒数第𝑘个结点。以上过程仅遍历链表一次。

2️⃣描述设该算法的详细实现步骤。

〖𝟚〗如下，

①初始时p,q指向链表头结点head的下一个结点，先让p向前移动，每移动一下𝑘减1；
②若p指向空结点了，但𝑘不为0，说明链表长度不够𝑘，返回0；
③否则，𝑘等于0，可以让q随p一起移动，直到p的下一结点为空，查找成功；
④算法结束。

3️⃣根据设计思想和实现步骤，采用C/C++编程实现，关键之处给出简要注释。

〖𝟛〗数据结构的定义不能少，算法部分只要能得到正确的结果就能得分，实在想不出来就用暴力法。
链表相关可以练习👉力扣第19题。

typedef int ElemType;
typedef struct LinkNode {
    ElemType data;
    struct LinkNode *link;
}* LinkedList;

int FindBackwardsKthNode(LinkedList head, int k)
{
    LinkedList p = list->link, q = list->link;
    while (p && k--)
        p = p->link; // p移动到第k个结点处
    if (k != 0)
        return 0; // 链表长度小于k
    while (p->link)
    {
        p = p->link; q = q->link; // q同步
    }
    printf("%d", q->data);
    return 1;
}

№43（8分）

某计算机的CPU主频为500MHz，CPI为5，即执行每条指令平均需5个时钟周期。假定某外设的数据传输率为0.5MBps，采用中断方式与主机进行数据传送，以32bit为传输单位，对应的中断服务程序包含18条指令，中断服务的其它开销相当于2条指令的执行时间。

问答：

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

〖𝟙〗以1秒为基准。
1秒内，外设需要申请0.5×exp10(6)B÷32b=0.125×exp10(6)次中断。
1次中断相当于18+2=20条指令的执行时间，需占用20×5=100个时钟周期。
1秒内，外设需占用0.125×exp10(6)×100=12.5×exp10(6)个时钟周期。
而1秒内CPU共有500×exp10(6)个时钟周期。
使用中断，该外设I/O占CPU时间比：(12.5×exp10(6))÷(500×exp10(6))=1/40=2.5%。

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

〖𝟚〗以1秒为基准。
1秒内，DMA次数为5×exp10(6)B÷5000B=1000次，需占用1000×500=0.5×exp10(6)个时钟周期。
使用DMA，该外设I/O占CPU时间比：(0.5×exp10(6))÷(500×exp10(6))=1/1000=0.1%。

№44（13分）

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

问答：

1️⃣题44-附2给出了上述加法指令取指和译码阶段每个节拍的功能和有效控制信号，请按表中描述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号？

〖𝟙〗一步步分析加法指令ADD [R1], R0需要完成的动作即可，有效控制信号很好确定。

①将R1的内容送入MAR，指明第二个加数在主存中的地址。
②从主存中读出第二个加数，通过数据总线DB打入MDR。
③可以把读出的第二个加数送入寄存器A；也可以把R0的内容送入寄存器A｛送R0的内容与读主存不冲突｝，可在②完成，少一步。
④执行加法运算，从R0和A中获取两个加数送给ALU运算，结果保存到AC。
⑤结果送入MDR，准备写回主存[R1]指明的地址｛已在①指明｝，MAR不需修改。
⑥写回主存，MDR的内容经数据总线DB写回主存MAR指明的地址。

№45（7分）

三个进程𝐏𝟷,𝐏𝟸,𝐏𝟹互斥使用一个包含𝑁｛𝑁是正整数｝个单元的缓冲区。𝐏𝟷每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；𝐏𝟸每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；𝐏𝟹每次用geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数个数。

问答：

1️⃣请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义，要求用伪代码描述。

〖𝟙〗PV操作大题，确定信号量是关键。首先，最容易想到的就是互斥信号量mutex控制𝐏𝟷,𝐏𝟸,𝐏𝟹间互斥地使用缓冲区，初值1表示有1个缓冲区。同步信号量odd控制𝐏𝟷向𝐏𝟸反馈往缓冲区生产了奇数，初值0表示有0个奇数，同步信号量even控制𝐏𝟷向𝐏𝟹反馈往缓冲区生产了偶数，初值0表示有0个偶数，同步信号量empty控制𝐏𝟸,𝐏𝟹向𝐏𝟷反馈从缓冲区消费了正整数，初值𝑁表示有𝑁个空位。

semaphore mutex = 1;
semaphore odd = 0, even = 0, empty = N;
Process P1()
{
    m = produce();  // 生产一个正整数
    P(empty);       // 判断缓冲区是否有空位
    P(mutex);
    put();          // 使用缓冲区
    V(mutex);
    if (m % 2 == 1)
        V(odd);     // 如果是奇数 向P2发出信号
    else
        V(even);    // 如果是偶数 向P3发出信号
}
Process P2()
{
    P(odd);         // 收到P1发来的信号 消费一个奇数
    P(mutex);
    getodd();
    V(mutex);
    V(empty);       // 释放一个缓冲区空位
    countodd();     // 与临界区无关的代码放在临界区外
}
Process P3()
{
    P(even);        // 收到P1发来的信号 消费一个偶数
    P(mutex);
    geteven();
    V(mutex);
    V(empty);       // 释放一个缓冲区空位
    counteven();    // 与临界区无关的代码放在临界区外
}

№46（8分）

请求分页管理系统中，按字节编址，假设某进程的页表内容如题46-附1所示，页大小为4KB，一次内存的访问时间是100ns，一次快表TLB的访问时间是10ns，处理一次缺页的平均时间为exp10(8)ns｛已包含更新快表和页表的时间｝，进程的驻留集大小固定为2，采用最近最少使用置换LRU算法和局部淘汰策略。

假设：➊TLB初始为空；➋地址转换时先访问TLB，若TLB未命中再访问页表，且忽略访问页表之后的TLB更新时间；➌有效位为0表示页面不在内存，产生缺页异常，缺页异常处理后，返回到产生缺页异常的指令处重新执行。
设有虚地址访问序列(ℍ2362,ℍ1565,ℍ25A5)。

问答：

1️⃣依次访问上述三个虚地址，各需多少时间？

〖𝟙〗按字节编址，页大小4KB，即页内偏移量占log(4K)＝12位，也就是3个十六进制数，虚地址共4个十六进制数，可以确定虚地址中的最左边的1个十六进制数恰好就是页面号。虚地址的结构是这样：［页面号4位｜页内偏移12位］。

①访问ℍ2362→2号页，查TLB：没有，10ns；查页表：有，100ns；从内存中读取该页，100ns，更新TLB，0ns；共210ns。
②访问ℍ1565→1号页，查TLB：没有，10ns；查页表：没有，100ns，缺页异常并更新TLB和页表，exp10(8)ns；缺页异常处理完还需要调页，查TLB：有但无效，10ns；从内存中读取该页，100ns；共100,000,220ns。
③访问ℍ25A5→2号页，查TLB：有，10ns；从内存中读取该页，100ns；共110ns。

2️⃣基于上述访问序列，虚地址ℍ1565对应的实地址是多少？

〖𝟚〗进程的驻留集大小为2，说明其页表中最多只能有2项的有效位为1。访问ℍ2362调入2号页面占了驻留集1个位置，访问ℍ1565调入1号页面，LRU算法会把0号页面从页表中淘汰，其ℍ101号页框分配给1号页面，于是虚地址ℍ1565对应实地址为ℍ101565。

№47（9分）

某网络拓扑如下图所示，路由器𝐑𝟷通过接口𝐄𝟷、𝐄𝟸分别连接局域网𝟷、局域网𝟸，通过接口𝐋𝟶连接路由器𝐑𝟸，并通过路由器𝐑𝟸连接域名服务器与互联网。
𝐑𝟷的接口𝐋𝟶的IP地址是202.118.2.1。
𝐑𝟸的接口𝐋𝟶的IP地址是202.118.2.2，接口𝐋𝟷的IP地址是130.11.201.1，接口𝐄𝟶的IP地址是202.118.3.1。
域名服务器的IP地址是202.118.3.2。
𝐑𝟷和𝐑𝟸的路由表结构都为：[目的网络地址｜子网掩码｜下一跳IP地址｜接口]。

问答：

1️⃣将IP地址空间202.118.1.0/24划分为2个子网，分别分配给局域网𝟷、局域网𝟸，每个局域网需分配的IP地址数不少于120个。请给出子网划分结果？

〖𝟙〗考察CIDR子网划分。202.118.1.0/24中前3个十进制数不能动，从第4个中拿出1个二进制位作为区分子网号，剩下7个二进制位还要去掉全0和全1，共126个，大于120。将第4个十进制数拆成二进制数。

将子网1分配给局域网𝟷，子网2分配给局域网𝟸。

2️⃣请给出𝐑𝟷的路由表，使其明确包括到局域网𝟷的路由、局域网𝟸的路由、域名服务器的主机路由、互联网的路由？

〖𝟚〗对𝐑𝟷来说，局域网𝟷与接口𝐄𝟷直连，局域网𝟸与接口𝐋𝟸直连，子网1和子网2都是25位子网掩码。路由器𝐑𝟷的路由表有1项到达域名服务器的专用路由202.118.3.2/32，有1项到达互联网的默认路由0.0.0.0/0，都从接口𝐋𝟶转发，且下一跳跳往𝐑𝟸的接口𝐋𝟶。

3️⃣请采用路由聚合技术，给出𝐑𝟸到局域网𝟷和局域网𝟸的路由？

〖𝟛〗局域网𝟷和局域网𝟸的地址可以聚合为202.118.1.0/24，对路由器𝐑𝟸来说，到达局域网𝟷和局域网𝟸都从接口𝐋𝟶转发。