什么是黑盒测试法？

[答案解析]

黑盒测试法把程序看成一个黑盒子，完全不考虑程序的内部结构和处理过程，它只检查程序功能是否能按照规格说明书的规定正常使用，程序是否能适当地接收输入数据，产生正确地输出信息。

某“调整工资”处理模块接受一个“职称”的变量，根据职称的不同（助教，讲师，副教授，教授）作不同的处理，其中若是助教还必须输入工龄，只有工龄超过两年才能调整工资。请用等价类划分法设计测试用例。

[答案解析]

划分等价类：

假定某航空公司规定，乘客可以免费托运重量不超过30公斤的行李。当行李重量超过30公斤时，对头等舱的国内乘客超重部分每公斤收费4元，对其它舱的国内乘客超重部分每公斤收费6元，对国外乘客超重部分每公斤收费比国内乘客多一倍，对残疾乘客超重部分每公斤收费比正常乘客少一半。

用判定树表示计算行李费的算法。

[答案解析]

定义三元组(a,b,c)(其中a,b,c均为正数)的距离D=|a-b|+|b-c|+|c-a|。给定3个非空整数集合S₁、S₂和S₃，按升序分别存储在3个数组中。设计一个尽可能高效的算法,计算并输出所有可能的三元组(a,b, c) (a∈S₁, b ∈S₂, c ∈S₃)中的最小距离。例如 S₁={-1,0,9}，S₂ = {-25,-10,10, 11}，S₃ ={2,9,17,30, 41}，则最小距离为2，相应的三元组为(9,10,9)。要求:

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

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

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

1)算法的基本设计思想

①使用D_min记录所有已处理过的三元组的最小距离，初值为一个足够大的整数。

② 集合 S₁、S₂和S₃分别保存在数组A、B、C中。数组的下标变量i=j=k=0,当i<|S₁|、j<|S₂|且k <|S₃|时 (|S|表示集合S中的元素个数)，循环执行a)~c)。 

a) 计算 (A[i], B[j], C[k]) 的距离D;(计算D) 

b) 若Dmin，则D_min=D;(更新D)

c) 将 A[i], B[j], C[k]中的最小值的下标+1;(对照分析:最小值为a，最大值为c，这里c不变而更新a，试图寻找更小距离D)

③ 输出Dmin，结束。

2)算法实现:

#define INT MAX 0x7fffffff 

int abs_(int a) {//计算绝对值

     if(a<0) return -a;

     else return a;

}

bool xls min(int a,int b,int c){//a是否是三个数中的最小值

       if(a<=b&&a<=c) return true; 

       return false;

}

int findMinofTrip(int A[l,int n,int B[],int m,int C[], int p){

      //D min用于记录三元组的最小距离，初值赋为INTMAX 

     int i=0,j=0,k=0,D min=INT MAX,D; 

     while(i0){

            D=abs_(A[i]-B[j])+abs_(B[j]-C[k])+abs_(C[k]-A[i]);//计算D

            if(D

            if(xls_min(A[i],B[j],C[k])) i++; //更新a 

            else if(xls_min(B[j],C[k],A[i]))j++; 

            else k++;

}

return D_min;

3) 设n =|S₁|+|S₂|+|S₃|，时间复杂度为O(n)，空间复杂度为O(1)。

若任一个字符的编码都不是其他字符编码的前缀，则称这种编码具有前缀特性。

现有某字符集(字符个数≥2)的不等长编码，每个字符的编码均为二进制的0、1序列，最长为L位，且具有前缀特性。请回答下列问题:

1)哪种数据结构适宜保存上述具有前缀特性的不等长编码?

2)基于你所设计的数据结构，简述从0/1串到字符串的译码过程。

3)简述判定某字符集的不等长编码是否具有前缀特性的过程。

1)使用一棵二叉树保存字符集中各字符的编码，每个编码对应于从根开始到达某叶结点的一条路径，路径长度等于编码位数，路径到达的叶结点中保存该编码对应的字符。

2)从左至右依次扫描0/1串中的各位。从根开始，根据串中当前位沿当前结点的左子指针或右子指针下移，直到移动到叶结点时为止。输出叶结点中保存的字符。然后从根开始重复这个过程，直到扫描到0/1串结束，译码完成。

