47.（7分）某公司网络如题47图所示。IP地址空间192.168.1.0/24 被均分给销售部和技术部两个子网，并已分别为部分主机和路由器接口分配了IP 地址，销售部子网的 MTU=1500B，技术部子网的 MTU=800B。
请回答下列问题。
（1）销售部子网的广播地址是什么?技术部子网的子网地址是什么?若每个主机仅分配一个IP 地址，则技术部子网还可以连接多少台主机?
（2）假设主机192.168.1.1向主机192.168.1.208发送一个总长度为1500B的IP分组，IP分组的头部长度为20B，路由器在通过接口 F1转发该IP 分组时进行了分片。若分片时尽可能分为最大片，则一个最大IP 分片封装数据的字节数是多少?至少需要分为几个分片?每个分片的片偏移量是多少?
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（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义（要求用伪代码描述）。
