当前位置: 首页> 娱乐> 明星 > 复习知识点

复习知识点

时间:2025/7/11 8:43:02来源:https://blog.csdn.net/m0_67187271/article/details/140400636 浏览次数:0次

目录

  • 链表
    • 判断两个单链表是否相交的最优操作通常涉及以下几个步骤:
    • 题目
  • 算法
    • 概念
    • 题目

链表

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

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

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

这种方法的时间复杂度是 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完成执行,此时作业RS到达,同时Q仍在队列中等待。2. **作业Q**- 到达时间:0- 开始时间:2P完成后)- 完成时间:6- 周转时间:( 6 - 0 = 6 )小时在6时刻,Q完成执行,此时选择执行RS中的较短作业。由于R的执行时间较短(6小时),R被优先执行。3. **作业R**- 到达时间:2- 开始时间:6Q完成后)- 完成时间:12- 周转时间:( 12 - 2 = 10 )小时在12时刻,R完成执行,此时只剩下S需要执行。4. **作业S**- 到达时间:2- 开始时间:12R完成后)- 完成时间:20- 周转时间:( 20 - 2 = 18 )小时现在,我们可以计算所有作业的平均周转时间:{平均周转时间} = {(2 + 6 + 10 + 18)}{4} = {36}/{4} = 9 {小时}所以,根据你提供的步骤和计算,平均周转时间确实是9小时,正确答案是 D9小时。

在这里插入图片描述
36/4=9

关键字:复习知识点

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: