NOIP 普及 2011 第一轮 第 13 题：双向链表查找的最快时间复杂度

题目

在含有 $n$ 个元素的双向链表中查询是否存在关键字为 $k$ 的元素，最快情况下运行的时间复杂度是（    ）。

选项

• A. $O(1)$
• B. $O(\log n )$
• C. $O( n )$
• D. $O( n \log n )$

答案

C

题解

考点定位

本题考「链表查询复杂度」,对应大纲 3.2.3 链表（难度【1】）。

解题过程

链表无随机访问，最坏遍历全表：O(n)。

选 C。

易错提醒

① 「最快情况下」表述即最坏情形的快——链表查找线性；② 有序数组可二分 O(log n)，链表不行。