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

声明：

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

二、综合应用：

第41~47题，共70分。

「41」（10分）、

将关键字序列(7,8,30,11,18,9,14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一位数组，散列函数为：𝑯𝒂𝒔𝒉(𝓀ℯ𝓎) = 𝓀ℯ𝓎 × 3 % 7，处理冲突采用线性探测再散列法，要求装填因子为0.7。

问答：

1️⃣请画出所构造的散列表？

1、共7个关键字，散列表的长度应是7÷0.7=10。

关键字的散列函数值为：

采用线性探测再散列法，当有冲突时，index+1寻找下一个空位，

2️⃣分别计算等概率情况下查找成功和查找不成功的平均查找长度？

2、查找成功和查找失败的平均查找长度计算方法不一样！

查找成功的，根据每个关键字的查找次数来计算，

ASL_success=(1+1+1+1+3+3+2)÷7=12/7。

查找失败的，根据最终落空时的比较次数来计算，散列函数的返回结果只能在0～6，

ASL_fail=(3+2+1+2+1+5+4)÷7=18/7。

「42」（13分）、

将n〔n为大于1的正整数〕个整数存放到一维数组R中，试设计一个在时间空间上都尽可能高效的算法。将R中保存的序列循环左移p〔p为0～n间的整数〕个位置，即(𝓧₀,𝓧₁,...,𝓧_n-1)变换为(𝓧_p,𝓧_p+1,...,𝓧_n-1,𝓧₀,...,𝓧_p-1)。要求：

问：

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

2️⃣根据设计思想和实现步骤，采用C/C++编程实现，关键之处给出注释。

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

答：

1、借助辅助数组，创建一个大小为p的数组S，将R中前p个整数暂存于S中，然后将R中后n-p个整数循环左移，最后将S中的p个整数放回R中的后续单元。

2、传递数组可以用int R[]或int* R，都是指针调用，

void LeftShiftpinR(int R[], int n, int p)
{
    int S[p];
    for (int i = 0; i < p; i++)
        S[i] = R[i];
    for (int i = p; i < n; i++)
        R[i-p] = R[i];
    for (int i = 0; i < p; i++)
        R[n-p+i] = S[i]
}

3、三次循环时间复杂度分别为𝜪(p),𝜪(n-p),𝜪(p)，算法时间复杂度为𝜪(n)，另开了𝜪(p)的数组，算法空间复杂度为𝜪(p)。

4、更高效的算法是：先逆转R[0,,p-1]，再逆转R[p,,n-1]，最后逆转R[0,,n-1]，时间复杂度𝜪(n)，空间复杂度𝜪(1)。如n=7,p=3,R=(a,b,c|d,e,f,g)，①R=(c,b,a|d,e,f,g)，②R=(c,b,a|g,f,e,d)，③(d,e,f,g|a,b,c)。

void Reverse(int S[], int start, int last)
{
    int temp, mid = (last - start + 1) / 2;
    for (int i = 0; i < mid; i++)
    { temp = R[start+i]; R[start+i] = R[last-i]; R[last-i] = temp; }
}

void LeftShiftpinR(int R[], int n, int p)
{
    Reverse(R, 0, p-1);
    Reverse(R, p, n-1);
    Reverse(R, 0, n-1);
}

「43」（11分）、

某计算机字长为16位，按字编址，主存地址空间大小为128KB。采用单字长指令格式，指令各字段定义如下，其中OP——操作码，Ms——源操作数寻址方式，Md——目的操作数寻址方式，Rs——源操作数寄存器编号，Rd——目的操作数寄存器编号，

转移指令采用相对寻址方式，相对偏移量用补码表示，寻址方式定义如下，其中(X)表示寄存器X或主存地址X中的内容，

问答：

1️⃣该指令系统最多可有多少条指令？该计算机最多可有多少个通用寄存器？存储器地址寄存器MAR和存储器数据寄存器MDR至少各需多少位？

1、看指令字段的定义，操作码在第15,14,13,12位，源操作数寻址方式在第11,10,9位，源操作数寄存器编号在第8,7,6位，目的操作数寻址方式在第5,4,3位，目的操作数寄存器编号在第2,1,0位。操作码占4位，最多可有exp(4)=16条指令。通用寄存器编号占3位，最多可有exp(3)=8个。主存被划分为128KB÷16b=64K个单元，MAR至少log(64K)=16位，机器字长16位，MDR至少16位。

2️⃣转移指令的目标地址范围是多少？

2、表中只有相对寻址方式是转移指令，PC和Rn都是16位，主存地址也是16位，故转移指令的目标地址范围是{0x0000,...,0xFFFF}←{0,...,exp(16)-1}。

3️⃣若操作码0b0010表示加法操作，助记符add，寄存器R4和R5的编号分别为0b100和0b101，R4的内容为0x1234，R5的内容为0x5678，主存地址0x1234中的内容为0x5678，主存地址0x5678中的内容为0x1234，则汇编语句“add (R4), (R5)+”对应的机器码是什么{用十六进制表示}？该指令执行后，哪些通用寄存器和主存单元中的内容会改变？改变后的内容是什么？

3、易得该汇编语句的二进制为：0010 001 100 010 101，十六进制为：2315。该加法操作完成的动作有：①从主存单元0x1234取出源操作数0x5678；②从主存单元0x5678取出目的操作数0x1234；③两数相加0x5678+0x1234=0x68AC，结果送回0x5678；④寄存器R5的内容自增为0x5679。即，通用寄存器R5的内容变为0x5679，主存单元0x5678的内容变为0x68AC。

「44」（12分）、

某计算机的主存地址空间大小为256MB，按字节编址。指令Cache和数据Cache分离，均有8个Cache块，每个Cache块大小为64B，数据Cache采用直接映射方式。现有两个功能相同的程序A和B，其伪代码如下：

// A                              |// B
int a[256][256];                  |int a[256][256];
/*  */                            |/*  */
int sum_array1()                  |int sum_array2()
{                                 |{
    int i, j, sum = 0;            |    int i, j, sum = 0;
    for (i = 0; i < 256; i++)     |    for (j = 0; j < 256; j++)
        for (j = 0; j < 256; j++) |        for (i = 0; i < 256; i++)
            sum += a[i][j];       |            sum += a[i][j];
    return sum;                   |    return sum;
}                                 |}

假定int型变量用32位补码表示，程序编译时i,j,sum均分配在寄存器中，数组a[][]按行优先方式存放，其首地址为320{此十进制数也}。

问答：

1️⃣若不考虑用于Cache一致性维护和替换算法的控制位，则数据Cache的总容量为多少？

1、除去不考虑的部分，该Cache还有数据位64B，标签位未知，有效位1b。主存256MB也要划64B为一块，共exp(22)个块，该Cache采用直接映射方式，Memory块号->Cache块号可直接取主存块号后3位，主存log(256M)=28位的地址应划为：[Cache标签19位|Cache块号3位｜块内地址6位]。故该数据Cahce的总容量为8×(64B+19b+1b)=532B。

2️⃣Cache行号从0开始，数组元素a[0][31]和a[1][1]各自所在的主存块对应的Cache块号分别是多少？

2、由1️⃣中的分析，算出这两个元素所在主存地址再看，数组的1个小格子占连续4个主存地址。a0在主存320+(0×256+31)×4=444-bin->0001 1011 1100，对应6号Cache块；a0在主存320+(1×256+1)×4=1348-bin->0101 0100 0100，对应5号Cache块。

3️⃣程序A和B的数据访问命中率各是多少？哪个程序执行时间更短？

3、首先，i,j,sum已在寄存器中，数据访问命中率只要考虑数组a[][]，其次，数组a[][]按行优先存放，首地址320=0b000101000000位于主存5号块的起始处，1个主存块能放64B÷4B=16个数组格子，数组的1行恰能放入256÷16=16个主存块。

①程序A是这样访问数组的，{a[0][0],a[0][1],...,a[0][15]}->{a[0][16],a[0][17],...,a[0][31]}->......a[255][255]，当需要a[0][0]时将Memory[5]调入Cache[5]，剩下15个都不用再访存，只有需要a[0][16]时才需要将Memory[6]调入Cache[6]，也就是每16个格子发生缺失1次，命中率15/16=93.75%。

②程序B是这样访问数组的，a[0][0]->a[1][0]->...->a[255][0]->a[0][1]->a[1][1]->...->a[255][1]->......->a[255][255]，a[0][0]在Memory[5]对应Cache[5]，a[1][0]在Memory[21]对应也是Cache[5]，a[m][0]在Memory[5+16×m]对应的均为Cache[5]，也就是每个格子都发生缺失，命中率0%。

「45」（7分）、

假设计算机系统采用循环扫描{CSCAN}的磁盘调度策略，使用2KB的内存空间记录16384{exp(14)}个磁盘块的空闲状态。

问答：

1️⃣请说明在上述条件下如何进行磁盘空闲状态的管理？

1、用位图，16384个位刚好2KB。

2️⃣设某单面磁盘旋转速度为6000rpm，每个磁道有100个扇区，相邻磁道间的平均移动时间为1ms。若在某时刻，磁头位于100号磁道处，并沿着磁道号增大的方向移动，磁道号请求队列为50,90,30,120，对请求队列中的每个磁道需读取1个随机分布的扇区，则读完这4个扇区点共需要多少时间？

2、CSCAN调度策略访问磁道的顺序：100→120→30→50→90，总的磁头移动时间为(20+90+20+40)×1ms=170ms；6000rpm⇒0.01spr，在各磁道上寻找随机扇区的平均时间为磁盘转半圈的时间，总的寻找扇区时间为4×(1÷200s)=20ms，总的读取扇区时间为4×(1/10000s)=0.4ms。共190.4ms。

3️⃣若将磁盘替换为随机访问的Flash半导体存储器，如U盘、SSD等，是否有比CSCAN更高效的外存调度策略？

3、Flash半导体存储器给出地址可以直接锁定存储单元，不需要寻道和旋转，先来先服务{FCFS}就更好。

「46」（8分）、

设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要6页存储空间，页大小为1KB，操作系统采用固定分配局部置换策略为此进程分配4个页框。在时刻260前的进程访问情况见下表：

当该进程执行到时刻260时，要访问逻辑地址为0x17CA的数据。

问答：

1️⃣该逻辑地址对应的页面号是？

1、逻辑地址和物理地址总位数皆为log(64K)=16，页内偏移占log(1K)=10，逻辑地址和物理地址结构均应是[页面号/页框号10位|页内偏移6位]。0x17CA=0b0001011111001010，对应页面号是5。

2️⃣若采用先进先出{FIFO}置换算法，该逻辑地址对应的物理地址是多少？

2、先进先出将会把装入时刻为130的0号页面换出，5号页面装入7号页框，0b0001111111001010=0x1FCA。

3️⃣若采用时钟{CLOCK}置换算法，查找下一面的指针沿顺时针方向移动，当前指在2号页框，该逻辑地址对应的物理地址是多少？

3、指针轮转，使用位为0的置换，为1的置0。前4次，转动页框号使用位全变0：(2,0)→(9,0)→(7,0)→(4,0)，第5次，发现2号页框使用位为0，把2号页面换出，5号页面装入2号页框，0b0000101111001010=0x0BCA。

「47」（9分）、

某局域网采用CSMA/CA协议实现介质访问控制，数据传输率为10Mbps，主机甲和主机乙之间的距离为2km，信号传播速度为200000km/s。

问答：

1️⃣若主机甲和主机乙发送数据时发生冲突，假设其它主机此时间段不发送数据，则从开始发送数据时刻起，到两台主机均检测到冲突为止，最短需经过多长时间？最长需经过多长时间？

1、就好比弹珠碰撞。最短：中途相撞，去程和回程皆1km，两主机均需2km÷200000km/s=0.01ms检测到碰撞；最长：出门相撞，一方0ms检测到碰撞，另一方需4km÷200000km/s=0.02ms检测到碰撞。

2️⃣若网络不存在任何冲突与差错，主机甲总是以标准的最长以太网数据帧1518B向主机乙发送数据，主机乙每成功收到一个数据帧后立即向主机甲发送一个64B的确认帧，主机甲收到确认帧后方可发送下一个数据帧。不考虑以太网的前导码，此时主机甲的有效数据传输速率是多少？

2、重点是记得以太网帧首尾要占去18B，源地址6B，目的地址6B，类型2B，帧检验序列4B，最大有效数据载荷1500B。主机甲乙一次发送确认周期是(1518×8b)÷exp10(7)bps+0.01ms+(64×8b)÷exp10(7)bps+0.01ms=1.2856ms，主机甲的有效数据传输速率是1500×8b÷1.2856ms=9.33Mbps。