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

声明：

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

二、综合应用：

第41~47题，共70分。

「41」（10分）、

设有6个有序表A,B,C,D,E,F，分别含有10,35,40,50,60,200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。

问答：

1️⃣给出完整的合并过程？并求出最坏情况下比较的总次数？

1、合并两个长度为m,n的有序表，最坏情况下是一直比较到两个表尾元素，m+n-1次，即依赖于两表长度和，越长的表就越要靠后合并，不难想到哈夫曼树，如图。最坏情况下总比较次数是45+85+110+195+395-5=825次。

2️⃣根据你的合并过程，描述N{N为大于1的正整数}个不等长升序表的合并策略？

2、借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下的最佳合并效率，哈夫曼树也就是最佳归并树。

「42」（13分）、

假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，"loading"和"being"的存储映像如下图所示。

设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为[data|next]，请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置{如图中字符i所在结点的位置p}。

问答：

1️⃣给出算法的基本设计思想。

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

3️⃣说明你所设计算法的时间复杂度。

1、①分别求出str1和str2所指的两个链表的长度m和n；②定义两个指针p,q指向str1,str2，然后移动较长链表处的指针，使得p,q所指结点到表尾的距离相等；③指针p,q同步向后移动，data相同即找到所求共同后缀的起始位置。

2、

typedef struct LinkNode {
    char data;
    struct LinkNode *next;
} *LinkedList;

LinkNode* Find1stCommonSuffix(LinkedList str1, LinkedList str2)
{
    int m = strlen(str1), n = strlen(str2);
    LinkedList p = str1, q = str2;
    for (; m > n; m--) // 使p开头的链表与q开头的链表等长
        p = p->next;
    for (; m < n; n--) // 使p开头的链表与q开头的链表等长
        q = q->next;
    while (p != nullptr && p->data != q->data)
    { p = p->next; q = q->next; } // pq同步后移
    return q;
}

3、时间复杂度𝜪(max(m,n))。

「43」（10分）、

假定某计算机的CPU主频为80MHz，CPI为4，平均每条指令访存1.5次，Memory{主存}与Cache之间交换的块大小为16B，Cache的命中率为99%，存储器总线宽度为32位。

问答：

1️⃣该计算机的MIPS数是多少？平均每秒Cache缺失的次数是多少？在不考虑DMA传送的情况下，主存带宽至少达到多少才能满足CPU的访存要求？

1、每秒80×exp10(6)个时钟周期，平均执行一条指令占4个时钟周期，即平均每秒执行指令20×exp10(6)条，MIPS=20。执行指令平均每秒要访存20×exp10(6)×1.5=30×exp10(6)次，Cache缺失30×exp10(6)×1%=3×exp10(5)次。Cache缺失时才去Memory取块，主存带宽至少16B×3×exp10(5)÷1s=4.8MBps。

2️⃣假定在Cache缺失的情况下访问主存时，存在0.0005%的缺页率，则CPU平均每秒产生多少次缺页异常？若页面大小为4KB，每次缺页都需要访问磁盘，访问磁盘时DMA传送采用周期挪用方式，磁盘I/O接口的数据缓冲寄存器为32位，则磁盘I/O接口平均每秒发出的DMA请求次数至少是多少？

2、平均每秒产生缺页异常30×exp10(6)×0.0005%=1.5次。平均每秒要从磁盘调入1.5×4KB=6KB的数据，磁盘I/O接口每准备好32位数据就向CPU发送一个DMA请求来挪用总线占用权，每秒发送DMA请求6×exp(10)B÷32b=1536次。

3️⃣CPU和DMA控制器同时要求使用存储器总线时，哪个优先级更高？为什么？

3、DMA连接的是较高速外设，如果DMA请求得不到及时的响应，那么I/O接口中的数据可能会被覆盖掉。

4️⃣为了提高性能，主存采用四体低位交叉存储模式，工作时每1/4个存储周期启动一个体。若每个体的存储周期为50ns，则该主存能提供的最大带宽是多少？

4、如图，低位交叉可以流水线方式工作，最好情况下，1个存储周期能让4个存储体都传32位数据，主存最大带宽4×32b÷50ns=320MBps。

「44」（12分）、

某16位计算机中，带符号整数用补码表示，数据Cache和指令Cache分离。下表给出了指令系统中部分指令格式，其中Rs和Rd表示寄存器，Mem表示存储单元地址，(X)表示寄存器X或存储单元X的内容。

该计算机采用5段流水方式执行指令，各流水段分别是取指{IF}、译码／读寄存器{ID}、执行／计算有效地址{EX}、访问存储器{M}和结果写回寄存器{WB}，流水线采用“按序发射，按序完成。”方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。

问答：

1️⃣若int型变量x的值为-513，存放在寄存器R1中，则执行指令"SHR R1"后，R1的内容十六进制是多少？

1、该计算机中，int型和寄存器R1都是16位，-513的补码是0b 1111 1101 1111 1111，算术右移一位是0b 1111 1110 1111 1111=0xFEFF。用-513÷2往下取整的-257转十六进制也可。

2️⃣若某个时间段中，有连续的4条指令进入流水线，在其执行过程中没有发生任何阻塞，则执行这4条指令所需的时钟周期数为多少？

2、一个时钟周期一条指令进入流水线，除前5段外，后续每过1个时钟周期就能完成一条指令，执行连续4条指令需时钟周期数是5+(4-1)=8个。

3️⃣若高级语言程序中某赋值语句为x=a+b，x,a,b均为int型变量，它们的存储单元地址分别表示为[x],[a],[b]。该语句对应的指令序列及其在指令流水线中的执行过程如下所示，则这4条指令执行过程中，I3的ID段和I4的IF段被阻塞的原因各是什么？

