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

声明：

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

二、综合应用：

第41~47题，共70分。

「41」（13分）、

已知一个整数序列A={a[0],a[1],...,a[n-1]}，其中0≤a[i]≤n(0≤i≤n)。若存在a[p1]=a[p2]=···=a[pm]=𝓍且m>n/2(0≤p[k]≤n,1≤k≤m)，则称𝓍为A的主元素。例如(0,5,5,3,5,7,5,5)，则5为主元素；又如A=(0,5,5,3,5,1,5,7)，则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。

问答：

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

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

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

1、由题意，主元素就是出现次数超过序列长度一半的元素，有0个或1个，于是可以开辟一个数组统计各元素的出现次数，遍历一次序列A即可找到。

2、

int FindMajority(int[] A, int n)
{
    int major = 0; // 主元素
    int* freq = (int*)calloc(n, sizeof(int));
    // 分配一块内存辅助数组并内容清空
    for (int i = 0; i < n; i++)
    {
        freq[A[i]]++;
        if (freq[A[i]] > freq[major])
            major = A[i]; // 记录下出现次数最多的元素
    }
    free(freq); // 手动释放数组占的内存
    if (freq[major] > n / 2)
        return major;
    else
        return -1;
}

3、时间复杂度𝜪(n)，空间复杂度𝜪(n)。参考答案给的最优算法空间复杂度是𝜪(1)，一般想不到也不必要花太多心思去想。

「42」（10分）、

设包含4个数据元素的集合S={"do","for","repeat","while"}，各元素的查找概率依次为：p1=0.35,p2=0.15,p3=0.15,p4=0.35。将S保存在一个长度为4的顺序表中，采用折半查找法，查找成功时的平均查找长度为2.2〔=0.35×2+0.15×1+0.15×2+0.35×3〕。

问答：

1️⃣若采用顺序存储结构保存S，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？

1、按查找概率降序排列，使用顺序查找，查找成功时的平均查找长度是0.35×1+0.35×2+0.15×3+0.15×4=2.1，略优。

2️⃣若采用链式存储结构保存S，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？

2、按查找概率降序排列，链式存储只能使用顺序查找，查找成功时的平均查找长度也是2.1。题中没要求用单链表，还可使用二叉链表构造二叉排序树，使用多叉链表构造B-树B+树等。

「43」（9分）、

某32位计算机，CPU主频为800MHz，Cache命中时的CPI为4，Cache块大小为32字节；主存采用8体交叉存储方式，每个体的存储字长为32位，存储周期为40ns；存储器总线宽度为32位，总线时钟频率为200MHz，支持突发传送总线事务。每次读突发传送总线事务的过程包括：送首地址和命令+存储器准备数据+传送数据。每次突发传送32字节，传送地址或32位数据均需要一个总线时钟周期。

问答：

1️⃣CPU和总线的时钟周期各为多少？总线的带宽〔最大数据传输速率〕为多少？

𝟙、CPU的时钟周期=1÷800MHz=1.25ns，总线时钟周期=1÷200MHz=5ns，总线带宽=32b×200MHz=800MB/s=6.4Gbps。

2️⃣Cache缺失时，需要用几个读突发传送总线事务来完成一个主存块的读取？

𝟚、Cache块大小32B，总线一次突发传送也是32B，且包括了传地址，故Cache缺失时读一个主存块只用1个读突发即可。

3️⃣存储器总线完成一次读突发传送总线事务所需的时间是多少？

𝟛、首先要用1个总线时钟周期传送首地址；8体交叉存储器以流水线方式准备+传送数据；每5ns启动1个体，8个体各启动1次就有32B的数据了，如图，共需(5+40+8×5)ns=85ns。

4️⃣若程序BP执行过程中，共执行了100条指令，平均每条指令需进行1.2次访存，Cache缺失率为5%，不考虑替换等开销，则BP的CPU执行时间是多少？

𝟜、也就是说要访存120次，无论Cache是否命中都要先访问Cache，120×4×1.25ns=500ns，当Cache缺失时会带来额外开销120×0.05×85ns=510ns，〔第2️⃣3️⃣问的用处〕，共1010ns。

「44」（14分）、

某计算机采用16位定长指令字格式，其CPU中有一个标志寄存器，其中包含进位／借位标志CF+零标志ZF+符号标志NF。假定为该机设计了条件转移指令，其格式如下。其中，00000为操作码OP；C+Z+N分别为CF+ZF+NF的对应检测位，某检测位为1时表示需检测对应标志，需检测的标志位中只要有一个为1就转移，否则不转移，例如，若C=1,Z=0,N=1，则需检测CF和NF的值，当CF=1或NF=1时发生转移；OFFSET是相对偏移量，用补码表示。转移执行时，转移目标地址为(PC)+2+2×OFFSET；顺序执行时，下条指令地址为(PC)+2。

问答：

1️⃣该计算机存储器按字节编址还是按字编址？该条件转移指令向后最多可跳转多少条指令？

𝟙、由(PC)+2知，1条指令占据2个存储器地址，是按字节编址的。8位补码可表示的范围是-128~127，注意到加上OFFSET之前PC已经向前走了1条指令，该条件转移指令向后最多跳127条指令。

2️⃣某条件转移指令的地址为0x200C，指令内容为00000 011 11100011，若该指令执行时CF=0,ZF=0,NF=1，则该指令执行后PC的值是多少？若该指令执行时CF=1,ZF=0,NF=0，则该指令执行后PC的值又是多少？

𝟚、由指令内容需检测ZF和NF的值，情况①要跳转，OFFSET要符号位扩展，PC=0x200C+2+2×OxFFE3=0x1FD4。情况②不跳转，PC=0x200C+2=0x200E。

3️⃣实现“无符号数比较小于等于时转移”功能的指令中，C,Z,N应各是什么？

𝟛、无符号数运算不涉及符号标志，N=0，两数之间的大小比较通常是对两个数进行相减，为零需检测零标志，Z=1，为负需检测借位标志，C=1。

4️⃣以下是该指令对应的数据通路示意图，说明图中部件①②③的名称或功能？

𝟜、部件①指令寄存器，存放当前指令。部件②移位器，将OFFSET左移1位相当于乘2。部件③加法器，加法器可以有多个。

「45」（7分）、

某博物馆最多可容纳500人同时参观，有一个出入口，该出入口一次仅允许一个人通过。参观者的活动描述如下，

cobegin
    process visitor[i]:
    {
        /*……*/
        come_in(); // 进门
        /*……*/
        visit(); // 参观
        /*……*/
        go_out(); // 出门
        /*……*/
    }
coend

问答：

1️⃣请添加必要的信号量和PV操作，以实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。

𝟙、PV操作大题，确定信号量是关键。互斥信号量mutex控制出入口一次仅允许一个人通过。同步信号量full控制博物馆最多容纳500人。

semaphore mutex = 1;
semaphore full = 500;
cobegin
    process visitor[i]:
    {
        P(full);
        P(mutex);
        come_in();
        V(mutex);
        visit();
        P(mutex);
        go_out();
        V(mutex);
        V(full);
    }
coend

「46」（8分）、

某计算机主存按字节编址，逻辑地址和物理地址都是32位，页表项大小为4字节。

问答：

1️⃣若使用一级页表的分页存储管理方式，逻辑地址结构为［页号20位｜页内偏移量12位］，则页的大小是多少字节？页表最大占用多少字节？

𝟙、页的大小=exp(12)B=4KB。一级页表最多exp(20)个页表项，占用exp(20)×4B=4MB。

2️⃣若使用二级页表的分页存储管理方式，逻辑地址结构为［页目录号10位｜页表索引10位｜页内偏移量12位］，设逻辑地址为LA，请分别给出其对应的页目录号和页表索引的表达式？

𝟚、LA是无符号数，进行逻辑右移，页目录号=(LA>>22)&0x3FF，或=LA/exp(22)；页表索引=(LA>>12)&0x3FF，或=LA%exp(22)/exp(12)。

3️⃣采用1️⃣中的分页存储管理方式，一个代码段起始逻辑地址为0x0000 8000，其长度为8KB，被装载到从物理地址0x0090 0000开始的连续主存空间中。页表从主存0x0020 0000开始的物理地址处连续存放，如下图所示〔地址大小自下向上递增〕。请计算出该代码段对应的两个页表项的物理地址？这两个页表项中的页框号以及代码页面2的起始物理地址？

𝟛、该代码段刚好占2个页面，代码页面1的逻辑地址0x0000 8000表明其位于8号页面，即第8个页表项，1个页表项占据4个地址，物理地址1=0x0020 0000+8×4=0x0020 0020，相应的页框号1=0x00900，物理地址2=0x0020 0024，相应的页框号2=0x00901，物理地址3=0x0090 1000。

「47」（9分）、

假设Internet的两个自治系统构成的网络如下图所示，自治系统ASI由路由器R1连接两个子网构成；自治系统AS2由路由器R2+R3互联并连接3个子网构成。各子网地址，R2的接口名，R1与R3的部分接口IP地址如下图所示。

问答：

1️⃣假设路由表结构为［目的网络｜下一跳｜接口］。请利用路由聚合技术，给出R2的路由表，要求包括到达题给的网络拓扑图中所有子网的路由，且路由表中的路由项尽可能少？

𝟙、考路由聚合技术，寻找AS1和AS2中两子网的最长公共前缀即可。

2️⃣若R2收到一个目的IP地址为194.17.20.200的IP分组，R2会通过哪个接口转发该IP分组？

𝟚、目的IP地址194.17.20.200将与路由表中目的网络为194.17.20.0/25和194.17.20.128/23的路由表项匹配，根据最长前缀匹配原则，最终选择E0接口转发。

3️⃣R1与R2之间利用哪个路由协议交换路由信息？该路由协议的报文被封装到哪个协议的分组中进行传输？

𝟛、 R1和R2属于不同的自治系统，可以使用边界网关协议BGP交换路由信息；BGP是应用层协议，报文被封装到TCP协议段中进行传输。