3)二叉树既可用于保存各字符的编码，又可用于检测编码是否具有前缀特性。判定编码是

否具有前缀特性的过程，也是构建二叉树的过程。初始时，二叉树中仅含有根结点，其左子指针和右子指针均为空。

依次读入每个编码C，建立/寻找从根开始对应于该编码的一条路径，过程如下:

对每个编码，从左至右扫描C的各位，根据C的当前位(0或1)沿结点的指针(左子指针或右子指针)向下移动。当遇到空指针时，创建新结点，让空指针指向该新结点并继续移动。沿指针移动的过程中，可能遇到三种情况:

若遇到了叶结点(非根)，则表明不具有前缀特性，返回。

②若在处理C的所有位的过程中，均没有创建新结点，则表明不具有前缀特性，返回。

③若在处理C的最后一个编码位时创建了新结点，则继续验证下一个编码。若所有编码均通过验证，则编码具有前缀特性。

有实现x x y的两个C语言函数如下:

unsigned umul (unsigned x, unsigned y) { return x*y;} 

int imul (int x, int y) {return x * y;}

假定某计算机M中ALU只能进行加减运算和逻辑运算。请回答下列问题。

1)若M的指令系统中没有乘法指令，但有加法、减法和位移等指令，则在M上也能实现

上述两个函数中的乘法运算，为什么?

2)若M的指令系统中有乘法指令，则基于ALU、位移器、寄存器以及相应控制逻辑实现

乘法指令时，控制逻辑的作用是什么?

3)针对以下三种情况:①没有乘法指令;②有使用ALU和位移器实现的乘法指令;

③有使用阵列乘法器实现的乘法指令，函数umul()在哪种情况下执行时间最长?哪种情况下执行的时间最短?说明理由

4)n位整数乘法指令可保存2n位乘积，当仅取低n位作为乘积时，其结果可能会发生溢出。当 n =32,x=23- 1,y=2时，带符号整数乘法指令和无符号整数乘法指令得到的 x x y的2n位乘积分别是什么(用十六进制表示)?此时函数umul()和imul()的返回结果是否溢出?对于无符号整数乘法运算，当仅取乘积的低n位作为乘法结果时，如何用2n位乘积进行溢出判断?

1)乘法运算可以通过加法和移位来实现。编译器可以将乘法运算转换为一个循环代码段，在循环代码段中通过比较、加法和移位等指令实现乘法运算。

2)控制逻辑的作用是控制循环次数，控制加法和移位操作。

3)①最长，③最短。对于①，需要用循环代码段(即软件)实现乘法操作，因而需要反复执行很多条指令，而每条指令都需要取指令、译码、取数、执行并保存结果，所以执行时间很长;对于②和③，都只需用一条乘法指令实现乘法操作，不过②中的乘法指令需要多个时钟周期才能完成，而③中的乘法指令可以在一个时钟周期内完成，所以③的执行时间最短。

4)当n=32,x=23- 1,y=2时，带符号整数和无符号整数乘法指令得到的64位乘积都是0000 0000 FFFF FFFEH。int型的表示范围为[-23,23- 1]，故函数imul()的结果溢出; unsigned int型的表示范围为[0,232-1]，故函数umul()的结果不溢出。对于无符号整数乘法，若乘积高n位全为0，即使低n位全为1也正好是232-1，不溢出，否则溢出。

假定主存地址为32位，按字节编址，指令Cache和数据Cache与主存之间均采用8路组相联映射方式，直写(WriteThrough)写策略和LRU替换算法，主存块大小为64B，数据区容量各为32KB。开始时Cache均为空。请回答下列问题。1)Cache每一行中标记(Tag)、LRU位各占几位?是否有修改位?

2)有如下C语言程序段:

   for (k = 0; k< 1024;k++) 

   s[k] = 2 *s[k];

   若数组s及其变量k均为int型，int型数据占4B，变量k分配在寄存器中，数组s在主存中的起始地址为008000C0H，则该程序段执行过程中，访问数组s的数据Cache     缺失次数为多少?

3)若CPU最先开始的访问操作是读取主存单元00010003H中的指令，简要说明从Cache

中访问该指令的过程，包括Cache缺失处理过程。

1)主存块大小为64B=26字节，所以主存地址低6位为块内地址，Cache组数为32KB/(64Bx8)=64=26，故主存地址中间6位为Cache组号，主存地址中高32-6-6=20位为标记，采用8路组相联映射，故每行中的LRU位占3位，采用直写方式，故没有修改位。

2)0080 00C0H= 0000 0000 1000 0000 0000 0000 1100 0000B，主存地址的低6位为块内地址，为全0，故s位于一个主存块的开始处，占1024x4B/64B=64个主存块;在执行程序段的过程中，每个主存块中的64B/4B=16个数组元素依次读、写1次，因而对每个主存块，总是第一次访问缺失，此时会将整个主存块调入Cache，之后每次都命中。综上，数组s的数据Cache访问缺失次数为64次。

3)0001 0003H=0000 0000 0000 0001 0000 000000 000011B，根据主存地址划分可知，组

索引为0，故该地址所在主存块被映射到指令Cache的第0组;因为Cache初始为空，所有Cache行的有效位均为0，所以Cache访问缺失。此时，将该主存块取出后存入指令Cache的第0组的任意一行，并将主存地址高20位(00010H)填入该行标记字段，设置有效位，修改LRU位，最后根据块内地址000011B从该行中取出相应的内容。

现有 5 个操作 A、B、C、D和E操作 C必须在 A 和B 完成后执行，操作 E必须在 C和 D 完成后执行，请使用信号量的 wait0、signal0操作 (P、V 操作)描述上述操作之间的同步关系，并说明所用信号量及其初值。

本题要求实现操作的先后顺序，没有互斥关系，是一个简单的同步问题。本题虽然有 5 个操作，但是只有 4 个同步关系，因此分别设置信号量 SAC、SBC、SCE 和SDE 对应4 个同步关系。

Semaphore SAC = 0;   //控制A和C的执行顺序

Semaphore SBC = 0;   //控制B和C的执行顺序

Semaphore SCE  0;    //控制C和E的执行顺序

Semaphore SDE=0;   //控制D和E的执行顺序

5个操作可描述为如下

CoBegin
A( ）{
完成动作A;
V(SAc);             //实现A、C之间的同步关系
}
B( ){
完成动作B;
   V(Sec);          //实现B、C之间的同步关系
C( ){
                    //C必须在A、B都完成后才能完成
P(SAc);
P(Sec);
完成动作C;
//实现C、E之间的同步关系
V(ScE);
D(）{
完成动作D;
V(SD);             //实现D、E之间的同步关系
}
E(){
         //E必须在完成C、D之后执行
         P(ScE);
         P(SDe)
         完成动作E;
}
CoEnd

某32位系统采用基于二级页表的请求分页存储管理方式，按字节编址，页目录项和页表项长度均为4字节，虚拟地址结构如下所示。

 某C程序中数组a[1024][1024]的起始虚拟地址为10800000H，数组元素占4字节，该程序运行时，其进程的页目录起始物理地址为00201000H，请回答下列问题。

1)数组元素a[1][2]的虚拟地址是什么?对应的页目录号和页号分别是什么?对应的页目录项的物理地址是什么?若该目录项中存放的页框号为00301H，则a[1][2]所在页对应的页表项的物理地址是什么?

2)数组a在虚拟地址空间中所占的区域是否必须连续?在物理地址空间中所占区域是否必须连续?

3）已知数组a 按行优先方式存放，若对数组a 分别按行遍历和按列遍历，则哪种遍历方式 的局部性更好？

1)①页面大小=22B=4096B=4KB。每个数组元素4B，每个页面可以存放4KB/4B=1024个数组元素，正好是数组的一行，数组a按行优先方式存放。10800000H的虚页号为10800H，因此a[0]行存放在虚页号为10800H的页面中，a[1]行存放在页号为10801H的页面中。a[1][2]的虚拟地址为10801000H+4x2=10801 008H。

②转换为二进制0001000010 0000000001 000000001000，根据虚拟地址结构可知，对

应的页目录号为042H，页号为001H。

③进程的页目录表起始地址为00201000H，每个页目录项长4B，因此042H号页目录

项的物理地址是00201000H+4x42H=00201108H。

④页目录项存放的页框号为00301H，二级页表的起始地址为00301000H，因此a[1][2]

所在页的页号为001H，每个页表项4B，因此对应的页表项物理地址是00301 000H+001Hx4=00301 004H。

2 ）根据数组的随机存取特点，数组a 在虚拟地址空间中所占的区域必须连续，由于数组a 不止占用一页，相邻逻辑页在物理上不一定相邻，因此数组a 在物理地址空间中所占的 区域可以不连续。

3）由 1）可知每个页面正好可以存放一整行的数组元素， “按行优先方式存放”意味着数 组的同一行的所有元素都存放在同一个页面中，同一列的各个元素都存放在不同的页面 中，因此数组a 按行遍历的局部性较好。

某校网有两局域网，通过路器 R1R2 R3 联后接入 Intermet，S1和2为以太网交换机。局域网采用静态 IP 地址配置，路由器部分接口以及各主机的 IP 地址如下图所示。

假设 NAT 转换表结构为

请回答下列问题:

1）为使 H2和H3能够 Web 服务器(使用默认端口号)需要进行什么配置?

2) H2主动访问 Web 服务器时，将 HTTP 请求报文封装到 IP 数据报P发送，则H2发送 P的源IP 地址和目的 IP 地址分别是什么?经过 R3 转发后，P的源址和目的IP 地址分别是什么?经过 R2 转发后，P 的源IP地址和目的 IP 地址分别是什么?