I1   LOAD   R1, [a]
I2   LOAD   R2, [b]
I3   ADD    R1, R2 
I4   STORE  R2, [x]

3、I3的ID段被阻塞的原因：I3与I1和I2都存在数据相关，需等到I1和I2将结果写回寄存器后，I3才能读寄存器内容。I4的IF段被阻塞的原因：要求流水线“按序发射，按序完成。”，I4的IF段必须和I3的ID段对齐。

4️⃣若高级语言程序中某赋值语句为x=x*2+a，x,a均为unsigned int类型变量，它们的存储单元地址分别表示为[x],[a]，则执行这条语句至少需要多少个时钟周期？像上一小题一样给出这条语句对应的指令序列及其在流水线中的执行过程示意图。

4、5条指令，17个时钟周期，如下。

I1   LOAD   R1, [x]
I2   LOAD   R2, [a]
I3   SHL    R1     
I4   ADD    R1, R2 
I5   STORE  R2, [x]

「45」（8分）、

某请求分页系统的局部页面置换策略如下：系统从0时刻开始扫描，每隔5个时间单位扫描一轮驻留集{扫描时间忽略不计}，本轮没有被访问过的页框将被系统回收，并放到空闲页框链尾，其中内容在下一次分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，那么重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。

假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32→15→21→41。进程P依次访问的＜虚拟页号，访问时刻＞是<1,1>, <3,2>, <0,4>, <0,6>, <1,11>, <0,13>, <2,14>。

问答：

1️⃣访问<0,4>时，对应的页框号是什么？

1、分析时间段0~5，
@1：访问1号页面，占用32号页框，链表=15→21→41；
@2：访问3号页面，占用15号页框，链表=21→41；
@4：访问0号页面，占用21号页框，链表=41；👈本问回答21。
@5：扫描驻留集，回收不了一个页。

2️⃣访问<1,11>时，对应的页框号是什么？

2、分析时间段6~11，
@6：访问0号页面，已在内存，链表=41；
@10：扫描驻留集，回收32,15两个页框，链表=41→32→15；
@11：访问1号页面，曾经使用过并且还在链表中，占用32号页框，链表=41→15；
👈本问回答32。

3️⃣访问<2,14>时，对应的页框号是什么？

3、分析时间段12~14，
@13：访问0号页面，已在内存，链表=41→15；
@14：访问2号页面，占用41号页框，链表=15；👈本问回答41。

4️⃣该策略是否适合于时间局部性好的程序？

4、合适，从题目给的例子可以看出，0号页面首次调入内存就一直在驻留集中，1号页面被回收后，又从空闲页框链表中拿到了原来的页框。对于时间局部性好的程序，该策略的缺页中断次数很少。

「46」（8分）、

某文件系统空间的最大容量为4TB{1TB=exp(40)B}，以磁盘块为基本分配单位。磁盘块大小为1KB。文件控制块{FCB}包含一个512B的索引表区。

问答：

1️⃣假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号，索引表项中块号最少占多少字节？可支持的单个文件最大长度是多少字节？

1、磁盘被划分为4TB÷1KB=4G个块，索引表项中块号最少占log(4G)=32b=4B。索引表区最多可放512B÷4B=128个索引表项，支持单个文件最大128×1KB=128KB。

2️⃣假设索引表区采用如下结构：第0~7字节采用＜起始块号，块数＞格式表示文件创建时预分配的连续存储空间，其中起始块号占6B，块数占2B；剩余504字节采用直接索引结构，一个索引项占6B，那么可支持的单个文件最大长度是多少字节？为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值？

2、连续空间最大exp(2×8)个块，直接索引空间最大504÷6=84个块，支持单个文件最大(65536+84)×1KB=65620KB。由1️⃣知起始块号占4B最合理，块数也4B，连续空间能达到exp(4×8)个块，刚好4TB。

「47」（9分）、

主机H通过快速以太网连接互联网，IP地址为192.168.0.8，服务器S的IP地址为211.68.71.80。H与S使用TCP通信时，在H上捕获的其中5个IP分组如“题47表1”所示。
{表中为十六进制数，两个十六进制数即一字节。}，{表1表2中给的IP分组内容刚好，第一行是IP分组头的20B，第二行是TCP段固定首部的20B。}。

问答：

1️⃣表1中的IP分组中，哪几个是由H发送的？哪几个完成了TCP连接建立过程？哪几个在通过快速以太网传输时进行了填充？

1、
H的IP地址192.168.0.8=0x.c0.a8.00.08，由图1，作为源IP地址的用红色标出，作为目的IP地址的用蓝色标出，①③④号是H发送的。
TCP三次握手的TCP段头中依次有(SYN=1,ACK=0),(SYN=1,ACK=1),(SYN=0,ACK=1)，由图2，①②③号完成TCP连接建立，三个段携带的序号和确认号也能对上。
以太网规定数据载荷最小46B，也就是IP分组头总长度小于0x2E的③⑤号要被填充。

2️⃣根据表1中的IP分组，分析S已经收到的应用层数据字节数是多少？

2、看④号IP分组，H给S发的序号是0x846b41c6，看⑤号IP分组，S给H发的确认号是0x846b41d6，代表S已经收到0x10=16字节。

3️⃣若表1中的某个IP分组在S发出时的前40字节如表2所示，则该IP分组到达H时经过了多少个路由器？

3、IP分组每经过一个路由器，生存时间减1，表2给的S发出的生存时间为0x40，表1中H收到的不论③号⑤号的生存时间都是0x31，可得该IP分组经过了0x40-0x31=0x0F=15个路由器。