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

声明：

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

二、综合应用：

第41～47题，共70分。

「41」（9分）、

对TCP的综合考察，看视频更好理解。

假设H3访问Web服务器S时，S为新建的TCP连接分配了20KB的接收缓存，最大段长MSS=1KB，平均往返时间RTT=200ms。H3建立连接时的初始序号为100，且持续以MSS大小的段向S发送数据，拥塞窗口初始阈值为32KB，S对收到的每个段进行确认，并通告新的接收窗口。假定TCP连接建立完成后，S端的TCP接收缓存仅有数据存入而无数据取出。

问答：

1️⃣在TCP连接建立过程中，H3收到的S发来的第二次握手TCP段的SYN和ACK标志位的值分别是多少？确认序号是多少？

𝟙、回顾TCP三次握手，直接给出答案，1，1，101。

2️⃣H3收到的第8个确认段所通告的接收窗口是多少？此时H3的拥塞窗口变为多少？H3的发送窗口变为多少？

𝟚、S每发一个确认就通告接收窗口-1，H3每收一个确认将拥塞窗口+1，H3的发送窗口=min(接收窗口,拥塞窗口)，12KB，9KB，9KB。

第𝟚小问我第一次做就错在，我不知道慢开始算法的微观过程，反而受宏观过程影响，拥塞窗口的变化是：1➧2➧4➧8➧16，误以为8之后拥塞窗口变为16了。另外注意题目给的条件：S对收到的每个段进行确认，S端只存不取。

3️⃣当H3的发送窗口=0时，下一个待发送的数据段序号是多少？H3从发送第1个数据段到发送窗口=0时刻为止，忽略段的传输时延，平均数据传输速率是多少？

𝟛、当H3的发送窗口=0时，已经发了20KB的数据，已知TCP三次握手中第1个数据段序号为101，那么第21个数据段序号是101+1024×20=20581。拥塞窗口变为21，结合慢开始算法可知经过了5个RTT，平均数据传输速率是20KB÷(5×200ms)=20KB/s=163.84Kbps。

4️⃣若H3与S之间通信已经结束，在t时刻H3请求断开该连接，则从t时刻起，S释放该连接的最短时间是多少？

𝟜、回顾TCP四次挥手，直接给出答案，最短1.5个RTT，300ms。

「42」（8分）、

若一棵非空k叉树T中每个非叶结点都有k个孩子，k是大于2的正整数，则称T为正则k叉树。给定一棵正则k叉树T。

问答：

1️⃣若T有𝓂个非叶结点，则T有多少个叶结点？

𝟙、设有𝓃个叶结点，有k𝓂+1=𝓂+𝓃 ⇒ 𝓃=(k-1)𝓂+1。

2️⃣若T的高度为h，根结点高度算作1，则T的结点数最多是多少个？最少又是多少个？

𝟚、最多时是h层挂满了结点，由等比数列公式，(k^h-1)/(k-1)个。最少时每层至多1个度为k的结点，1+(h-1)k个。

「43」（15分）、

已知由n个正整数构成的集合A={a[k]|k∈0～(n-1)}，将其划分为两个不相交的子集A1和A2，元素个数分别是n1和n2，A1和A2的元素之和分别是S1和S2。设计一个尽可能高效的划分算法，满足：|n1-n2|最小，|S1-S2|最大。

问答：

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

𝟙、核心思想就是从中位数划开，小的半边给A1，大的半边给A2，排序是最容易想到的办法。更优解是仿照快速排序的思想，基于枢轴划分。

根据划分后枢轴所处下标mid：①mid==⌊n/2⌋，划分完成；②mid<⌊n/2⌋，mid及之前的所有元素均属于A1，继续对mid之后的元素进行划分；③mid>⌊n/2⌋，mid及之后的所有元素均属于A2，继续对mid之后的元素进行划分；

不需要对元素全部排好序，时间复杂度𝜪(n)，空间复杂度𝜪(1)。

2️⃣根据设计思想，采用C/C++描述算法，关键之处给出注释？

𝟚、。

int SetPartition(int A[], int n)
{
    // std::sort(A, A+n);  // 最直接的排序法
    int low = already_low = 0；
    int high = already_high = n - 1;
    int mid = n / 2;
    while (true)
    {
        int pivot = A[low++];   // 选取A[low]作为枢轴
        while (low < high)
        {
            while (low < high && A[high] >= pivot)
                high--;
            while (low < high && A[low] <= pivot)
                low++;
            std:swap(A[low], A[high]); // 交换
            low++; high--;
        }
        A[already_low] = A[high];
    A[high]=pivot;          // 确定枢轴的最终位置
        if (low == mid)         // 情况①
            break;
        else if (low < mid)     // 情况②
            already_low = ++low, high = already_high;
        else                    // 情况③
            already_high = --high, low = already_low;
    }
    std::copy(A, A + mid, A1);
    std::copy(A + mid, A + n, A2);
    int S1 = S2 = 0;
    for (int i = 0; i < mid; i++)
        S1 += A[i];
    for (int i = mid; i < n; i++)
        S2 += A[i];
    return S2 - S1;
}

「44」（9分）、

某CPU主频为50MHz，CPI为4。设备D采用异步串行通信方式向主机传送7位ASCII字符，通信规程中有1位奇校验位和1位停止位，从D接收启动命令到字符送往I/O端口需要0.5ms。

问答：

