2018年12月考研的408试题，本篇为大题部分，小题见上一篇。
声明：
- 0x和0b分别表示十六进制数和二进制数，其余为十进制数。
- 0y和0c分别表示十六进制形式补码和二进制形式补码。
- exp()和log()分别是以2为底的指数和对数，exp10()以10为底。
- 乘除号用最朴素的×÷，分数用/，⌊⌋⌈⌉分别是向上向下取整。
- 参与计算的英文字母变量用的是手写体。
- 对原题一些容易误会的文字做了修改。
- 图片使用亿图图示等绘制。
二、综合应用：
第41～47题，共70分。
「41」（13分）、
设线性表𝑳=(𝒂[1],𝒂[2],𝒂[3],...,𝒂[n-2],𝒂[n-1],𝒂[n])采用带头结点的单链表保存，链表中的结点定义如下👇，请设计一个空间复杂度为𝜪(1)且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表𝑳'=(𝒂[1],𝒂[\n],𝒂[2],𝒂[n-1],𝒂[3],𝒂[n-2],...)。
问答：
1️⃣给出算法的基本设计思想？说明你所设计的算法的时间复杂度？
𝟙、观察发现新单链表由旧单链表取第一个结点+倒数第一个结点，第二个结点+倒数第二个结点...组成，①快慢指针寻找单链表中点；②头插法将后半段原地倒转；③头插法将后半段挨个插入前半段。时间复杂度𝜪(n)。
2️⃣根据设计思想，采用C/C++语言描述算法，关键之处给出注释？
𝟚、如下👇。
typedef struct node
{
int data;
struct node* next;
} node;
void ChangeLinkedList(node* head)
{
node *fast, *slow, *temp;
fast = slow = head;
while (fast->next)
{
fast = fast->next;
slow = slow->next; // slow走一步
if (fast->next)
fast = fast->next; // fast走两步
}
fast = slow->next; // fast指向后半段第一个结点
slow->next = nullptr; // slow指向前半段最后一个结点
while (fast) // 头插法后半段原地倒转
{
temp = fast->next;
fast->next = slow->next;
slow->next = fast;
fast = temp;
}
fast = slow->next; // fast指向后半段第一个结点a[1]
slow->next = nullptr; // 前后两段断开
slow = head->next; // slow指向前半段第一个结点a[n]
while (fast) // 挨个插入
{
temp = fast->next;
fast->next = slow->next;
slow->next = fast;
slow = fast->next; // slow移向前半段下一个待处理结点
fast = temp; // fast移向后半段下一个待处理结点
}
}「42」（10分）、
请设计一个队列，要求满足：❶初始时队列为空；❷入队时，允许增加队列占用空间；❸出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；❹入队操作和出队操作的时间复杂度始终保持为𝜪(1)。
问答：
1️⃣该队列是应选择链式存储结构，还是应选择顺序存储结构？
𝟙、链式存储。要求❷链式存储方便增加结点；要求❸元素出队后结点并不真正释放而是保留为空闲结点，新元素入队时利用空闲结点，但是这些空闲结点位于队头指针前面，可以设计为首尾相接的循环队列，那些空闲结点就位于队尾指针后面啦；入队出队的时间复杂度能保持为𝜪(1)，要求❹可以满足。
2️⃣画出队列的初始状态，并给出判断队空和队满的条件？
𝟚、如下👇，配置一个哑结点。队空front == rear，队满rear->next == front。
3️⃣画出第一个元素入队后的队列状态？
𝟛、如下👇。
4️⃣给出入队操作和出队操作的基本过程？
𝟜、如下👇。
入队操作QueAppend(data):
if (rear->next == front) // 队满
nodeptr = (node*)malloc(); // 增加一个结点
rear->next = nodeptr; // 插入到rear后面
nodeptr->next = front; // 且在front前面
rear->data = data; // 入队元素保存到rear所指结点
rear = rear->next; // rear后移
出队操作QueDelete():
if (front == rear) // 队空
throw EMPTY_ERROR; // 抛出错误提示
nodeptr = front; // 保留队头结点
front = front->next; // front后移
return nodeptr->data; // 返回队头元素「43」（8分）、
有n位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在圆桌中心有m只碗，每两位哲学家之间有一根筷子。每位哲学家必须取到一只碗和两侧的筷子后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。n是大于3的正整数，m是大于1的正整数。
问答：
1️⃣为使尽可能多的哲学家同时就餐，且防止出现死锁现象，请使用信号量的P(wait)V(signal)操作描述上述过程中的互斥与同步，并说明所用信号量及初值的含义？
回顾传统哲学家进餐问题，n个哲学家n根筷子，当n个哲学家各持有1根筷子时发生死锁。有一种避免死锁的方法：限制至多n-1个哲学家同时抢筷子，那么至少有1个哲学家可以获得2根筷子顺利就餐，从而避免死锁。
𝟙、本题是n个哲学家n根筷子m只碗，可以限制抢碗来避免死锁，让哲学家要先抢到碗，再抢到筷子才能就餐。当m<n时，限制至多m个哲学家同时抢碗，这样保证至少有1个哲学家可以获得1只碗和2根筷子；当m≥n时，限制至多n-1个哲学家同时抢碗，也能保证至少有1个哲学家可以获得1只碗和2根筷子。于是碗作为信号量，初值为min(m,n-1)。
semaphore chopsticks[n] = {1};
semaphore bowl = m < n ? m : n - 1;
CoBegin philosopher[i] {
while (true) {
/*thinking*/
j = (i + 1) % n;
P(bowl);
P(chopsticks[i]);
P(chopsticks[j]);
/*dining*/
V(chopsticks[j]);
V(chopsticks[i]);
V(bowl);
} } CoEnd「44」（7分）、
某计算机系统中的磁盘有300个柱面，每个柱面有10个磁道，每个磁道有200个扇区，扇区大小为512B，文件系统的每个簇包含2个扇区。
问答：
1️⃣磁盘的容量是多少？
𝟙、300×10×200×512B=3×exp(5)KB <300MB。
2️⃣假设磁头在85号柱面上，此时有4个磁盘访问请求，簇号分别为100260,60005,101660,110560。若采用最短寻道时间优先SSTF调度算法，则系统访问簇的先后次序是什么？
𝟚、每个柱面上有10×200÷2=1000个簇，85号柱面上的簇号：85000～85999，按照SSTF调度算法规则，先后访问的是60005,100260,101660,110560。
3️⃣簇号100530在磁盘上的物理地址是什么？将簇号转换成磁盘物理地址的过程是由I/O系统的什么程序完成的？
𝟛、物理地址=(柱面号,磁道号,扇区号)，簇号=柱面号×1000+磁道号×100+⌊扇区号÷2⌋。簇号100530所在：柱面号⌊100530÷1000⌋=100，磁道号⌊100530%1000÷100⌋=5，扇区号100530%10000×2=60。簇号转换成磁盘物理地址的过程由磁盘驱动程序完成。
「45」（分）、
已知，计算𝒇(𝓃)的C语言函数f1的源程序及其在32位机器M上的部分机器级代码如下👇。其中，机器级代码行包括行号·虚拟地址·机器代码·汇编语句，位于C语句下方的白色部分，机器M按字节编址，int型变量占32位。
int f1(int n)
{
1 00401000 55 push ebp
if (n > 1)
11 00401018 83 7D 08 01 cmp dword ptr [ebp+8], 1
12 00401018 7E 17 jle f1+0x35 &(00401035)
return n * f1(n-1);
13 0040101E 8B 45 08 mov eax, dword ptr [ebp+8]
14 00401021 83 E8 01 sub eax, 1
15 00401024 50 push eax
16 00401025 E8 D6 FF FF FF call f1 &(0x00401000)
19 00401030 0F AF C1 imul eax, ecx
20 00401033 EB 05 jmp f1+0x3A &(0x0040103A)
else return 1;
21 00401035 B8 01 00 00 00 mov eax, 1
}
26 00401040 3B EC cmp ebp, esp
30 0040104A C3 ret
问答：
1️⃣计算𝒇(10)需要调用函数f1多少次？执行哪条指令会递归调用f1？
𝟙、𝒇(10)调用函数f1共10次。第16行的call指令递归调用。
2️⃣哪条指令是条件转移指令？哪几条指令一定会使程序跳转执行？
𝟚、第12行的jle指令是条件转移指令，含义：根据上一行cmp指令的比较结果，若是小于等于，则跳转到地址0x00401035。一定会使程序跳转的有：第16行的call指令，第20行的jmp指令，第30行的ret指令。
3️⃣根据第16行的call指令，第17行指令的虚拟地址应是多少？已知第16行的call指令采用相对寻址方式，该指令中的偏移量应是多少？已知第16行的call指令的后4字节为偏移量，M是采用大端方式还是小端方式？
𝟛、第16行的call指令占5个地址，第17行的地址为0x00401025+5=0x0040102A。第16行的call指令，PC当前值0x0040102A，目标值0x00401000，偏移量0x00401000-0x0040102A=0xFFFFFFD6，第16行的call指令的后4字节为D6FFFFFF，是小端方式，适合机器阅读。
4️⃣𝒇(13)=6227020800，但f1(13)的返回值为1932053504，为什么两者不相等？要使f1(13)能返回正确的结果，应如何修改f1的源程序？
𝟜、int型变量可表示范围-2147483648～2147483647，6227020800显然溢出了，高位被截断。想要正确的结果，将f1的返回值类型改为long long或float。
5️⃣第19行的imul指令叫带符号整数乘，功能是R[𝚎𝚊𝚡]←R[𝚎𝚊𝚡]×R[𝚎𝚌𝚡]，当乘法器输出的高·低32位积之间满足什么条件时，溢出标志OF=1？要使CPU在发生溢出时转异常处理，编译器应在imul指令后应加一条什么指令？
𝟝、高33位为非全0且非全1时溢出。加一条“溢出自陷指令”。
「46」（7分）、
对于题45，机器M的主存地址为32位，釆用分页存储管理方式，页大小为4KB。指令Cache有64块，采用4路组相联映射方式，主存块大小为64B。
问答：
1️⃣第1行的指令push和第30行的指令ret是否在同一页面中？
𝟙、页内偏移占log(4K)=12位，虚拟地址结构：［页面号20位｜页内偏移12位］，第1行和第30行都在0x00401号页面。
2️⃣32位主存地址中，哪几位表示块内偏移？哪几位表示Cache行号？哪几位表示主存标记？
𝟚、块内偏移占log(64)=6位，Cache有16行4列，Cache行号log(16)=4，实际地址结构：［主存标记22位｜Cache行号4位｜块内偏移6位］。
3️⃣读取第16行的指令call时，只可能在指令Cache的哪一行里被命中？
𝟛、0x00401025只能被放到Cache的0b0000=0号行里。
「47」（9分）、
某网络拓扑如下图👇，其中R为路由器，主机H1～H4的IP地址以及R的各接口IP地址配置如图中所示。现有若干无VLAN功能的以太网交换机和路由器两类网络互连设备可供选择。
问答：
1️⃣设备1,2,3分别应选择什么类型的网络设备？
𝟙、H1,H2在同一个广播域LAN1，H3,H4在同一个广播域LAN2，LAN1,LAN2不是同一个广播域，设备1,2,3分别是路由器，交换机，交换机。
2️⃣设备1,2,3中，哪几个设备的接口需要配置IP地址？为对应的接口配置正确的IP地址？
𝟚、应为路由器即设备1的接口配置IP地址。只能配置为：{IF1:192.168.1.254/30, IF2:192.168.1.1, IF3:192.168.1.65}。
3️⃣为确保H1～H4能够访问Internet，R需要提供什么服务？
𝟛、H1～H4配的都是私有IP地址，想访问Internet得靠公有IP地址，R需提供NAT服务。
4️⃣若主机H3发送一个目的地址为192.168.1.127的IP数据报，网络中哪几个主机会接收该数据报？
𝟜、发的是LAN2的广播报，路由器隔离了广播域，只有H4会接收该数据报。
