2009年联考《408计算机学科专业基础综合》真题答案.pdf

计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解。请见：网学天地(www.e-);咨询QQ:2696670126移动到第k个结点时，q指针与p指针同步移动，当p指针移动到链表尾结点时，q指针所指元素即为倒数的第k个结点。以上过程对链表仅进行一遍扫描。(2)算法的详细实现步骤如下：(5分)置count=0,p和q指向链表表头结点的下一个结点。若p为空，则转向。若count等于k,则q指向下一个结点；否则，置count=-count+-1。置p指向下一个结点，转向。若cout等于k,则查找成功，输出该结点的data域的值，返回l;否则，查找失败，返回0。算法结束。(3)算法实现如下：（5分)天物typedef struct LNodeint data;struct LNode*link;)*LinkList;-LinkList p,qiint count=0;什教幕赋初值p=g=11st-1nk?地利和互指向链表表头结点的下二个结点while(p!-NULL)if(count11nk,1/g移到下一个结点p-p-link/P移到下个纬点if(countdata);7/输出第k个结点的值return(1);/查找成功【评分说明】若所给出的算法采用一遍扫描方式就能得到正确结果，可给满分15分；若采用两遍计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解。请见：网学天地(www.e-);咨询QQ:2696670126或者多遍扫描才能得到正确结果的，最高给10分：若采用递归算法得到正确结果的，最高给10分：若实现的算法空间复杂度过高（使用了大小与k有关的辅助数组），但结果正确，最高给10分。参考答案中只给出了C语言的版本，使用C+/小ava语言正确实现的算法同样给分。若在算法基本思想描述和算法步骤描述中因文字表达没有非常清晰地反映出算法的思路，但在算法实现中能够清晰地看出算法思想和步骤且正确，按照的标准给分。若考生的答案中算法基本思想描述、算法步骤描述或算法实现中部分正确，可酌情给分。43.【答案要点】(1)中断方式下，CPU每次用于数据传输的时钟周期数：518+52=100个时钟周期，为达到外设0.5MB/s的数据传输速率，外设每秒申请的中断次数：0.5MB/4B=125000,则1s内用于中断的开销：100125000=12500000=12.5M个时钟周期CPU用于外设IVO的时间占整个CPU时间的百分比为12.5MW500M100%f2,5%(2)外设数据传输率提高到5MB/s时，1s内需要产生的MA次数为5MB/5000B=1000JCPU用于DMA处理的总开销为05001000=500000-=0.5M个时钟周期。udysk的CPU用于外设IVO的时间占整个狱时间的首分围0500iM1002-0.1%【评分说明】如果考生只给出正确的计算结果，未给出计算过程，每个给2分。44.【答案要点】地参考答案一：时钟功能有效控制信号C5CR网RRlout,MARinC6M(MAR)MDR,(RO)-AMemR,MDRinE,ROout,AinC7(A)+(MDR)-ACMDRout,Add,ACinC8(AC)-MDRACout,MDRinC9(MDR)-M(MAR)MDRoutE,MemW“(RO)A”也可以在C7:“(A)HMDR)AC”之前的一个时钟周期执行。参考答案二：时钟功能有效控制信号C5RI)MARRlout,MARinC6M(MAR)-MDRMemR,MDRinEC7(MDR)-AMDRout,AinC8(A)+(R0)-ACROout,Add,ACinC9(AC)-MDRACout,MDRinc10(MDR)-M(MAR)MDRoutE,MemW