2009年统考计算机考研真题及答案解析三
一． 选择题12345678910
BCDBCBADAB
111213 14 15 16 17 18 19 20
CDDCDCAADB
212223 24 25 26 27 28 29 30
DADDCACBAA
313233 34 35 36 37 38 39 40
BABBCADDCA
二． 综合应用题
41.该方法求得的路径不一定是最短路径。例如，对于下图所示的带权图，如果按照题中的原则，
从A到C的最短路径为A→B→C，事实上其最短路径为A→D→C。
42. （1）算法基本思想如下：从头至尾遍历单链表，并用指针P指向当前节点的前K个节点。当遍历
到链表的最后一个节点时，指针P所指向的节点即为所查找的节点。
（2）详细实现步骤：增加两个指针变量和一个整型变量，从链表头向后遍历，其中指针P1指向当
前遍历的节点，指针P指向P1所指向节点的前K个节点，如果P1之前没有K个节点，那么P指向表头
节点。用整型变量i表示当前遍历了多少节点，当i>k时，指针p随着每次遍历，也向前移动一个节
点。当遍历完成时，p或者指向表头就节点，或者指向链表中倒数第K个位置上的节点。
（3）算法描述：
Int LocateElement(linklist list,int k)
{ P1=list->link;
P=list;
i=1;
while(P1)
{ P1=P1->link;
i++;
if(i>k)p=p->next; //如果i>k,则p也往后移
}
if(p==list)return 0;//说明链表没有k个结点
else
{
printf(“%d\n“,p->data);
return 1;
}
}
43.（1）在中断方式下，每32位（4B）被中断一次，故每秒中断
0.5MB/4B=0.5×106/4=12.5×104次
要注意的是，这里是数据传输率，所以1MB=106B。因为中断服务程序包含18条指令，中断服务的
其他开销相当于2条指令的执行时间，且执行每条指令平均需5个时钟周期，所以，1秒内用于中断
的时钟周期数为
（18+2）×5×12.5×104=12.5×106
（2）在DMA方式下，每秒进行DMA操作
5MB/5000B=5×106/5000=1×103 次因为DMA预处理和后处理的总开销为500个时钟周期，所以1秒
钟之内用于DMA操作的时钟周期数为
500×1×103=5×105
故在DMA方式下，占整个CPU时间的百分比是
（（5×105）/（500×106））×100%=0.1%
44.指令执行阶段每个节拍的功能和有效控制信号如下所示
时钟 功能有效控制信号
C5MAR←(R1)PCout,MARin
C6MDR←M(MAR)MemR,MDRinE
C7A←(R0)R0out,Ain
C8AC←(MDR)+(A) MDRout,Addr,ACin
C9MDR←(AC)ACout,MDRin
C10M(MAR) ←MDR MDRoutE,MemW
45.定义信号量S1控制P1与P2之间的同步；S2控制P1与P3之间的同步；empty控制生产者与消费者
之间的同步；mutex控制进程间互斥使用缓冲区。程序如下：
Var s1=0,s2=0,empty=N,mutex=1;
Parbegin
P1:begin
X=produce();
P(empty);
P(mutex);
Put();
If x%2==0
V(s2);
else
V(s1);
V(mutex);
end.
P2:begin
P(s1);
P(mutex);
Getodd();
Countodd():=countodd()+1;
V(mutex);
V(empty);
end.
P3:begin
P(s2)
P(mutex);
Geteven();
Counteven():=counteven()+1;
V(mutex);
V(empty);
end.
Parend.
页:
[1]