1️⃣每传送1个字符，在异步串行通信线上需传输多少位？在设备D持续工作过程中，每秒最多可向I/O端口送入多少字符？

𝟙、1位起始位，1位停止位，1位奇校验位，7位ASCII字符，共10位。D每秒最多可向I/O端口送入1s÷0.5ms=2000个字符。

2️⃣D采用中断方式I/O，如下图所示，I/O端口每收到1个字符申请1次中断，中断响应需10个时钟周期，中断服务程序共有20条指令，其中第15条指令后启动D工作。若CPU需从D读取1000个字符，则完成这一任务大约需多少个时钟周期？完成这一任务占了CPU大约多少个时钟周期？在中断响应阶段CPU做了哪些操作？

𝟚、中断服务程序开始至启动D工作需15×4=60个时钟周期，从D接收启动命令到字符送往I/O端口需0.5ms×50MHz=25000个时钟周期，1个字符就要花10+60+25000=25070个时钟周期，1000个字符就要25070000个时钟周期。CPU不管D的工作，只要处理中断，花在这1000个字符上1000×(10+20×4)=90000个时钟周期。中断响应阶段所做之事就是中断隐指令：①关中断；②保护断点；③形成中断向量。

「45」（14分）、

某计算机采用页式虚拟存储管理方式，按字节编址，虚拟地址为32位，物理地址为24位，页大小为8KB，TLB采用全相联映射，Cache数据区大小为64KB，按二路组相联方式组织，主存块大小为64B。存储访问过程如下图所示。

问答：

1️⃣图中字段A～G的位数各是多少？TLB标记字段B中存放的是什么信息？

𝟙、页内偏移log(8K)=13位，页面号32-13=19位，页框号24-13=11位。Cache有1K个块，512行×2列。块内偏移log(64)=6位，Cache行号log(512)=9位，主存标记24-9-6=9位。A：19位，B：19位，C：11位，D：13位，E：9位，F：9位，G：6位。B中存放的是虚拟页面号。

2️⃣将块号为4099的主存块装入到Cache中时，所映射的Cache行号是多少？对应的H字段内容是什么？

𝟚、4099=0b 000001000 000000011，Cache行号是0b000000011=3，H字段即主存标记是0b000001000=8。

3️⃣Cache缺失处理的时间开销大还是缺页处理的时间开销大？为什么？

𝟛、缺页处理的时间开销大。Cache缺失是从主存复制块到Cache；页表缺失是从辅存复制页到主存中，并且会产生中断。

4️⃣为什么Cache可以采用直写策略，而修改页面内容总是采用回写策略？

𝟜、在Cache-Memory层，读写速度相对较快，可以采用直写策略。而主存-辅存层，辅存读写速度慢，总是采用回写策略，修改页面时不立即写辅存，当页面将被置换时才写到辅存。

「46」（6分）、

某进程调度程序采用基于优先数priority的调度策略，即选择优先数最小的进程运行，进程创建时由用户指定一个nice作为静态优先数。为了动态调整优先数，引入运行时间cpuTime和等待waitTime，初值均为0。进程处于执行态时，cpuTime定时加1，且waitTime置0；进程处于就绪态时，cpuTime置0，且waitTime定时加1。

问答：

1️⃣若调度程序只将nice值作为进程的优先数，即priority=nice，则可能会出现饥饿现象，为什么？

𝟙、当就绪队列中源源不断地出现低优先数的进程时，高优先数的进程容易饥饿。

2️⃣使用nice,cpuTime,waitTime设计一种动态优先计算方法，以避免出现饥饿现象，并说明waitTime的作用？

𝟚、与cpuTime正相关，与waitTime负相关的公式都可，如priority=nice+𝓅×cpuTime-𝓆×waitTime,𝓅>0,𝓆>0。waitTime用于降低长时间等待的进程的优先数，提升其抢占CPU的能力，避免被饿死。

「47」（9分）、

某磁盘文件系统使用链接分配方式组织文件，簇大小为4KB。目录文件的每个目录项包括文件名和文件的第一个簇号，其它簇号存放在文件分配表FAT中。整个磁盘只有一张FAT。

问答：

1️⃣假设目录树如下图左边所示，各文件占用的簇号及顺序如下图右边所示，请给出所有目录文件的内容？

𝟙、。

2️⃣若FAT的每个表项仅存放簇号，占2字节，则FAT的最大长度为多少字节？该文件系统支持的文件长度最大是多少？

𝟚、2字节就是16比特，可表示exp(16)个数，单个FAT最大可塞exp(16)个簇号，也就是exp(16)×2B=128KB。单个文件最大exp(16)×4KB=256MB。

3️⃣系统通过目录文件和FAT实现对文件的按名存取，file1的106,108簇号分别存放在FAT的哪个表项中？

𝟛、类似静态链表，106簇号放在FAT的100号表项，108簇号放在FAT的106号表项。

4️⃣假设仅FAT和目录文件dir已读入内存，若需将文件路径为dir/dir1/file1的第5000个字节读入内存，则要访问哪几个簇？

𝟜、要访问dir1所在的48号簇，file1的106号簇。先在dir里找到dir1第一个簇在48号簇，访问磁盘48号簇将dir1读入内存，在dir1里找到file1第一个簇在100号簇，第5000个字节在第⌈5000B÷4KB⌉=2簇里，从FAT中拿出file1的第1第2簇的表项即可，不用访问file1的第1簇所在的100号簇。