Questão FC374707
Durante a análise e o desenvolvimento de sistemas no Tribunal de Justiça do Estado de Rondônia (TJRO), é essencial garantir a eficiência das operações de armazenamento e recuperaçã
Algoritmos e Lógica de Programação
Instituto Consulplan · 2025
Durante a análise e o desenvolvimento de sistemas no Tribunal de Justiça do Estado de Rondônia (TJRO), é essencial garantir a eficiência das operações de armazenamento e recuperação de dados. Uma das formas de otimizar essas operações é por meio de algoritmos de ordenação e busca. O conhecimento sobre a complexidade de algoritmos e a escolha da estrutura de dados mais adequada para um determinado problema impacta diretamente no desempenho do sistema.
Sobre a complexidade dos algoritmos de ordenação, busca e respectivas estruturas de dados, assinale a afirmativa INCORRETA.
- O algoritmo QuickSort tem uma complexidade média de O(n log n).
- As tabelas hash oferecem uma busca com complexidade O(1) no pior caso.
- O algoritmo de ordenação Bubble Sort tem complexidade O(n2) no pior caso.
- A busca binária exige que o conjunto de dados esteja ordenado previamente.
- As listas encadeadas não permitem busca eficiente, pois exigem percorrimento sequencial.
Mostrar resposta e comentário
Gabarito
B
Comentário do professor
Incorreta. Uma tabela hash oferece busca de tempo constante apenas no caso médio/esperado, não no pior caso. O comportamento médio é \(O(1)\) quando as chaves se distribuem uniformemente entre os baldes.
O pior caso \(O(n)\) ocorre quando muitas chaves colidem e acabam no mesmo balde — por exemplo, todas as chaves mapeadas para uma única posição. Em encadeamento isso exige percorrer uma lista com até \(n\) elementos; em endereçamento aberto provoca longas sequências de sondagem, também linearizáveis.
Para garantir desempenho prático usa-se boa função hash, controle do fator de carga e redimensionamento/rehash, o que mantém o tempo esperado em \(O(1)\). Implementações avançadas (ex.: converter listas em árvores) mitigam o pior caso, reduzindo-o para \(O(\log n)\) em vez de \(O(n)\).
Conteúdo do catálogo FC Concursos · Atualizado em