2009年统考计算机考研真题及答案解析三

考研网

　　一． 选择题
　　1  2  3  4  5  6  7  8  9  10
　　B  C  D  B  C  B  A  D  A  B
　　11  12  13 14 15 16 17 18 19 20
　　C  D  D  C  D  C  A  A  D  B
　　21  22  23 24 25 26 27 28 29 30
　　D  A  D  D  C  A  C  B  A  A
　　31  32  33 34 35 36 37 38 39 40
　　B  A  B  B  C  A  D  D  C  A
　　二． 综合应用题
　　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个位置上的节点。

kyfive

　　（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.指令执行阶段每个节拍的功能和有效控制信号如下所示
　　时钟 功能  有效控制信号
　　C5  MAR←(R1)  PCout,MARin
　　C6  MDR←M(MAR)  MemR,MDRinE
　　C7  A←(R0)  R0out,Ain
　　C8  AC←(MDR)+(A) MDRout,Addr,ACin
　　C9  MDR←(AC)  ACout,MDRin
　　C10  M(MAR) ←MDR MDRoutE,MemW

kyfour

　　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.