45.某请求分页系统的局部页面置换策略如下∶ 系统从0时刻开始扫描，每隔5个时间单位扫描一轮驻留集（扫描时间忽略不计），本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页链表中，那么重新放回进程的驻留集中;否则，从空闲页框链表头部取出一个页框。
假设不考虑其他进程的影响和系统开销。初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程P依次访问的<虚拟页号，访问时刻>是<1，1>，<3，2>，<0，4>，<0，6>，<1，11>，<0，13>，<2，14>。请回答下列问题。
1）访问<0，4>时，对应的页框号是什么?说明理由。
2）访问<1，11>时，对应的页框号是什么?说明理由。
3）访问<2，14>时，对应的页框号是什么?说明理由。
4）该策略是否适合于时间局部性好的程序?说明理由。
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（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义（要求用伪代码描述）。