1)两个子网使用了相同的网段，且路由器开启了NAT功能，加上题干给出了NAT表的结

构，因此需要配置NAT表。路由器R2开启NAT服务，当路由器R2从WAN口收到 H2或H3发来的数据时，根据NAT 表发送给Web服务器的对应端口。外网IP地址应该为路由器的外端IP地址，内网IP地址应该为Web服务器的地址，Web服务器的默认端口为80，因此内网端口号固定为80，当其他网络的主机访问Web服务器时，默认访问的端口应该也是80，但是访问的目的IP是路由器的IP地址，因此NAT 表中的外部端口最好也统一为80。题目中并未要求对H1进行访问，因此H1的NAT表项可以不写。R2的NAT表配置如下:

2)由于启用了NAT服务，H2发送的P的源IP地址应该是H2的内网地址，目的地址应

该是R2的外网IP地址，源IP地址是192.168.1.2，目的IP地址是203.10.2.2。R3转发后，将P的源IP地址改为R3的外网IP地址，目的IP地址仍然不变，源IP地址是203.10.2.6，目的IP地址是203.10.2.2。R2转发后，将P的目的IP地址改为Web服务器的内网地址，源地址仍然不变，源IP地址是203.10.2.6，目的IP地址是192.168.1.2。

（15 分）已知无向连通图 G 由顶点集 V 和边集 E 组成|E|>0，当 G 中度为奇数的顶点个数 为不大于 2 的偶数时，G 存在包含所有边且长度为|E|的路径(称为 EL 路径)，设图 G 采用邻接 矩阵存储，类型定义如下：

Typedef struct{
                                    //图的定义 
int numVertices，numEdges; 
                                    //图中实际的顶点数和边数 
Char VertticesList[MAXV]; 
                                    //顶点表。MAXV 为已定义常量 
Int Edge[MAXV][MAXV];
                                    //邻接矩阵 
};MGraph;

请设计算法：int IsExistEL(MGraph G)，判断 G 是否存在 EL 路径，若存在，则返回 1，否则，返回 0，要求： 

（1）给出算法的基本设计思想。 

（2）根据设计思想采用 C 或者 C++语言描述算法，关键之处给出注释。 

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

【答案解析】

（1）算法的基本设计思想

对于采用邻接矩阵存储的无向图，邻接矩阵每一行（列）中非零元素的个数为本行（列）对应顶点的度。可以依次计算连通图 G 中各顶点的度，并记录度为奇数的顶点个数，若个数为 0或 2，则返回 1，否则返回 0。

（2）算法实现

Int IsExistEL(MGraph G)
                   //采用邻接矩阵存储，判断图是否存在 EL 路径
{ int degree,i,j, count=0;
 for(i=0;I<G.numVertices;i++)
 { degree=0;
 for(j=0;j<G.numVertices;j++)
                   //依次计算各个顶点的度
 degree+=G.Edge[i][j];
 if(degree%2!=0)
 count++;   //对度为奇数的顶点计数
}
if（count ==0 || count == 2）
 return 1；  //存在 EL 路径，返回 1
else
 return 0；  //不存在 EL 路径，返回 0
}

