选择海文选择成功
2010年计算机研究生全国统一考试冲刺模拟题（一）答案
一、BBBDC,ABBCD,AACCB,DBCCB,DCDDB,ADACA,ABBBB,AABDA 二、（1） 散列地址 关键字 0 1 4 2 3 12 4 49 5 38 2 6 13 1 7 24 2 8 32 1 9 21 2 10 比较次数 1 1 1 ASLsucc =（1+1+1+2+1+2+1+2）/8=11/8 ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11
（2）ASLsucc =11/8 ASLunsucc=19/11
值得指出，对用拉链法求查找失败时的平均查找长度有两种观点。其一，认为比较到空指针算失败。以本题为例，哈希地址0、2、5、7、9和10均为比较1次失败，而哈希地址1和3比较2次失败，其余哈希地址均为比较3次失败，因此，查找失败时的平均查找长度为19/11，我们持这种观点。还有另一种理解，他们认为只有和关键字比较才计算比较次数，而和空指针比较不计算。照这种观点，本题的ASLunsucc=（1+1+2+2+2）/11=8/11
1. D_搜索类似BFS，只是用栈代替队列，入出队列改为入出栈。查某顶点的邻接点时，若其邻接点尚未
遍历，则遍历之，并将其压入栈中。当一个顶点的所有邻接点被搜索后，栈顶顶点是下一个搜索出发点。 void D_BFS(AdjList g ,vertype v0)
// 从v0顶点开始，对以邻接表为存储结构的图g进行D_搜索。 { int s[], top=0; //栈，栈中元素为顶点，仍假定顶点用编号表示。 for (i=1,i<=n;i++) visited[i]=0; //图有n个顶点，visited数组为全局变量。 for (i=1,i<=n;i++) //对n个顶点的图g进行D_搜索。 if (visited[i]==0)
{s[++top]=i; visited[i]=1; printf( \ while (top>0)
{i=s[top--]; //退栈
p=g[i].firstarc; //取第一个邻接点
while (p!=null) //处理顶点的所有邻接点
{j=p->adjvex;
if (visited[j]==0) //未访问的邻接点访问并入栈。
{visited[j]=1; printf( \ p=p->next; } //下一个邻接点
}//while(top>0)
} //if
http://www.vipkaoyan.com
16
海文专业课模拟试卷
}//D_BFS
2. 求信息码01101110的海明校验码。
分析1：
①确定海明校验位的位数。
设r为海明校验位的位数，则整个码字的位数应满足不等式：k+r ≤2-1
设r=3，则2-1=7，n=8+3=11,不等式不满足；设r=4，则2-1=15，n=8+4=12，不等式满足。所以r最小取4。
②确定校验位的位置。
位号（1～12）为2的权值的那些位，即：20，21，22，23的位置作为校验位，记做P1、P2、P3、P4，余下的为有效信息位。即：
12 11 10 9
8
7 6
5 4 3
2 1
D7 D6 D5 D4 P4 D3 D2 D1 P3 D0 P2 P1
3
4
r
③分组：有4个校验位，将12位分成4组，第i组由校验位号之和等于i的那些校验位所校验，如下表所示，如：第11位D6由P1（位号为1）、P2（位号为2）、P4（位号为8）所校验，因为1+2+8=11。
4位校验位的分组
12 D7 0 第一 组（P1） 第二 组（P2） 第三√ 组（P3） 第四√ 组（P4） 11 D6 1 √ √ √ 10 D5 1 √ √ 9 D4 0 √ √ 8 P4 √ 7 D3 1 √ √ √ 6 D2 1 √ √ 5 D1 1 √ √ 4 P3 √ 3 D0 0 √ √ 2 P2 √ 1 P1 √ ④校验位的形成。
P1=第一组中的所有位(P1外)同=D6?D4?D3?D1?D0=1?0?1?1?0=1 P2=第一组中的所有位(P2外)同=D6?D5?D3?D2?D0=1?1?1?1?0=0 P3=第一组中的所有位(P3外)同=D7?D3?D2?D1=0?1?1?1=1 P4=第一组中的所有位(P4外)同=D7?D6?D5?D4=0?1?1?0=0 P5=D7?D6?D5?D4?D3?D2?D1?D0?P1?P2?P3?P4 =0?1?1?0?1?1?1?0?1?0?1?0=1
答案1：信息码01101110的海明校验码为：1011011110110。 校验原理
分析2：在接收端分别求G1、G2、G3、G4、G5。 G1=P1?D6?D4?D3?D1?D0 G2=P2?D6?D5?D3?D2?D0
信息咨询： 010-82487377 13701202290
17
为了能检测两个错误，增加一位校验位P5，放在最高位。
选择海文选择成功
G3=P3?D7?D3?D2?D1 G4=P4?D7?D6?D5?D4
G5=P5?D7?D6?D5?D4?D3?D2?D1?D0?P1?P2?P3?P4
当G5=1时有一位数，由G4G3G2G1的二进制编码指出出错位号。例如G4G3G2G1=1001说明第9位出当G5=0时无错或有偶数个错（两个错的可能性比较大）；当G4G3G2G1=0000时，接收的数无错，否
错，将其取反，即可纠错。
则有两个错。 答案：能找出两个错误并能纠正一位出错位的海明校验逻辑电路如下图所示
3. 页式虚拟存储器把虚拟存储空间（逻辑空间）和主存空间（物理空间）等分成固定大小的页面，虚存
和实存间交换数据是以页面为单位进行的，每个虚拟页面可以装入主存中任一个物理页面。如果页面
大小为4KB，则页内地址共12位，虚拟空间的虚拟地址，去掉页内地址，就是页面地址，简称页号，即虚拟地址（逻辑地址）的高位地址。
给定一个虚拟地址（逻辑地址），从虚拟存储器中取出该单元的数据的过程是：首先必须查页表，进行虚实地址转换。页表中存放着各逻辑页面调入主页时的对应物理页号，如果所读逻辑页面已调入主存，可按页表给出该逻辑页面装入主存的物理页号作为访问主存的高位地址，再把逻辑地址的页内地址作为物理页面的页内地址（被访问主存单元的低位地址），二者合起来构成主存的物理地址。如果虚拟访问的页面还为调入主存，则必须先将磁盘中该页调入主存一个空闲页面中，并在页表中填入有关物理页号。然后根据主存地址访问主存单元，即可达到访问对应虚拟地址对应单元的目的。 4. (1):17次
(2):17次 (3)11次
5. 为解决并行所带来的死锁问题，在wait操作中引入AND条件，其基本思想是将进程在整个运行过程
中所需要的所有临界资源，一次性地全部分配给进程，用完后一次性释放.解决生产者－消费者问题可
描述如下:
var mutex,empty,full: semaphore:=1,n,0; buffer: array[0,...,n-1] of item; in,out: integer:=0,0; begin
parbegin
producer: begin
http://www.vipkaoyan.com
18
海文专业课模拟试卷
repeat . .
produce an item in nextp; .
.
wait(empty);
wait(s1,s2,s3,...,sn); //s1,s2,...,sn为执行生产者进程除empty外其余的条件 wait(mutex); buffer(in):=nextp; in:=(in+1) mod n; signal(mutex); signal(full);
signal(s1,s2,s3,...,sn); until false; end
consumer: begin repeat
wait(full);
wait(k1,k2,k3,...,kn); //k1,k2,...,kn为执行消费者进程除full外其余的条件 wait(mutex);
nextc:=buffer(out); out:=(out+1) mod n; signal(mutex); signal(empty);
signal(k1,k2,k3,...,kn); consume the item in nextc; until false; end parend end
6. 已知数据帧的长度为1kb，卫星通信信道的数据传输速率为50kb/s,因此发送一帧的时间 为1/50=0.02(s)。另外，卫星信道的单向传播延时为270ms=0.27s。
（1）在停止等待协议中，发送方首先用0.02s发送一个帧，然后等待确认。该帧经过0.27s后到达接收方，接收方立即用0.02s发送一个数据帧，其中捎带了对所接受的帧的确认，该数据帧经过另外0.27s之后到达发送方。于是，发送周期为(0.02+0.27+0.02+0.27)=0.58(s)。其中用于发送数据的时间为0.02s。因此，可以取得的信道最大利用率=0.02/0.58，约为3.4％。
（2）在后退N滑动窗口协议中，由于帧序号的长度为3比特，发送窗口大小的最大值=23-1=7，也就是在一个发送周期内发送方可以连续发送7帧。后退N协议的发送周期与停止等待协议的发送周期相同，也为0.58s。因此，可以取得的信道最大利用率=7×0.02/0.58,约为24.1％。
（3）在选择重发滑动窗口协议中，由于帧序号的长度为3比特，发送窗口大小的最大值=23-1=4，也就是在一个发送周期内发送方可以连续发送4帧。选择重发协议的发送周期与停止等待协议的发送周期相同，也为0.58s。因此可以取得的信道最大利用率=4×0.02/0.58，约为13.8％。
信息咨询： 010-82487377 13701202290
19
选择海文选择成功
2010年计算机研究生全国统一考试冲刺模拟题（二）答案
7. 上三角矩阵第一行有n个元素，第i-1行有n-（i-1）+1个元素，第一行到第i-1行是等腰梯形，而第
i行上第j个元素（即aij）是第i行上第j-i+1个元素，故元素Aij在一维数组中的存储位置（下标k）
为：
k=(n+(n-(i-1)+1))(i-1)/2+(j-i+1)=(2n-i+2)(i-1)/2+j-i+1
2
进一步整理可得k=（n+1/2）i-i/2+j-n，
则得f1（i）=（n+1/2）i-i2/2，f2（j）=j，c=-n。 8. （1）递归算法
void DecPrint(BSTree t）
//递减序输出二叉排序树t中所有左子树为空右子树非空的结点数据域的值。 { if（t）
{DecPrint(t->rchild)；
if（!t->lchild && t->rchild）printf(t->data：4） DecPrint(t->lchild）； }
}//DecPrint
（2）非递归算法 void DecPrint(BSTree t）
// 递减序输出二叉排序树t中所有左子女为空右子女非空的结点的值 { BSTree S[]；//S是二叉排序树结点指针的栈，容量足够大 int top=0； while（t || top>0）
{while（t）
{S[++top]=t；t=t->rchild ；} //沿右分枝向下 if（top>0） {t=S[top--]；
if（!t->lchild && t->rchild）printf(t->data：4)； t=t->lchild； // 去左分枝 }//if
}//while }//算法结束
9. 16K?1位的芯片有14条地址线，行地址线、列地址线各7条，行数和列数各等于27=128
条。用它来构成32K?8的存储器需要32/16?8=16片。一个刷新周期执行的刷新操作数等于行数（128），所占用的时间=128?50ns=6400ns=6.4 ?s.两次刷新之间的时间间隔=1ms/128=7.8 ?s（分布式刷新，相邻两行的刷新时间间隔）。
10. （1）当使用正常的中断屏蔽码时，处理机响应各中断源的中断请求的先后次序是根据
优先级从高到低的级别排列的，分别是1级、2级、3级4级和5级。实际处理的顺序也是这个顺序。
（2）当使用改编后的屏蔽码时，处理机响应各中断源的中断请求的先后依序依然是1级、2级、3级、4级和5级。但是由于中断屏蔽寄存器的设置，故改变了中断处理的顺序，变成4级、5级、3级、2级和1级。
http://www.vipkaoyan.com
20