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

声明：

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

声明：

• 0x和0b分别表示十六进制数和二进制数，其余为十进制数。
• 0y和0c分别表示十六进制形式补码和二进制形式补码。
• exp()和log()分别是以2为底的指数和对数，exp10()以10为底。
• 乘除号用最朴素的×÷，分数用/，⌊⌋⌈⌉分别是向上向下取整。
• 参与计算的英文字母变量用的是手写体。
• 对原题一些容易误会的文字做了修改。
• 图片使用亿图图示等绘制。

二、综合应用：

第41～47题，共70分。

「41」（15分）、

用单链表保存m个整数，结点的结构为：［data｜link］，且|data|≤n〔n为正整数〕。现要求设计一个时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，

若给定的单链表head为：[HEAD|•]→[21|•]→[-15|•]→[-15|•]→[-7|•]→[15|🅧]，
则删除重复结点后的head为：[HEAD|•]→[21|•]→[-15|•]→[-7|🅧]。

问答：

1️⃣给出算法的基本设计思想？说明你所设计算法的时间复杂度和空间复杂度？

𝟙、使用辅助数组或集合记录链表中已出现过的数值，只需对链表进行一趟扫描。若当前遍历到的数值没出现在集合中，则加入到集合，否则执行链表删除结点操作，链表删除操作需要两个指针。时间复杂度𝜪(m)，空间复杂度𝜪(n)。

2️⃣采用C/C++语言，给出单链表结点的数据类型定义，并描述算法，关键之处给出注释？

𝟚、如下。

typedef struct node
{
    int data;
    struct node *link;    
}* head;

void Deduplication(linked head, int n)
{
    // int seen[n+1] = {0};          用辅助数组来存储已出现的绝对值
    std::unordered_set<int> seen; // 或者用哈希集合
    linked p = head, q;
    while (p != nullptr && (q = p->link) != nullptr)
    {
        int m = q->data >= 0 ? q->data : -q->data; // 绝对值
        if (seen.find(m) == seen.end()) // 第一次出现
        {
            seen.insert(m);
            p = p->link;               // 保留
        }
        else
        {
            p->link = q->link;         // 删除
            free(q);                   // 释放
        }
    }
}

「42」（8分）、

已知含有5个顶点的图G如下图所示。

问答：

1️⃣写出图G的邻接矩阵A，行列下标都从0开始？

𝟙、如下。

2️⃣求A的2次方，矩阵A^2中位于0行3列元素值的含义是什么？

𝟚、0行3列🟰3，表示顶点0到顶点3之间，长度为2的路径有3条。

3️⃣若已知具有n个〔n是大于2的正整数〕顶点的图的邻接矩阵为B，则B的m次方〔m是介于2到n的正整数〕中非零元素的含义是什么？

𝟛、位于i行是列的非零元素含义是：图中顶点i到顶点j之间长度为m的路径条数。相关证明见离散数学——图论。

「43」（13分）、

某16位计算机的主存按字节编码，存取单位为16位，采用16位定长指令字格式；CPU采用单总线结构，主要部分如下图所示。图中R0~R3为通用寄存器，T为暂存器；SR为移位寄存器，可实现➊直送〔mov〕，➋左移一位〔left〕，➌右移一位〔right〕，3种操作，控制信号为“SRop”，SR的输出由信号“SRout”控制；ALU可实现➊直送A〔mova〕，➋A加B〔add〕，➌A减B〔sub〕，➍A按位与B〔and〕，➎A按位或B〔or〕，➏按位非A〔not〕，➐A自增1〔inc〕，7种操作，控制信号为“ALUop”。

问答：

1️⃣图中哪些寄存器是程序员可见的？为何要设置暂存器T？

𝟙、程序员可见的寄存器是R0~R3及PC。由于采用单总线结构，ALU的两端操作数被传来有先后顺序，设置暂存器T是为了让两操作数同时进入ALU。

2️⃣控制信号“ALUop”和“SRop”的位数至少各是多少？

𝟚、“ALUop”的位数至少⌈log(7)⌉=3；“SRop”的位数至少⌈log(3)⌉=2。

