优先权调度,采用单链表保存进程就绪队列,高优先级进程在队头。就绪队列长度为 n,则插入进程、选出进程的时间复杂度()
A.O(1) O(1)
B.O(1) O(n)
C.O(n) O(1)
D.O(n) O(n)
在优先权调度算法中,若使用单链表保...
用户登录可进行刷题及查看答案
在优先权调度算法中,若使用单链表保存进程就绪队列且高优先级进程位于队头,分析插入进程和选出进程的时间复杂度如下:
1. 插入进程的时间复杂度
目标:将新进程插入到链表中合适位置,确保队头始终为最高优先级进程。
过程:
单链表无法随机访问,需从头节点开始遍历链表,比较新进程与各节点的优先级,找到第一个优先级低于新进程的节点位置,或遍历至链表末尾(若新进程优先级最低)。
最坏情况:新进程优先级最低,需遍历整个链表(共 n 个节点),才能确定插入位置(链表尾部)。
结论:插入操作的时间复杂度为 O(n)。
2. 选出进程的时间复杂度
目标:选取当前就绪队列中的最高优先级进程(即队头节点)。
由于高优先级进程已在队头,只需直接取出头节点即可,无需遍历或比较。
结论:选出操作的时间复杂度为 O(1)。
最终答案
插入进程的时间复杂度为 O(n),选出进程的时间复杂度为 O(1),对应选项 C。
登录后提交答案
暂无评论,来抢沙发