目录
- 链表
- 判断两个单链表是否相交的最优操作通常涉及以下几个步骤:
- 题目
- 算法
- 概念
- 题目
链表
判断两个单链表是否相交的最优操作通常涉及以下几个步骤:
获取链表长度:
首先,遍历两个链表以确定它们的长度。
如果两个链表长度不同,将较短的链表的头指针移动到较长链表的尾部开始的位置,直到两个链表剩余的长度相等。对齐长度。
从对齐后的起始点开始,同时遍历两个链表的剩余部分。如果在某个节点处两个链表相遇,那么这两个链表相交;如果遍历完整个长度都没有相遇,那么链表不相交。同时遍历。
这种方法的时间复杂度是 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