一个由高速缓冲存储器Cache与主存储器组成的二级存储系统。已知主存容量为1 MB，按字节编址，缓存容

设有一个由正整数组成的无序(后向)单链表，编写能够完成下列功能的算法：

(1)找出最小值结点，且打印该数值。

(2)若该数值为奇数，则将其与直接后继结点的数值交换。

(3)若该数值为偶数，则将其直接后继结点删除。

位为时间片，优先级以数值大者为优。

(1)请说明分别使用FCFS、RR(时间片=1)、SPF以及非抢夺式优先级调度算法时，这些进程的执行情况。

(2)争对上述每种调度算法，给出平均周转时间和平均带权周转时间。

顺序访问的地址为20124H、58100H、60140H和60138H等4个主存字节单元中的数。已知访问开始前第2组(组号为1)的地址阵列内容如下图所示，Cache采用LRU替换策略。

说明Cache的结构(即分多少组、组内分多少块)，给出主存及Cache的地址格式。上述4个数能否直接从Cache中读取，若能，请给出实际访问的Cache地址。第4个数访问结束时，上图的内容如何变化。

设备真正地并行。但是处理机的利用率提高并不是简单地将两个进程的处理机利用率相加，而是遵循一定的规律。现在有一个计算机系统采用多道程序技术实现了并发，调度算法采用时间片轮转，时间片很小可以不计进程并发时的次序。忽略计算机系统的开销，请计算并填写下表以及甘特图的空缺内容：

假设进程创建时间和完全占有CPU运行的确切时间如下表所示。已知其IO繁忙率为80％，处理机的利用率为20％。

请计算并填写下列空格(填百分率)和图表空格处(填时间)。

的算法，将L改造成L=(a1，a2，……，an，……a4，a2)。要求：

(1)给出算法的基本设计思想。

(2)根据设计思想，采用C或C十十或JAVA语言描述算法，关键之处给出注释。

(3)说明你所设计算法的时间复杂度和空间复杂度。

已知加权有向图G如下，回答下列问题：

(1)画出该有向图G的邻接矩阵；

(2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径，并给出求解过程。