Questão nº 41
Questão de Estrutura de Dados · FGV TJRN Analista TI 2023 (nº 41)
FGV2023Comum TIEstrutura de Dados
Gabarito: Bver comentário ↓
Numa busca por uma chave armazenada numa lista encadeada circular, cujos elementos estão dispostos ordenadamente pelo valor da chave, a complexidade do algoritmo no pior caso é:
- A1;
- BN; (alternativa correta)
- Clog N;
- DN log N;
- EN².
Resposta comentada
Gabarito Alternativa B
- (A) Incorreta: O(1) exigiria acesso direto, impossível numa lista encadeada, que só permite percurso sequencial.
- (B) Correta: mesmo ordenada, a lista encadeada não oferece acesso aleatório, exigindo percorrer sequencialmente os nós; no pior caso, todos são visitados, resultando em O(N).
- (C) Incorreta: O(log N) seria a busca binária, que requer acesso indexado, indisponível em lista encadeada.
- (D) Incorreta: O(N log N) é típico de ordenações eficientes, não de uma busca linear.
- (E) Incorreta: O(N²) corresponde a algoritmos com laços aninhados, não a esta busca simples.
Fonte: FGV TJRN Analista TI 2023 Conhecimentos Comuns (TI) (Caderno Tipo 1). Reproduzida para fins de estudo.