题目
以下存储结构中,不适用于折半查找的是(I有序链表[1]II无序数组III有序静态链表IV无序静态链表)A. 仅I和IIIB. 仅II和IVC. 仅II III IVD. I II III IV
以下存储结构中,不适用于折半查找的是(I有序链表[1]II无序数组III有序静态链表IV无序静态链表)
A. 仅I和III
B. 仅II和IV
C. 仅II III IV
D. I II III IV
题目解答
答案
D. I II III IV
解析
折半查找(二分查找)的核心条件是数据必须有序且支持随机访问(即能直接通过索引找到中间元素)。
- 有序链表虽然有序,但无法快速定位中间节点(需遍历),导致效率低下。
- 无序结构(数组或静态链表)直接不满足有序性。
- 静态链表即使有序,存储空间不连续,无法通过索引直接访问中间元素。
因此,所有选项均不满足折半查找的条件。
I. 有序链表
- 有序性:满足。
- 随机访问:不满足。链表只能通过指针逐个节点遍历,无法直接跳转到中间节点,导致每次查找中间元素的时间复杂度为 $O(n)$,整体时间复杂度退化为 $O(n \log n)$。
II. 无序数组
- 有序性:不满足。折半查找依赖有序性,无法进行。
III. 有序静态链表
- 有序性:满足。
- 随机访问:不满足。静态链表存储在数组中,但通过指针连接,中间元素的位置需遍历指针链,无法直接计算得到。
IV. 无序静态链表
- 有序性:不满足。
- 随机访问:不满足。
结论:所有选项均不适用折半查找。