Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FGV 2026
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
fg127329
Banca
FGV
Órgão
AL-RO
Ano
2026
Nível
Superior
Cargo
Analista Legislativo (Tecnologia da Informação - Análise e Desenvolvimento de Sistemas)
Em um sistema de apoio à tomada de decisão legislativa, é necessário armazenar uma lista de chaves de acesso de tamanho fixo. O requisito mais crítico do sistema é realizar buscas por chaves específicas no menor tempo possível (complexidade 0(1) em média), embora o consumo de memória não seja a principal preocupação.A estrutura de dados mais eficiente para atender ao requisito de busca com complexidade 0(1) em média para chaves, mesmo que envolva um trade-off no uso de memória, é
Aa Lista Encadeada.
Ba Árvore Binária de Busca Balanceada.
Co Array Estático.
Da Tabela Hash.
Eo Heap Binário.
Revelar gabarito e comentário▾
GabaritoD — a Tabela Hash.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Estrutura de dados para busca O(1) em média
Gabarito: letra D. A tabela hash (ou tabela de dispersão) é a estrutura que fornece complexidade de busca O(1) em média para chaves, utilizando uma função hash para mapear chaves a posições em um array, com trade-off de maior consumo de memória — exatamente o que o enunciado descreve.
A banca explora o conhecimento básico sobre complexidades de operações em estruturas de dados clássicas. O requisito crítico é busca por chave específica, não acesso por índice. Vejamos cada alternativa:
Busca por chave
1O(1) em média
Tabela Hash (D)
Função hash → índice
Trade-off: mais memória
2O(log n)
Árvore Binária Balanceada (B)
3O(n)
Lista Encadeada (A)
Array Estático (C) — busca por valor
Heap Binário (E)
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
A Lista Encadeada é uma estrutura linear com busca sequencial; no pior caso (e na média) a busca percorre toda a lista, resultando em complexidade O(n). Não atende ao requisito O(1).
Alternativa B — ❌ Incorreta
A Árvore Binária de Busca Balanceada (como AVL ou rubro-negra) garante busca em O(log n), que é eficiente, mas não constante O(1).
Alternativa C — ❌ Incorreta
O Array Estático permite acesso O(1) por índice, mas busca por valor/chave é O(n) (a menos que ordenado com busca binária O(log n)). O enunciado pede busca por chave, não por posição, portanto não atende.
NÃO CAIA NESSA!
Cuidado para não confundir acesso por índice (O(1) em array) com busca pelo valor (O(n)). O array estático só é O(1) quando você sabe a posição exata — o que não é o caso de uma busca por chave arbitrária.
Alternativa D — ✅ Correta ⟵ GABARITO
A Tabela Hash armazena pares chave-valor e, usando uma função de espalhamento (hash), mapeia cada chave a um índice do array subjacente. Em média, as operações de busca, inserção e remoção ocorrem em tempo O(1). O preço é o maior consumo de memória (para lidar com colisões e eventual fator de carga), mas isso é aceitável conforme o enunciado.
Alternativa E — ❌ Incorreta
O Heap Binário é uma árvore binária especializada em filas de prioridade (min-heap ou max-heap). A busca por um elemento específico não é sua operação principal; requer percurso que pode chegar a O(n).