Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — IV - UFG 2024
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qg273536
Banca
IV - UFG
Órgão
UFG
Ano
2024
Nível
Médio
Cargo
IV - - Técnico de Tecnologia da Informação
Considere um cenário onde é necessário armazenar e acessar rapidamente dados não ordenados, mas que podem conter chaves duplicadas. Qual estrutura de dados é adequada para esse propósito, permitindo acesso eficiente e suporte a chaves duplicadas?
ALista ligada.
BÁrvore binária de busca.
CTabela hash.
DFila.
Revelar gabarito e comentário▾
GabaritoC — 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”.
Tabela Hash para dados não ordenados com chaves duplicadas
Gabarito: letra C. A tabela hash (hash table) é a estrutura de dados mais adequada para armazenar e acessar rapidamente dados não ordenados, mesmo com chaves duplicadas, pois oferece tempo de acesso médio O(1) por meio de uma função de espalhamento. Listas ligadas, árvores binárias de busca e filas não atendem simultaneamente aos requisitos de eficiência e suporte a chaves duplicadas.
A questão testa o conhecimento sobre as características fundamentais das estruturas de dados clássicas e sua adequação a cenários específicos. O ponto central é o equilíbrio entre velocidade de acesso (busca por chave) e a capacidade de lidar com chaves repetidas.
Estrutura
Acesso eficiente por chave
Suporte a chaves duplicadas
Dados não ordenados
Complexidade de busca
Lista ligada
❌ Não (busca sequencial)
✅ Sim
✅ Sim
O(n)
Árvore binária de busca
✅ Sim (O(log n))
❌ Não (padrão)
❌ Não (ordenada)
O(log n)
Tabela hash
✅ Sim (O(1) médio)
✅ Sim
✅ Sim
O(1) médio
Fila
❌ Não (FIFO)
✅ Sim
✅ Sim
O(n)
Alternativa A — ❌ Incorreta
A lista ligada permite armazenar dados duplicados, mas o acesso a um elemento exige percorrer a lista sequencialmente, com complexidade O(n) no pior caso. Não é eficiente para acesso rápido por chave quando o volume de dados é grande.
Alternativa B — ❌ Incorreta
A árvore binária de busca (ABB) padrão não aceita chaves duplicadas (cada chave é única). Mesmo com adaptações (como árvores que permitem repetições), a estrutura mantém os dados ordenados, o que não é necessário no cenário descrito. Além disso, o acesso é O(log n) em árvores balanceadas, ainda mais lento que a tabela hash para conjuntos grandes.
Alternativa C — ✅ Correta ⟵ GABARITO
A tabela hash (ou tabela de dispersão) armazena pares chave-valor e oferece acesso médio de tempo constante O(1) para inserção, busca e remoção. Ela suporta chaves duplicadas por meio de técnicas como encadeamento separado (listas ligadas em cada bucket) ou endereçamento aberto com sondagem. É a estrutura ideal para dados não ordenados que exigem acesso rápido, mesmo com chaves repetidas.
Alternativa D — ❌ Incorreta
Uma fila segue o princípio FIFO (first in, first out) e não permite acesso direto a um elemento por chave. Para encontrar um dado específico, seria necessário percorrer a fila inteira, resultando em O(n). Não atende ao requisito de acesso eficiente.
PEGA ESSA DICA!
Em questões sobre escolha de estrutura de dados, identifique primeiro as operações críticas (busca por chave, inserção, ordenação) e as restrições (duplicatas, ordem). Tabelas hash são campeãs em acesso rápido a dados não ordenados; árvores binárias são melhores quando a ordenação é necessária; listas e filas são adequadas para acesso sequencial.