41.（10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：  　　

①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；  　　

②选择离u最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v；  　　

③重复步骤②，直到u是目标顶点时为止。  　　

请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。  　　

             　　

 42.（15分）已知一个带有表头结点的单链表，结点结构为  　　

data 　　

　　

　 　

假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0。要求：  　　

（1） 描述算法的基本设计思想  　　

（2） 描述算法的详细实现步骤  　　

（3） 根据设计思想和实现步骤，采用程序设计语言描述算法（使用c或c++或java语言实现），关键之处请给出简要注释。   　　

　 　

43.（8分）某计算机的cpu主频为500mhz，cpi为5（即执行每条指令平均需5个时钟周期）。假定某外设的数据传输率为0.5mb/s，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。  　　

（1）在中断方式下，cpu用于该外设i/o的时间占整个cpu时间的百分比是多少？  　　

（2）当该外设的数据传输率达到5mb/s时，改用dma方式传送数据。假设每次dma传送大小为5000b，　　

且dma预处理和后处理的总开销为500个时钟周期，则cpu用于该外设i/o的时间占整个cpu时间的百分比是多少？（假设dma与cpu之间没有访存冲突）  　　

　 　

  44.（13分）某计算机字长16位，采用16位定长指令字结构，部分数据通路结构如图所示。图中所有控制信号为1时表示有效、为0时表示无效。例如控制信号mdrine为1表示允许数据从db打入mdr，mdrin为1表示允许数据从内总线打入mdr。假设mar的输出一直处于使能状态。加法指令“add（r1），r0”的功能为（r0）+（（r1））→（r1），即将r0中的数据与r1的内容所指主存单元的数据相加，并将结果送入r1的内容所指主存单元中保存。