3️⃣控制信号“SRout”所控制部件的名称或作用是什么？

𝟛、作用是控制移位器与总线之间数据通路的连接或断开，避免干扰总线正在进行的数据传输。名称是三态门，高电压下为通路。

4️⃣端点①～⑨中，哪些端点须连接到〔IR下面的〕控制部件的输出端？

𝟜、虚线箭头的①②③⑤⑧都是控制信号，由控制部件的输出端产生。

5️⃣为完善单总线数据通路，需要在端点①～⑨中相应的端点之间添加必要的连线。写出连线的起点和终点，以正确表示数据的流动方向？

𝟝、剩下的④⑥⑦⑨要构成数据通路，⑥连⑨，④连⑦。

6️⃣为什么二路选择器MUX的一个输入端是2？

𝟞、指令是16位定长，该机器按字节编址，故每条指令占据2个地址，MUX的一个输入端是2可方便执行(PC)+2。

「44」（10分）、

题43中描述的机器，其部分指令执行过程的控制信号如下图1所示。该机器指令格式如下图2所示，支持寄存器直接和寄存器间接两种寻址方式，寻址方式位分别为0和1，通用寄存器R0~R3的编号分别为0,1,2,3。

问答：

1️⃣该机器的指令系统最多可定义多少条指令？

𝟙、寻址方式各1位，寄存器编号各2位，操作码有16-3×3=7位，最多可定义exp(7)=128条指令。

2️⃣假定inc,shl,sub指令的操作码分别为0x01,0x02,0x03，则以下汇编代码对应的机器代码各是什么？

inc R1            ; R1 + 1 → R1         : 0000001 001 000 000
shl R2, R1        ; (R1) << 1 → R2      : 0000010 010 001 000
sub R3, (R1), R2  ; [(R1)] - [R2] → R3  : 0000011 011 101 010

𝟚、题目不说也能猜出注释中的，(R1)是寄存器直接寻址，[(R1)]是寄存器间接寻址。按照图2填就好，如上。

3️⃣假设寄存器X的输入和输出控制信号分别为“Xin”和“Xout”，其值为1表示有效，为0表示无效，例如PCout=1表示PC内容送总线；存储器控制信号为“MEMop”，用于控制存储器的读和写操作。写出题图1中标号①～⑧处的控制信号或控制信号的取值？

𝟛、没有难度：①0；②mov；③mova；④left；⑤read；⑥sub；⑦mov；⑧SRout。题43第6问，做到取指阶段这，也应当想起是考PC自增。

4️⃣汇编代码➊“sub R1, R3, (R2)”和➋“inc R1”的执行阶段至少各需要多少个时钟周期？

𝟜、单总线，占用一次总线就得算一个时钟周期。
按照图2的执行阶段，分析一下➊➋的动作：➊4个；➋2个。

➊sub R1, R3, (R2):
R2out=1,MARin=1,MEMop=read;
R3out=1,Tin=1;
MDRout=1,MUXop=1,ALUop=sub,SRop=mov;
SRout=1,R1in=1;

➋inc R1:
R1out=1,Tin=1,ALUop=inc,SRop=mov;
SRout=1,R1in=1;

「45」（9分）、

有AB两人通过信箱进行辩论，每个人都从自己的信箱中取得对方的问题。将答案和向对方提出的新问题组成一个邮件放入对方的邮箱中。假设A的信箱最多放M个邮件，B的信箱最多放N个邮件。初始时A的信箱中有x个邮件，B的信箱中有y个，〔M,N,x,y均为正整数且0<x<M,0<y<N〕。辩论者每取出一个邮件，邮件数减1。A和B两人的操作过程描述如下：

cobegin A { while (true) {        |cobegin B { while (true) {
    RetrieveAnEmail(Amailbox);    |    RetrieveAnEmail(Bmailbox);
    AnsweredAndAsking();          |    AnsweredAndAsking();
    PlaceAnEmail(Bmailbox);       |    PlaceAnEmail(Amailbox);
} } coend                         |} } coend

问答：

