题目

在优先权调度中，采用单链表保存进程就绪队列，高优先级进程在队头。若就绪队列长度为 n，则插入进程、选出进程的时间复杂度为（ ）。

错因

A

把"链表插入是 "的口诀套用过来——但那个口诀的前提是已知插入位置的前驱节点。这道题"按优先级有序插入"必须先扫描链表找到第一个比新进程优先级低的节点，扫描本身就是 。链表插入的"动作"虽然是 ，但"找位置"的代价不能忽略。

B

把"插入"和"选出"的复杂度对换了。可能心里想的是某种反向有序链表（低优先级在头）：选出最高优先级要遍历到尾才能找到——但题目明确说"高优先级进程在队头"，所以选出就是直接取队头，肯定 ，不是 。两个数都对反了。

D

把"链表查找永远 "机械地套到两端。选出进程的"取队头"操作根本不需要查找——队头指针直接给到，是 。把"链表"和""做了过度等价，没区分"哪个端在做什么"。

总解析

有序链表的两种基本操作复杂度：

操作	是否需要扫描	复杂度
在链表头插入 / 队头取出	否（指针直接命中）
在链表中按某种顺序找位置	是（最坏扫到尾）

逐项分析：

• 插入新进程：题目要求按优先级保持有序，新进程的优先级可能落在链表中任意位置——必须从头遍历，找到第一个优先级比它低的节点，再插到该节点之前。最坏情况扫到尾，复杂度 。

• 选出进程：调度选最高优先级的——既然规定了"高优先级在队头"，那就是直接摘队头，单链表只要把头指针后移一格即可，复杂度 。

为什么不是堆？ 优先队列的工业实现常用二叉堆（插入和选出都是 ），但题目限定了"单链表"这个数据结构，问的是有序链表下的复杂度，不是最优实现。

复杂度速记表：

数据结构	插入有序	取最大值
有序单链表（高优先级在头）
无序单链表	（头插）	（扫一遍）
二叉堆		（弹出+下滤）

最终答案是 C（O(n), O(1)）。