单选题 适中
#21108

小杨采用如下双链表结构保存他喜欢的歌曲列表: struct dl_node { string song ; dl_node * next ; dl_node *…

小杨采用如下双链表结构保存他喜欢的歌曲列表:

struct dl_node {
	string song;
	dl_node* next;
	dl_node* prev;
};

小杨想在头指针为 head 的双链表中查找他喜欢的某首歌曲,采用如下查询函数,该操作的时间复杂度为( )。

dl_node* search(dl_node* head, string my_song) {
	dl_node* temp = head;
	while (temp != nullptr) {
		if (temp->song == my_song)
			return temp;
		temp = temp->next;
	}
	return nullptr;
}
未登录也能判分,登录后才会记录
答案与解析
正确答案:B
解析

该查询函数的时间复杂度为O(n),其中n是双链表中节点的数量。

函数使用一个指针temp从头指针head开始,沿着双链表向后遍历。

在每个节点处,它检查节点中的歌曲名称是否与目标歌曲my_song匹配。

最坏情况下,如果目标歌曲不在双链表中或者在最后一个节点才找到,那么需要遍历整个双链表,因此时间复杂度为O(n)

这是因为在最坏情况下,需要遍历所有n个节点才能确定目标歌曲是否存在。