（3）算法的时间复杂度和空间复杂度

本

（6 分）已知某排序算法：

void cmpCountSort（int a[],int b[], int n]）
{         int i,j, *count;
          count=(int *)malloc(sizeof(int) *n);
                                      //C++语言：count=new int[n];
              for(i=0;i<n;i++) count[i]=0;
              for(i=0;i<n-1;i++)
                     for(j=i+1;j<n;j++)
                            if(a[i]<a[j])    count[j]++;
                            else               count[i]++;
              for(i=0;i<n;i++)          b[count[i]]=a[i];
              free(count);                 //C++语言：delete count；
}

请回答下列问题。

（1）若有 int a[]={25,-10,25,10,11,19}，b[6]；，则调用 cmpCountSort（a,b,6）后数组 b中的内容是什么

（2）若 a 中含有 n 个元素，则算法执行过程中，元素之间的比较次数是多少？

（3）该算法是稳定的吗？若是，则阐述理由；否则，修改为稳定排序算法。

【答案解析】

cmpCountSort 算法基于计数排序的思想，对序列进行排序。cmpCountSort 算法遍历数组中的元素，count 数组记录比对应待排序数组元素下标大的元素个数，例如，count[1]=3 的意思是数组 a 中有 3 个元素比 a[1]大，即 a[1]是第 4 大元素，a[1]的正确位置应是 b[3]。

（1）数组 b[ ]={-10，10，11，19，25，25}

