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

声明：

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

二、综合应用：

第41～47题，共70分。

「41」（13分）、

给定一个含n个整数的数组A[]，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正整数是1，数组{1,2,3}中未出现的最小正整数是4。

问答：

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

𝟙、空间换时间，用一个数组B[n]记录A[]中是否出现了1～n中的正整数，初始全为false，B[0]对应正整数1，若A[]中有1，则B[0]=true，依此类推，对A[]中小于1和大于n的数可以不理会。
时间复杂度𝜪(n)，空间复杂度𝜪(n)。

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

𝟚、如下👇。

int FindMissedMinPositive(int A[], int n)
{
    bool B[n] = {false};        // 用于做标记的数组
    for (int a: A)              // 基于范围的for循环
        if (a >= 1 && a <= n)   // 标记1～n中出现过和整数
            B[a-1] = true;
    for (int i = 0; i < n; i++) // 遍历标记数组找到目标值
        if (!B[i])
            return i + 1;       // 1～n中的某数
    return n + 1;               // 1～n都已出现返回n+1
}

「42」（12分）、

如题42图👇，拟建设一个光通信骨干网络连通BJ,CS,XA,QD,JN,NJ,TL,WH等8个城市，无向边上的权值表示两个城市间备选光缆的铺设费用。

问答：

1️⃣仅从铺设费用角度出发，给出所有可能的最经济的光缆铺设方案，并计算相应方案的总费用？

𝟙、求无向带权图的最小生成树，可得到两种方案如下👇，总费用16。

2️⃣题42图可采用图的哪一种存储结构？给出求解问题1️⃣所使用的算法名称？

𝟚、存储图可以采用邻接矩阵。构造最小生成树采用Prim算法或Kruskal算法。

3️⃣假设每个城市采用一个路由器按1️⃣中得到的最经济方案组网，主机H1直接连接在TL的路由器上，主机H2直接连接在BJ的路由器上。若H1向H2发送一个TTL=5的IP分组，则H2是否可以收到该IP分组？

𝟛、 TTL=5，IP分组最多过5个路由器，方案𝔞不行，路由距离为6；方案𝔟可以，路由距离为1。

「43」（8分）、

假定计算机的主频为500MHz，CPI为4。现有设备A和B，其数据传输率分别为2MBps和40MBps，对应I/O接口中各有一个32位数据缓冲寄存器。

问答：

1️⃣若设备A采用定时查询I/O方式，每次输入／输出都至少执行10条指令。设备A最多间隔多长时间查询一次才能不丢失数据？CPU用于设备A输入／输出的时间占CPU总时间的百分比至少是多少？

𝟙、设备A准备32b数据需32b÷2MBps=2us，故最多隔2us必须查询一次，否则I/O接口中的数据就被下一次来的覆盖了。查询一次占用CPU的开销10×4÷500MHz=0.08us，占比0.08/2=4%。

2️⃣在中断I/O方式下，若每次中断响应和中断处理的总时钟周期数至少为400，则设备B能否采用中断I/O方式？

𝟚、设备B准备32b数据需32b÷40MBps=0.1us，即I/O接口中的数据隔0.1us刷新一次。中断一次占用CPU的开销400÷500MHz=0.8us，来不及，故B不能采用中断I/O方式。

3️⃣若设备B采用DMA方式，每次DMA传送的数据块大小1000B，CPU用于DMA预处理和后处理的总时钟周期数为500，则CPU用于设备B输入／输出的时间占CPU总时间的百分比最多是多少？

𝟛、设备B用DMA方式准备1000B数据需1000B÷40MBps=25us，输入／输出即DMA处理占用CPU的开销500÷500MHz=1us，占比1/25=4%。

「44」（15分）、

某计算机采用页式虚拟存储管理方式，按字节编址。CPU进行存储访问的过程如题44图👇。

问答：

1️⃣主存物理地址＼实地址占多少位？

𝟙、看图，TLB下面的：实页号16位+页内地址12位=28位；或Cache下面的20位+3位+5位=28位。

2️⃣TLB采用什么映射方式？TLB用SRAM还是DRAM实现？

𝟚、TLB采用全相联映射，页表项可以放在TLB任一空行。TLB用SRAM，读写速度快。

3️⃣Cache采用什么映射方式？若Cache采用LRU替换算法和回写策略，则Cache每行中除数据区，主存标记，有效位外，还应有哪些附加位？Cache总容量是多少？Cache中有效位的作用是什么？

𝟛、Cache采用2路组相联映射，8行2列。还要有1位替换算法控制位，1位修改位表示是否需要回写主存。数据区exp(5)×1B=32B，主存标记20位，有效位1位，Cache总容量是16×(32B+20b+1b+1b+1b)=4464b。有效位为0表示主存标记字段无效，为1表示此项有效。

4️⃣若CPU给出的虚拟地址为0x0008C040，则对应的物理地址是多少？是否在Cache中命中？若CPU给出的虚拟地址为0x0007C260，则该地址所在主存块映射到的Cache行号是多少？

𝟜、查TLB，0x0008C040⮕0x0040040，且有效位为1，查Cache，0x00400有，但有效位为0，未命中。0x0007C260只看低8位，0x60=0b01100000，被映射到的Cache行号是3。

「45」（8分）、

还是题44图👆给出的虚拟储管理方式。

问答：

1️⃣某虚拟地址对应的页目录号为6，在相应的页表中对应的页号为6，页内偏移量为8，该虚拟地址的十六进制表示是什么？

𝟙、根据图中给出的虚拟地址结构，本题虚拟地址是0b 0000000110 0000000110 000000001000 = 0x01806008。

2️⃣寄存器PDBR用于保存当前进程的页目录起始地址，该地址是物理地址还是虚拟地址？进程切换时，PDBR的内容是否会变化？同一进程的线程切换时，PDBR的内容是否会变化？

𝟚、PDBR"Page Directory Base Register"，保存页目录在内存中的起始物理地址，每个进程都有自己的页目录，进程切换时PDBR变化，同一进程PDBR不变。

3️⃣为了支持改进型CLOCK置换算法，需要在页表项中设置哪些字段？

𝟛、访问位和修改位。

「46」（7分）、

某文件系统采用索引节点存放文件的属性和地址信息，簇大小为4KB。每个文件索引节点占64B，有11个地址项，其中直接地址项8个，一级·二级·三级间接地址项各1个，每个地址项长度为4B。1K=exp(10)，1M=exp(20)。

问答：

1️⃣该文件系统能支持的最大文件长度是多少？

𝟙、每簇可塞4KB÷4B=1024个地址项，最大文件长度(8+1×1024+1×1024×1024+1×1024×1024×1024)×4KB=32KB+4MB+4GB+4TB。

2️⃣文件系统用1M个簇存放文件索引节点，用512M个簇存放文件数据。若某图像文件的大小为5600B，则该文件系统最多能存放多少个这样的图像文件？

𝟚、文件索引节点数1M×4KB÷64B=64M个，5600B要占2个簇，文件数据区能放512M÷2=256M个，取小者64M个。

3️⃣若文件F1的大小为6KB，文件F2的大小为40KB，则该文件系统获取F1和F2最后一个簇的簇号需要的时间是否相同？

𝟛、F1的最后一个簇由直接地址指针指出，F2的最后一个簇由一级间接地址指针对应的一级索引表指出，需要的时间不相同。

「47」（7分）、

某公司网络如题47图👇。IP地址空间192.168.1.0/24被均分给销售部和技术部两个子网，并已分别为部分主机和路由器接口分配了IP地址，销售部子网的MTU=1500B，技术部子网的MTU=800B。

问答：

1️⃣销售部子网的广播地址是什么？技术部子网的网络地址是什么？若每个主机仅分配一个IP地址，则技术部子网还可以连接多少台主机？

𝟙、192.168.1.127，192.168.1.128。技术部子网还剩209～253可分配，253-209+1=45个。

2️⃣假设主机192.168.1.1向主机192.168.1.208发送一个总长度为1500B的IP分组，IP分组的头部长度为20B，路由器在通过接口F1转发该IP分组时进行了分片。若分片时尽可能分为最大片，则一个最大IP分片封装数据的字节数是多少？至少需要分为几个分片？每个分片的片偏移量是多少？

𝟚、IPv4数据报首部格式中指出，片偏移量必须是8B的整数倍。一个最大IP分片封装数据⌊(800-20)÷8⌋×8=776B，至少分⌈(1500-20)÷776⌉=2片，片偏移量分别是0，776÷8=97。