得最短途径？若该办法可行，请证明之；否则，请举例阐明。 Р РРР42.（15分）已知一种带有表头结点单链表，结点构造为 Рdata Рlink РР假设该链表只给出了头指针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内容所指主存单元中保存。
全文预览