（2）由代码 for(i=0;i

（3）不是稳定的，需要将程序中的 if 语句修改如下：

 if(a[i]<=a[j]) count[j]++;
  else count[i]++;

如果不加等号，两个相等的元素比较时，前面元素的 count 值会加 1，导致原序列中靠前的元素在排序后的序列中处于靠后的位置。

（15 分）假定计算机 M 字长为 16 位，按字节编址，连接 CPU 和主存的系统总线中地址 线为 20 位、数据线为 8 位，采用 16 位定长指令字，指令格式及其说明如下：

其中，op1~op3 为操作码，rs、rt 和 rd 为通用寄存器编号，R[r]表示寄存器 r 的内容，imm 为 立即数，target 为转移目标的形式地址。请回答下列问题。

（1）ALU 的宽度是多少位？可寻址主存空间大小为多少字节？指令寄存器、主存地址寄存 器（MAR）和主存数据寄存器（MDR）分别应有多少位？ 

（2）R 型格式最多可定义多少种操作？I 型和 J 型格式总共最多可定义多少种操作？通用寄 存器最多有多少个？ 

（3）假定 op1 为 0010 和 0011 时，分别表示带符号整数减法和带符号整数乘法指令，则指令 01B2H 的功能是什么（参考上述指令功能说明的格式进行描述）？若 1、2、3 号通用寄存器 当前内容分别为 B052H、0008H、0020H，则分别执行指令 01B2H 和 01B3H 后，3 号通用寄 存器内容各是什么？各自结果是否溢出？ 

（4）若采用 I 型格式的访存指令中 imm（偏移量）为带符号整数，则地址计算时应对 imm 进 行零扩展还是符号扩展？ 

（5）无条件转移指令可以采用上述哪种指令格式？

【答案解析】 

（1）ALU 的宽度为 16 位。可寻址主存空间大小为 2^20 字节（或 1MB）。指令寄存器、MAR 和 MDR 各有 16 位、20 位和 8 位。 

（2）R 型最多有 24（或 16）种操作。I 型和 J 型总共最多有 63 种操作。通用寄存器最多有 4 个。 

（3）指令 01B2H=000000 01 10 11 0010B，其功能为 R[3]←R[1]-R[2]。 执行指令 01B2H 后，R[3]=B052H-0008H=B04AH；结果不益出；执行指令 01B3H 后，R[3]=R[1] ×R[2]=B052H×0008H=8290H，结果溢出。 

（4）应对 imm 进行符号扩展。 

（5）无条件转移指令可以采用 J 型格式。

（8 分）假设计算机 M 的主存地址为 24 位，按字节编址；采用分页存储管理方式，虚拟 地址为 30 位，页大小为 4KB；TLB 采用 2 路组相联方式和 LRU 替换策略，共 8 组。请回答 下列问题。 

（1）虚拟地址中哪几位表示虚页号？哪几位表示页内地址？ 

（2）已知访问 TLB 时虚页号高位部分用作 TLB 标记，低位部分用作 TLB 组号，M 的虚拟 地址中哪几位是 TLB 标记？哪几位是 TLB 组号？

（3）假设 TLB 初始时为空，访问的虚页号依次为 10、12、16、7、26、4、12 和 20，在此过 程中，哪一个虚页号对应的 TLB 表项被替换？说明理由。 

（4）若将 M 中的虚拟地址位数增加到 32 位，则 TLB 表项的位数增加几位？

【答案解析】 

（1）因为按字节编址，页大小为 4KB=212B,所以虚拟地址中高 30-12=18 位表示虚页号。虚 拟地址低 12 位表示页内地址。 

（2）因为 TLB 采用 2 路组相联方式，共 8=23 组，所以虚拟地址(或虚页号）中高 18-3=15 位 为 TLB 标记；虚拟地址中随后 3 位（或虚页号中低 3 位）为 TLB 组号。 

（3）虚页号 4 对应的 TLB 表项被替换。因为虚页号与 TLB 组号的映射关系为 TLB 组号=虚 页号 mod TLB 组数=虚页号 mod 8，因此，虚页号 10、12、16、7、26、4、12、20 映射到的 TLB 组号依次为 2、4、0、7、2、4、4、4。TLB 采用 2 路组相联方式，从上述映射到的 TLB 组号序列可以看出，只有映射到 4 号组的虚页号数量大于 2，相应虚页号依次是 12、4、12 和 20。根据 LRU 替换策略，当访问第 20 页时，虚页号 4 对应的 TLB 表项被替换出来。 

（4）虚拟地址位数增加到 32 位时，虚页号增加了 32-30=2 位，使得每个 TLB 表项中的标记 字段增加 2 位，因此，每个 TLB 表项的位数增加 2 位。

（7 分）下表给出了整型信号量 S 的 wait（）和 signal（）操作的功能描述，以及采用开/ 关中断指令实现信号量操作互斥的两种方法。

请回答下列问题。 

（1）为什么在 wait（）和 signal（）操作中对信号量 S 的访问必须互斥执行？ 

（2）分别说明方法 1 和方法 2 是否正确。若不正确，请说明理由。 

（3）用户程序能否使用开/关中断指令实现临界区互斥？为什么？

【答案解析】 

（1）因为信号量 S 是能够被多个进程共享的变量，多个进程都可以通过 wait（）和 signal（） 对 S 进行读、写操作。所以，在 wait（）和 signal（）操作中对 S 的访问必须是互斥的。 

（2）方法 1 是错误的。在 wait（）中，当 S<=0 时，关中断后，其他进程无法修改 S 的值， while 语句陷入死循环。方法 2 是正确的。 

（3）用户程序不能使用开/关中断指令实现临界区互斥。因为开中断和关中断指令都是特权指 令。

（8 分）某计算机用硬盘作为启动盘，硬盘第一个扇区存放主引导记录，其中包含磁盘引 导程序和分区表。磁盘引导程序用于选择要引导哪个分区的操作系统，分区表记录硬盘上各 分区的位置等描述信息。硬盘被划分成若干个分区，每个分区的第一个扇区存放分区引导程 序，用于引导该分区中的操作系统。系统采用多阶段引导方式，除了执行磁盘引导程序和分 区引导程序外，还需要执行 ROM 中的引导程序。请回答下列问题。 

（1）系统启动过程中操作系统的初始化程序、分区引导程序、ROM 中的引导程序、磁盘引 导程序的执行顺序是什么？ 

（2）把硬盘制作为启动盘时，需要完成操作系统的安装、磁盘的物理格式化、逻辑格式化、 对磁盘进行分区，执行这 4 个操作的正确顺序是什么？ 

（3）磁盘扇区的划分和文件系统根目录的建立分别是在第（2）问的哪个操作中完成的？

【答案解析】 

（1）执行顺序依次是 ROM 中的引导程序、磁盘引导程序、分区引导程序、操作系统的初始 化程序。 

（2）4 个操作的执行顺序依次是磁盘的物理格式化、对磁盘进行分区、逻辑格式化、操作系 统的安装。 

（3）磁盘扇区的划分是在磁盘的物理格式化操作中完成的。文件系统根目录的建立是在逻辑 格式化操作中完成的。

（9 分）某网络拓扑如题 47 图所示，以太网交换机 S 通过路由器 R 与 Internet 互联。路由 器部分接口、本地域名服务器、H1、H2 的 IP 地址和 MAC 地址如图中所示。在 t0 时刻 H1 的 ARP 表和 S 的交换表均为空，H1 在此刻利用浏览器通过域名 www.abc.com 请求访问 Web 服 务器，在 t1 时刻（t1＞t0）S 第一次收到了封装 HTTP 请求报文的以太网帧，假设从 t0 到 t1 期 间网络未发生任何与此次 Web 访问无关的网络通信。

请回答下列问题。 

（1）从 t0到 t1 期间，H1 除了 HTTP 之外还运行了哪个应用层协议？从应用层到数据链路层， 该应用层协议报文是通过哪些协议进行逐层封装的？ 

（2）若 S 的交换表结构为：< MAC 地址，端口>，则 t1时刻 S 交换表的内容是什么？ 从 t0 到 t1 期间，H2 至少会接收到几个与此次 Web 访问相关的帧？接收到的是什么帧？帧的 目的 MAC 地址是什么？

【答案解析】 

（1）从 t0 到 t1 期间，H1 除了 HTTP 之外还运行了 DNS 应用层协议；DNS 报文从应用层到 数据链路层，逐层封装关系是：DNS 报文→UDP 数据报→IP 数据报→CSMA/CD 帧。 （2）S 在 t1 时刻的交换表为：

（3）H2 至少会接收到 2 个帧；接收到的均是封装 ARP 查询报文的以太网帧；这些帧的目的 MAC 地址均是：FF-FF-FF-FF-FF-FF。

设线性表L=（a₁ ，a₂，a₃，···，a_n-2,a_n-1, a_n）采用带头结点的单链表保存，链表中的 结点定义如下：

typedef struct node
{ int data; 
struct node*next; 
} NODE；

请设计一个空间复杂度为 O(1)且时间上尽可能高效的算法，重新排列 L 中的各结点，得到 线性表L' =（a1 ，a_n, a₂，a_n-1,a₃，a_n-2,···）。要求： 

（1）给出算法的基本设计思想。 

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

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

【答案解析】

（1）算法的基本设计思想：先观察 L (a1 ,a2,a3,……,an-2, an-1,an ) 和 L’ (a1,an ,a2 ,an-1, a3 ,an- 2,……)，发现 L’ 是由 L 摘取第一个元素，再摘取倒数第一个元素……依次合并而成的。为了 方便链表后半段取元素，需要先将 L 后半段原地逆置［题目要求空间复杂度为 O(1)，不能借 助栈］，否则每取最后一个结点都需要遍历一次链表。①先找出链表 L 的中间结点，为此设置 两个指针 p 和 q，指针 p 每次走一步，指针 q 每次走两步，当指针 q 到达链尾时，指针 p 正 好在链表的中间结点；②然后将 L 的后半段结点原地逆置。③从单链表前后两段中依次各取 一个结点，按要求重排。 

（2）算法实现：

void change_list(NODE *h) {
        NODE *p,*q,*r,*s; 
        p=q=h; 
        while(q->next!=NULL) { // 寻找中间结点 
              p=p->next; //p 走一步 
              q=q->next; 
             if(q->next!=NULL) q=q->next; //q 走两步 
      }  
     q=p->next; //p 所指结点为中间结点， q 为后半段链表的首结点 
     p->next=NULL; 
     while(q!=NULL) { // 将链表后半段逆置 
           r=q->next; 
          q->next=p->next; 
          p->next=q; 
          q=r; 
    }  
    s=h->next; //s 指向前半段的第一个数据结点，即插入点 
    q=p->next; //q 指向后半段的第一个数据结点 
    p->next=NULL; 
    while(q!=NULL) { // 将链表后半段的结点插入到指定位置
          r=q->next; //r 指向后半段的下一个结点 
          q->next=s->next; // 将 q 所指结点插入到 s 所指结点之后 
          s->next=q; s=q->next; //s 指向前半段的下一个插入点 
          q=r; 
      }  
}

（3）第 1 步找中间结点的时间复杂度为 O(n)，第 2 步逆置的时间复杂度为 O(n)，第 3 步合 并链表的时间复杂度为 O(n)，所以该算法的时间复杂度为 O(n)。

请设计一个队列，要求满足：①初始时队列为空；②入队时，允许增加队列 占用空间；③出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减； ④入队操作和出队操作的时间复杂度始终保持为 O(1)。请回答下列问题： 

（1）该队列是应选择链式存储结构，还是应选择顺序存储结构？ 

（2）画出队列的初始状态，并给出判断队空和队满的条件。 

（3）画出第一个元素入队后的队列状态。 

（4）给出入队操作和出队操作的基本过程。

【答案解析】

（1）顺序存储无法满足要求②的队列占用空间随着入队操作而增加。根据要求来分析：要求 ①容易满足；链式存储方便开辟新空间，要求②容易满足；对于要求③，出队后的结点并不 真正释放，用队头指针指向新的队头结点，新元素入队时，有空余结点则无须开辟新空间， 赋值到队尾后的第一个空结点即可，然后用队尾指针指向新的队尾结点，这就需要设计成一 个首尾相接的循环单链表，类似于循环队列的思想。设置队头、队尾指针后，链式队列的入 队操作和出队操作的时间复杂度均为 O(1)，要求④可以满足。因此，采用链式存储结构（两 段式单向循环链表），队头指针为 front，队尾指针为 rear。 

（2）该循环链式队列的实现，可以参考循环队列，不同之处在于循环链式队列可以方便增加 空间，出队的结点可以循环利用，入队时空间不够也可以动态增加。同样，循环链式队列也 要区分队满和队空的情况，这里参考循环队列牺牲一个单元来判断。初始时，创建只有一个 空闲结点的循环单链表，头指针 front 和尾指针 rear 均指向空闲结点，如下图所示。

队空的判定条件： front == rear。 队满的判定条件： front == rear->next 。 

（3）插入第一个元素后的状态如下图所示。

（4）操作的基本过程如下：

有 n（n≥3）位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在 圆桌中心有 m（m≥1）个碗，每两位哲学家之间有一根筷子。每位哲学家必须取到一个碗和两 侧的筷子后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。为使尽可能多的哲学 家同时就餐，且防止出现死锁现象，请使用信号量的 P、V 操作［wait()、signal()操作］描述上 述过程中的互斥与同步，并说明所用信号量及初值的含义。

【答案解析】 回顾传统的哲学家问题，假设餐桌上有 n 个哲学家、n 根筷子，那么可以用这种方法避免死 锁：限制至多允许 n-1 个哲学家同时“抢”筷子，那么至少会有 1 个哲学家可以获得两根筷 子并顺利进餐，于是不可能发生死锁的情况。本题可以用碗这个限制资源来避免死锁：当碗 的数量 m 小于哲学家的数量 n 时，可以直接让碗的资源量等于 m，确保不会出现所有哲学家 都拿一侧筷子而无限等待另一侧筷子进而造成死锁的情况；当碗的数量 m 大于等于哲学家的 数量 n 时，为了让碗起到同样的限制效果，我们让碗的资源量等于 n-1，这样就能保证最多只 有 n-1 个哲学家同时进餐，所以得到碗的资源量为 min{ n-1, m}。在进 PV 操作时，碗的资源 量起限制哲学家取筷子的作用，所以需要先对碗的资源量进行 P 操作。具体过程如下：

// 信号量
semaphore bowl; // 用于协调哲学家对碗的使用
semaphore chopsticks[n]; // 用于协调哲学家对筷子的使用
for(int i=0; i<n; i++)
      chopsticks[i]=1; // 设置两个哲学家之间筷子的数量
bowl=min(n-1,m); //bowl ≤ n-1，确保不死锁
CoBegin
while(TRUE) { // 哲学家 i 的程序
       思考;
  P(bowl); // 取碗 
  P(chopsticks[i]); // 取左边筷子 
  P(chopsticks[(i+1)%n]); // 取右边筷子 就餐;  
  V(chopsticks[i]); 
  V(chopsticks[(i+1)%n]); 
  V(bowl); 
} 
CoEnd