2008年12月考研的408试题，网上能找到的最早的408试题，本篇为大题部分，小题见上一篇。

声明：

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

二、综合应用：

第41~47题，共70分。

「41」（10分）、

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

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

问：

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

答：

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

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

「42」（15分）、

已知一个带有头结点的单链表，结点结构为[data|link]，假设该链表只给出了头指针list。

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

问：

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

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

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

答：

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

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

3、

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

int FindBackwardsKthNode(LinkedList list, 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;
}

数据结构的定义不能少，算法部分只要能得到正确的结果就能得分，实在想不出来就用暴力法。

有兴趣可以做一下相关的👉力扣第19题——删除链表的倒数第N个结点

「43」（8分）、

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

问答：

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

1、以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时间的百分比是多少？

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

问：

下表给出了上述指令{加法指令}取指和译码阶段每个节拍{时钟周期}的功能和有效控制信号，请按表中描述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号？

答：

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

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

「45」（7分）、

三个进程P1,P2,P3互斥使用一个包含N{N是正整数}个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数个数。

问：

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

答：

PV操作大题，确定信号量是关键。首先，最容易想到的就是互斥信号量mutex控制进程P1,P2,P3间互斥地使用缓冲区。同步信号量odd控制P1向P2反馈往缓冲区生产了奇数，同步信号量even控制P1向P3反馈往缓冲区生产了偶数，同步信号量empty控制P2,P3向P1反馈从缓冲区消费了正整数。

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分）、

请求分页管理系统中，按字节编址，假设某进程的页表内容如下表所示：

页面大小为4KB，一次内存的访问时间是100ns，一次快表{TLB}的访问时间是10ns，处理一次缺页的平均时间为exp10(8)ns——已包含更新快表和页表的时间，进程的驻留集大小固定为2，采用最近最少使用置换算法{LRU}和局部淘汰策略。

假设：①TLB初始为空；②地址转换时先访问TLB，若TLB未命中再访问页表，且忽略访问页表之后的TLB更新时间；③存在位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。
设有虚地址访问序列(0x2362,0x1565,0x25A5)。

问答：

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

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

①访问0x2362→2号页，查TLB：没有{10ns}，查页表：有{100ns}，从内存中获取该页{100ns}，更新TLB{0ns}，共耗时210ns。
②访问0x1565→1号页，查TLB：没有{10ns}，查页表：没有{100ns}，缺页中断并更新页表和TLB{exp10(8)ns}，缺页中断处理完还需要调页，查TLB：有{10ns}，从内存中获取该页{100ns}，共100,000,220ns。
③访问0x25A5→2号页，查TLB：有{10ns}，从内存中获取该页{100ns}，共110ns。

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

2、进程的驻留集大小为2，说明进程的页表中最多只能有2个页的存在位为1。访问0x2362调入2号页占了驻留集1个位置，访问0x1565调入1号页，LRU算法会把0号页从页表中淘汰，其页框号0x101分配给1号页，于是0x1565的实地址为0x101565。

「47」（9分）、

某网络拓扑如下图所示，路由器R1通过接口E1、E2分别连接局域网1、局域网2，通过接口L0连接路由器R2，并通过路由器R2连接域名服务器与互联网。
R1的L0接口的IP地址是202.118.2.1。
R2的L0接口的IP地址是202.118.2.2，L1接口的IP地址是130.11.201.1，E0接口的IP地址是202.118.3.1。
域名服务器的IP地址是202.118.3.2。
R1和R2的路由表结构都为：[目的网络地址|子网掩码|下一跳IP地址|接口]。

问答：

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

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

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

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

2、对路由器R1来说，局域网1与接口E1直连，局域网2与接口L2直连，子网1和子网2都是25位子网掩码。路由器R1的路由表有一项到达域名服务器的专用路由202.118.3.2/32，有一项到达互联网的默认路由0.0.0.0/0，都从接口L0转发，且下一跳跳往路由器R2的L0接口。

3️⃣请采用路由聚合技术，给出R2到局域网1和局域网2的路由？

3、局域网1和局域网2的地址可以聚合为202.118.1.0/24，对路由器R2来说，到达局域网1和局域网2都从L0接口转发。