|
二、综合应用题：41～47小题，共70分。请将答案写在答题纸指定位置上。
41．
【答案解析】此题考察的知识点是图的存储以及关键路径求解的综合知识。
（1）由题可以画出待定上三角矩阵的结构图如下（图中“？”待定元素）
可以看出，第一行至第五行主对角线上方的元素分别5、4、3、2、1个，由此可以画出
压缩存储数组中的元素所属行的情况，如下图所示：
|
4
|
6
|
∞
|
∞
|
∞
|
5
|
∞
|
∞
|
∞
|
4
|
3
|
∞
|
∞
|
3
|
3
|
将个元素填入各行即得邻接矩阵：（2分）
A=
(2)根据第一步所得矩阵A容易做出有向带权图G，如下：（2分）
(3)下图中粗线箭头所标识的4个活动组成G的关键路径（3分）
由上图容易求得图的关键路径长度为：4+5+4+3=16。
42．
【答案解析】此题考察的知识点是基本算法的灵活运用。
（1）算法的基本设计思想：（5分）
1) 比较笨的方法：
将两升序序列归并排序，然后求其中位数，时间复杂度是O(n)，空间复杂度O(n)。
2) 高效的方法：分别求两个升序序列A和B的中位数，设为a和b。
如果a=b，则a或者b即为所求的中位数。
原因：如果将两序列归并排序，则最终序列中，排在子序列ab前边的元素为先前两序列中排在a和b前边的元素；排在子序列ab后边的元素为先前两序列a和b后边的元素。所以子序列ab一定位于最终序列的中间，有因为a=b，显然a就是中位数。
如果a≠b（假设a<b），中位数只能出现在（a，b）范围内。
原因：同样可以用归并排序后的序列来验证，归并后排序后必然有形如…a…b…的序列出现，中位数必然出现在（a，b）范围内。因此可以做如下处理：舍弃a所在序列A之中比较小的一半，同时舍弃b所在序列B之中比较大的一半。在保留的两个升序序列中求出新的中位数a和b，重复上述过程，直到两个序列只含一个元素为止，则较小者即为所求中位数。
（2）算法实现（高效方法）：（8分）
int Search(int A[], int B[], int n)
{
int s1,e1,mid1,s2,e2,mid2;
s1=0;
e1=n-1;
s2=1;
e2=n-1;
while(s1!=e1||s2!=e2)
{
mid1=(s1+e1)/2;
mid2=(s2+e2)/2;
if(A[mid1]==B[mid2])
return A[mid1];
if(A[mid1]<B[mid2])
{
//分别考虑奇数和偶数，保持两个子数组元素个数相等
if（（s1+e1）%2==0）//若元素个数为奇数
{
s1=mid1;//舍弃A中间点以前部分且保留中间点
e2=mid2; //舍弃B中间点以后部分且保留中间点
}
else//若元素个数为偶数
{
s1=mid1+1;//舍弃A中间点以前部分且保留中间点
e2=mid2; //舍弃B中间点以后部分且保留中间点
}
}
else
{
if((s1+e1)%2==0)//若元素个数为奇数个
{
e1=mid1;//舍弃A中间点以后部分且保留中间点
s2=mid2;//舍弃B中间点以前部分且保留中间点
}
else //若元素个数为偶数个
{
e1=mid1+1；//舍弃A中间点以后部分且保留中间点
s2=mid2；//舍弃B中间点以前部分且保留中间点
}
}
}
return （A[s1]<B[s2] ? A[s1]:B[s2]）;
}
(3)上述所给算法的时间、空间复杂度分别是O(log2n)和O(1)。（2分）
因为每次总的元素个数变为原来的一半，所以有：
第一次：元素个数为n/2=n/(21)
第二次：元素个数为n/4=n/(22)
……
……
第k次：元素个数为n/(2k)
最后元素个数为2
则有n/(2k)=2
解得k= log2n – 1
因此：时间复杂度为O(log2n)，而空间复杂度从上述程序中可看出为O(1)。
43．
【答案解析】此题考察的知识点是程序编译运行时各寄存器的运用与变化。
（1）寄存器R1存储的是134，转换成二进制为1000 0110B，即86H。寄存器R5存储的是x－y的内容，x－y=-112，转换成二进制为1001 0000B，即90H。寄存器R6存储的是x+y的内容，x+y=380，转换成二进制为1 0111 1100B（前面的进位舍弃），即7CH。由于计算机字长为8位，所以无符号整数能表示的范围为0~255。而x+y=380，故溢出。
（2）m二进制表示为1000 0110B，由于m是int型，所以最高位为符号位，所以可以得出m的原码为：1111 1010（对1000 0110除符号位取反加1），即-122。同理n的二进制表示为1111 0110B，故n的原码为：1000 1010，转成十进制为-10。所以k1=-122-（-10）=-112.
（3）可以利用同一个加法器及辅助电路实现。因为无符号整数都是以补码形式存储，所以运算规则都是一样的。但是有一点需要考虑，由于无符号整数和有符号整数的表示范围是不一样的，所以需要设置不一样的溢出电路。
（4）带符号整数只有k2会发生溢出。分析：8位带符号整数的补码取值范围为：-128~+127，而k2=m+n=-122-10=-132，超出范围，而k=-112，在范围-128~+127之内。三种方法可以判断溢出：双符号位、最高位进位、符号相同操作数的运算后与原码操作数的符号不同则溢出。
44．
【答案解析】此题考察的知识点是计算机的地址管理。
（1）由于虚拟地址空间大小为16MB，且按字节编址，所以虚拟地址共有24位（224=16M）。由于页面大小为4KB（212=4K），所以虚页号为前12位。由于主存（物理）地址空间大小为1MB，所以物理地址共有20位（220=1M）。由于页内地址12位，所以20-12=8，即前8位为页框号。
（2）由于Cache采用直接映射方式，所以物理地址应划分成3个字段，如下：
12位 3位 5位
分析：由于块大小为32B，所以字块内地址占5位。Cache共8行，故字块标记占3位，所以主存字块标记占20-5-3=12位。
（3）虚拟地址001C60H的虚页号为前12位，即001H=1。查表可知，其有效位为1，故在内存中。虚页号为1对应页框号为04H，故物理地址为04C60H。由于采用的是直接映射方式，所以对应Cache行号为4。尽管有效位为1，但是由于标记位04CH≠064H，故不命中。
（4）由于采用了4路组相联的，所以Cache被分为2组，每组4行。所以物理地址应划分成3个字段，如下：
11位 1位 12位
将024BACH转成二进制为：0000 0010 010 0 1011 1010 1100，可以看出组号为0，标记为0000 0010 010，换成十六进制为0000 0001 0010（高位补一个0），即012H，从图44-c中的0组可以看出，标记为012H页面的页框号为1F，故虚拟地址024BACH所在的页面在主存中。
45.
【答案解析】此题考察的知识点是共享资源的使用与 P、V操作以防止死锁。
Semaphore seets =10;//表示空余座位数量的资源信号量，初值为10
Semaphore mutex = 1; //管理取号机的互斥信号量，初值为1，表示取号机空闲
Semaphore custom = 0; //表示顾客数量的资源信号量，初值为0
Process 顾客
{
P(seets); //找个空座位
P(mutex); //在看看取号机是否空闲
从取号机取号；
V(mutex) //放开那个取号机
V(custom); //取到号，告诉营业员有顾客
等待叫号；
V(seets) //被叫号，离开座位
接受服务；
}
Process 营业员
{
While(true)
{
P(custom); //看看有没有等待的顾客
叫号；
为顾客服务；
}
}
46.
【答案解析】此题考察的知识点是文件系统中数据的组织方式，及文件的查找。
（1）连续更合适。因为一次写入不存在插入问题，而且写入文件之后不需要修改，连续的数据块组织方式很适合一次性写入磁盘不再修改的情况，同时连续存储相对链式和索引省去了指针的空间开销，支持随机查找，查找速度最快。
（2）FCB集中存储较好。FCB存储有文件的很多重要信息，同时是文件目录的重要组成部分，在检索时，通常会访问对应文件的FCB。如果将FCB集中存储，则可以减少在检索过程中产生的访盘次数，提高检索速度。
(责任编辑：考研秘籍网) | 
您现在的位置： 