Questão comentada de Algoritmos e Estrutura de Dados

Gabarito: B

Numa lista encadeada circular, mesmo que os elementos estejam ordenados pela chave, voce ainda nao ganha acesso direto ao elemento desejado. Isso porque a estrutura encadeada nao permite salto por indice, como acontece em vetores. Para procurar a chave, voce precisa ir seguindo ponteiro por ponteiro, verificando cada no ate encontrar a chave ou dar a volta completa na lista. Como a lista e circular, existe um detalhe importante: a busca termina quando voce retorna ao ponto de partida, ou antes, se achar a chave. No pior caso, a chave nao existe ou esta no ultimo no verificado. Aí nao tem milagre: voce percorre todos os N elementos. Por isso, a complexidade no pior caso e linear, isto e, O(N). A ordenacao ajuda mais na pratica do que na classe de complexidade. Ela pode permitir interromper a busca antes se voce passar da chave procurada, mas isso nao muda o pior caso. Em prova, sempre desconfie quando a banca mistura 'lista encadeada' com 'ordenada': isso quase nunca vira busca logaritmica, porque sem acesso aleatorio voce nao consegue fazer a estrategia de meio do caminho que aparece no vetor e na busca binaria. Portanto, o gabarito B esta correto porque a busca em lista encadeada circular ordenada continua exigindo, no pior caso, a verificacao sequencial de todos os elementos.