47.（9分）某局域网采用CSMA/CD 协议实现介质访问控制，数据传输率为10Mbit/s，主机甲和主机乙之间的距离为 2km，信号传播速度是 200000km/s。请回答下列问题，要求说明理由或写出计算过程。
（1）若主机甲利和主机乙发送数据时发牛冲类，则从开始发送数据时亥走起， 冉全两台主材机均检测到冲突时刻为止，最短需经过多长时间?最长经过多长时间?（假设主机甲和主机乙发送数据过程中，其他主机不发送数据）
（2）若网脊不存在行何冲类与差错。干机甲总是标准的最长心大数据（1518B）向主村乙发送数据，主机乙每成功收到一个数据帧后立即向主机甲发送一个 64B 的确认帧， 主机甲收到确认帧后立即发送下一个数据帧。此时主机甲的有效数据传输速率是多少?（不考虑以太网帧的前导码）
41.（10 分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法∶
①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点;
② 选择离u最近且尚未在最短路径中的一个顶点v，加入最短路径中，修改当前顶点u=v;
③ 重复步骤②，直到u是目标顶点时为止。
请问上述方法能否求得最短路径?若该方法可行，请证明之;否则，请举例说明。
①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点;
② 选择离u最近且尚未在最短路径中的一个顶点v，加入最短路径中，修改当前顶点u=v;
③ 重复步骤②，直到u是目标顶点时为止。
请问上述方法能否求得最短路径?若该方法可行，请证明之;否则，请举例说明。
42. （5分）已知一个带有表头结点的单链表，结点结构为
Data/link
假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法;查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的 data 域的值，并返回1∶否则，只返回0。要求∶
1）描述算法的基本设计思想。
2）描述算法的详细实现步骤。
3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C、C++或 Java 语言实现），关键之处请给出简要注释。
Data/link
假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法;查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的 data 域的值，并返回1∶否则，只返回0。要求∶
1）描述算法的基本设计思想。
2）描述算法的详细实现步骤。
3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C、C++或 Java 语言实现），关键之处请给出简要注释。
43.（8分）某计算机的CPU主频为 500Mz，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 之间没有访存冲突）?
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），RO"的功能为（RO）+（R1））→（R1），即将R0中的数据与 R1的内容所指主存单元的数据相加，并将结果送入 R1的内容所指主存单元中保存。
下表给出了上述指令取指和译码阶段每个节拍（时钟周期）的功能和有效控制信号。请按表中描述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号。
时钟：功能/有效控制信号
C1：MAR←(PC)/PCout, MARin
C2：MDR←M(MDR) PC←(PC)+1/MemR, MDRinE, PC+1
C3：IR←(MDR)/MDRout, IRin
C4：指令译码/无
下表给出了上述指令取指和译码阶段每个节拍（时钟周期）的功能和有效控制信号。请按表中描述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号。
时钟：功能/有效控制信号
C1：MAR←(PC)/PCout, MARin
C2：MDR←M(MDR) PC←(PC)+1/MemR, MDRinE, PC+1
C3：IR←(MDR)/MDRout, IRin
C4：指令译码/无
45.（7分）三个进程P1、P2、P3互斥使用一个包含N（N>0）个单元的缓冲区。
P1每次用 produce（）生成一个正整数并用 putO）送入缓冲区某一空单元中;P2每次用 getodd（）从该缓冲区中取出一个奇数并用countodd（）统计奇数个数;P3每次用 geteven（）从该缓冲区中取出一个偶数并用 counteven（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义（要求用伪代码描述）。
P1每次用 produce（）生成一个正整数并用 putO）送入缓冲区某一空单元中;P2每次用 getodd（）从该缓冲区中取出一个奇数并用countodd（）统计奇数个数;P3每次用 geteven（）从该缓冲区中取出一个偶数并用 counteven（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义（要求用伪代码描述）。
