Questão de Algoritmos e Estrutura de Dados — Hashing — Instituto Consulplan 2024
Algoritmos e Estrutura de Dados›Hashing
Código
qg295925
Banca
Instituto Consulplan
Órgão
Prefeitura de Campos dos Goytacazes - RJ
Ano
2024
Nível
Superior
Cargo
Analista de Sistemas
Determinado profissional deseja criar um sistema para armazenar informações de contato com base no número de telefone. A chave seria o número de telefone e o valor o nome da pessoa. Ao tentar encontrar o nome de alguém, existe uma função que mapeia o número de telefone para a posição na tabela onde o nome está armazenado. Podemos afirmar que uma tabela hash (hash table) em estruturas de dados e algoritmos se trata de
Atécnica para armazenar valores únicos em uma lista.
Bestrutura de dados que organiza os dados em uma árvore binária.
Ctabela que permite a pesquisa de dados usando índices numéricos.
Destrutura de dados que armazena pares chave-valor e permite pesquisa eficiente com base na chave, empregando uma função de hash.
Revelar gabarito e comentário▾
GabaritoD — estrutura de dados que armazena pares chave-valor e permite pesquisa eficiente com base na chave, empregando uma função de 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 (Hashing)
Gabarito: letra D. A tabela hash é uma estrutura de dados que armazena pares chave-valor e permite pesquisa, inserção e remoção eficientes (tempo esperado O(1)) por meio de uma função de hash, que mapeia a chave para um índice na tabela. Essa definição corresponde exatamente à alternativa D.
A questão descreve um sistema onde o número de telefone é a chave e o nome é o valor, e uma função mapeia o telefone para a posição onde o nome está armazenado – ou seja, o uso clássico de uma tabela hash.
Tabela hash: Estrutura (Pares chave-valor, Função de hash (chave → índice)); Operações (O(1) esperado) (Inserção, Pesquisa, Remoção); Tratamento de colisões (Listas encadeadas, Endereçamento aberto); Não é (Lista de valores únicos, Árvore binária, Indexação numérica direta)
Alternativa A — ❌ Incorreta
Afirma que a tabela hash é uma técnica para armazenar valores únicos em uma lista. Embora conjuntos (sets) possam ser implementados com hash, a definição geral envolve pares chave-valor, e não apenas valores. Além disso, não é uma “lista”, mas uma estrutura com acesso direto por hash.
Alternativa B — ❌ Incorreta
Diz que a tabela hash organiza dados em uma árvore binária. Isso é característico de árvores de busca binária (BST) ou suas variações balanceadas (AVL, vermelho-preto), não de hash. Em hash não há ordenação ou hierarquia entre os elementos.
Alternativa C — ❌ Incorreta
Afirma que a tabela permite pesquisa usando índices numéricos. O acesso não é por índice da posição, mas sim por transformação da chave via função hash. A posição é calculada, não indexada diretamente. Além disso, a chave não precisa ser numérica.
Alternativa D — ✅ Correta ⟵ GABARITO
Define corretamente a tabela hash: armazena pares chave-valor e permite pesquisa eficiente com base na chave por meio de uma função de hash. Essa é a descrição padrão encontrada em livros como Cormen (Algoritmos: Teoria e Prática) e em qualquer material de ciência da computação.
Conceito central: A função de hash converte a chave em um índice da tabela, e colisões são tratadas (por exemplo, com listas encadeadas ou endereçamento aberto). Esse mecanismo garante operações em tempo constante na média.