给定一个非空线性表 L,其数据元素为整数。若 L 为单链表 a1→a2→...→an→∅,现欲删除链表中所有值大于等于 m 且小于等于 n 的节点(m < n),则最坏情况下需要遍历多少次链表?

答案解析

核心考点说明:本题考察线性表(单链表)的基本操作:删除节点,以及对最坏情况时间复杂度的理解。线性表删除操作的时间复杂度主要取决于查找待删除元素所需的时间。 解题思路分析:为了删除满足条件的节点,必须遍历整个链表,检查每个节点的值是否在[m, n]区间内。即使所有节点都不满足删除条件,也必须遍历整个链表以确认。 因此,最坏情况下,需要遍历整个链表。 每个选项的详细分析: A. 0次:错误。必须遍历链表才能确定哪些节点需要删除,或者确认没有节点需要删除。 B. 1次:正确。由于是单链表,无论是否进行删除,需要从头到尾遍历一次即可完成删除操作或者确认没有节点需要删除。因此一次遍历即可。 C. n 次:错误。 这里的n指的是链表节点的个数,不是删除操作的遍历次数,只是描述了最坏情况时遍历的次数。但遍历次数是1次。 D. 无法确定,因为可能需要遍历多次:错误。单链表只需要遍历一次即可完成删除操作或者确定没有节点需要删除。 易错点提醒: 考生可能误认为删除过程需要多次遍历,但实际上单链表的删除操作可以在一次遍历中完成。重点是理解最坏情况下的遍历次数,以及单链表遍历的特点。 关键依据:单链表只需遍历一次,即可完成删除操作或判断无需删除。
正确答案:B
随机推荐
开始刷题