有种数据结构叫跳跃列表(SkipList)，它是一种基于并联的链表的随机化数据结构，其效率可比拟于二叉查找树(

单项选择题

有种数据结构叫跳跃列表(SkipList)，它是一种基于并联的链表的随机化数据结构，其效率可比拟于二叉查找树(对于大于数操作需要O(logn)平均时间)。它是按层建造的。底层是一个普通的有序链表。每个更高层都充当下面列表的“快速跑道”，这里在层i中的元素按概率l/p出现在层i+1中。平均起来，每个元素都在p/(p-1)个列表中出现，而最高层的元素(通常是在跳跃列表前段的一个特殊的头元素)在O(logpn)个列表中出现。调节p的大小可以在内存消耗和时间消耗上进行折中。试分析在该数据结构中查找一个元素的平均时间复杂度。

A.O(logn)
B.O(n)
C.O(n*logn)
D.以上都不正确

计算机考试试题及答案解析