1️⃣当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。当信箱不满时，辩论者才能将新邮件放入信箱，否则等待。请添加必要的信号量和P(wait)V(signal)操作，以实现上述过程。要求写出完整过程，并说明信号量的含义和初值。

𝟙、可以看成两个读写缓冲区问题。两个互斥信号量mutexA,mutexB控制对信箱AB的互斥访问；两个同步信号量fullA,fullB用于表示信箱AB中有多少邮件，两个同步信号量emptyA,emptyB用于表示信箱AB中有多少空位。

semaphore mutexA = 1, mutexB = 1;
semaphore fullA = x, fullB = y;
semaphore emptyA = M - x, emptyB = N - y;
CoBegin A {                        |CoBegin B {
while (true) {                     |while (true) {
    P(fullA);                      |    P(fullB);   
    P(mutexA);                     |    P(mutexB);
    /*RetrieveAnEmail(Amailbox);*/ |    /*RetrieveAnEmail(Bmailbox);*/
    V(mutexA);                     |    V(mutexB);
    V(emptyA);                     |    V(emptyB)
    /*AnsweredAndAsking();*/       |    /*AnsweredAndAsking();*/
    P(emptyB);                     |    P(emptyA);
    P(mutexB);                     |    P(mutexA);
    /*PlaceAnEmail(Bmailbox);*/    |    /*PlaceAnEmail(Amailbox);*/
    V(mutexB);                     |    V(mutexA);
    V(fullB);                      |    V(fullA);
} } CoEnd                          |} } CoEnd

「46」（6分）、

某计算机系统按字节编址，采用二级页表的分页存储管理方式，虚拟地址格式为：
［页目录号10位｜页表索引10位｜页内偏移量12位］。

问答：

1️⃣页面和页框的大小各为多少字节？进程的虚拟地址空间大小为多少页？

𝟙、页面页框的大小都是exp(12)×1B=4KB。虚拟地址空间有exp(20)=1M个页。

2️⃣假定页目录项和页表项均占4个字节，则进程的页目录和页表共占多少页框？

𝟚、页目录项1K个，页表项1M个，共占(1K+1M)×4B÷4KB=1025个页框。

3️⃣若某指令周期内访问的虚拟地址为0x 0100 0000和0x 0111 2048，则进行地址转换时共访问多少个二级页表？

𝟛、取高10位看看，页目录号都是4，因此共访问1个二级页表，都是4号页目录对应的二级页表。

「47」（9分）、

某网络拓扑如图所示，其中路由器内网接口+DHCP服务器+WWW服务器+主机1均采用静态IP地址配置，相关地址信息见图中标注；主机2～主机N通过DHCP服务器动态获取IP地址等配置信息。

问答：

1️⃣DHCP服务器可为主机2～主机N动态分配IP地址的最大范围是什么？主机2使用DHCP协议获取IP地址的过程中，发送的封装DHCP“Discover”报文的IP分组的源IP地址和目的IP地址分别是什么？

𝟙、DHCP动态分配最大范围是111.123.15.5~111.123.15.254。DHCP“Discover”报文：源IP地址=0.0.0.0，目的IP地址=255.255.255.255。

2️⃣若主机2的ARP表为空，则该主机访问Internet时，发出的第一个以太网帧的目的MAC地址是什么？封装主机2发往Internet的IP分组的以太网帧的目的MAC地址是什么？

𝟚、主机2访问要先获取默认网关的MAC地址，首先发出ARP广播请求的以太网帧，目的MAC地址是ff-ff-ff-ff-ff-ff。封装主机2发往Internet的IP分组的以太网帧的目的MAC地址，就是默认网关的MAC地址00-a1-a1-a1-a1-a1。

3️⃣若主机1的子网掩码和默认网关分别配置为255.255.255.0和111.123.15.2，则该主机是否能访问WWW服务器？是否能访问Internet？

𝟛、从网络拓扑和子网掩码上看，主机1能访问到同一子网中的WWW服务器；但当访问Internet时，发出的IP分组会被错误转发给DHCP服务器，DHCP服务器可没有路由功能。