考研真题

单元测试一般以        测试为主，        测试为辅。

成本估计方法主要有        、        和算法模型估计三种类型。

什么是软件危机？为什么会产生软件危机？

[答案解析]

软件危机是指软件在开发和维护过程中遇到的一系统严重问题，主要包含二方面的问题，一是如何开发利用软件，二是如何维护数量不断膨胀的已有软件。产生软件危机的原因，一方面与软件本身的特点有关，另一方面和软件开发与维护的方法不正确有关。

耦合性有哪几种类型？其耦合度的顺序如何？

[答案解析]

低：非直接耦合→数据耦合→标记耦合→控制耦合→外部耦合→公共耦合→内容耦合：高

简述需求分析工作可以分成哪四个方面？

软件需求分析的有哪三个基本原则？

[答案解析]

需求分析阶段分成四个方面：对问题的识别、分析与综合、制定规格说明和评审。

三个基本原则：必须能够表达和理解问题的数据域和功能域；必须按自顶向下、逐步分解的方式对问题进行分解和不断细化；要给出系统的逻辑视图和物理视图。

什么是黑盒测试法？

[答案解析]

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

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

[答案解析]

划分等价类：

假定某航空公司规定，乘客可以免费托运重量不超过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）用户程序不能使用开/关中断指令实现临界区互斥。因为开中断和关中断指令都是特权指 令。