复习知识点

链表

判断两个单链表是否相交的最优操作通常涉及以下几个步骤：

获取链表长度：
首先，遍历两个链表以确定它们的长度。
如果两个链表长度不同，将较短的链表的头指针移动到较长链表的尾部开始的位置，直到两个链表剩余的长度相等。对齐长度。

从对齐后的起始点开始，同时遍历两个链表的剩余部分。如果在某个节点处两个链表相遇，那么这两个链表相交；如果遍历完整个长度都没有相遇，那么链表不相交。同时遍历。

这种方法的时间复杂度是 O(n + m)，其中 n 和 m 分别是两个链表的长度。这是因为你需要遍历每个链表一次来确定它们的长度，然后根据需要对齐它们，最后再次遍历剩余部分。

题目

选自牛客网
判断两个单链表是否相交的最优操作是（）
A。遍历第一个链表的每个结点，依次与第二个链表的每个结点比较，如果存在相同的结点，则两个链表相交

B.遍历第一个链表，将每个结点的指针保存到一个哈希表中，然后遍历第二个链表，检查每个结点是否在哈希表中，如果存在，则两个链表相交

C.遍历第一个链表，将最后一个结点的指针指向第二个链表的头节点，然后判断第二个链表是否存在环，如果存在环，则两个链表相交

D.遍历第一个链表，将最后一个结点的指针指向第二个链表的头节点，然后判断第一个链表是否存在环，如果存在环，则两个链表相交
正确答案：B

---

算法

概念

短作业优先算法（Shortest Job First，SJF）是一种用于作业调度的算法，其核心思想是优先执行预计执行时间（或长度）最短的作业。这种算法试图减少作业的平均等待时间，从而提高系统的整体效率。SJF算法有两种变体：

非抢占式SJF：一旦一个作业开始执行，它将一直运行直到完成，即使有更短的作业到达。
抢占式SJF：如果有一个新的作业到达，并且它的执行时间比当前正在执行的作业短，当前作业将被抢占，新作业将开始执行。

题目

在一个单道系统中，有4个作业P、Q、R和S，执行时间分别为2小时、4小时、6小时和8小时，P和Q同时在0时到达，R和S在2小时到达，采用短作业优先算法时，平均周转时间为（）。
A.15小时
B.12小时
C.6小时
D.9小时
正确答案：D
分析

根据你提供的步骤和计算，我们可以分析并验证短作业优先算法（SJF）下的平均周转时间。

首先，作业P和Q在0时刻到达，由于P的执行时间最短（2小时），它被优先执行。

1. **作业P**：- 到达时间：0- 开始时间：0- 完成时间：2- 周转时间：( 2 - 0 = 2 )小时在2时刻，P完成执行，此时作业R和S到达，同时Q仍在队列中等待。2. **作业Q**：- 到达时间：0- 开始时间：2（P完成后）- 完成时间：6- 周转时间：( 6 - 0 = 6 )小时在6时刻，Q完成执行，此时选择执行R和S中的较短作业。由于R的执行时间较短（6小时），R被优先执行。3. **作业R**：- 到达时间：2- 开始时间：6（Q完成后）- 完成时间：12- 周转时间：( 12 - 2 = 10 )小时在12时刻，R完成执行，此时只剩下S需要执行。4. **作业S**：- 到达时间：2- 开始时间：12（R完成后）- 完成时间：20- 周转时间：( 20 - 2 = 18 )小时现在，我们可以计算所有作业的平均周转时间：{平均周转时间} = {(2 + 6 + 10 + 18)}{4} = {36}/{4} = 9 {小时}所以，根据你提供的步骤和计算，平均周转时间确实是9小时，正确答案是 D：9小时。

36/4=9