Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — FAURGS 2018

Algoritmos e Estrutura de DadosAlgoritmos
Código
qq337151
Banca
FAURGS
Órgão
UFRGS
Ano
2018
Nível
Médio
Cargo
Técnico de Tecnologia da Informação - Sistema da Informação
Pesquisa Binária e Hash Code são duas técnicas de busca de dados em um arquivo ou tabela muito usados em informática, com grande vantagem sobre a Pesquisa Sequencial. Sobre essas técnicas, assinale a afirmação INCORRETA.
  1. ANa Pesquisa Binária, os dados devem estar classificados pelo campo que é a chave de busca.
  2. BNa Pesquisa Binária, o número mínimo de tentativas para localizar um registro é 1, e o máximo é log₂ n (arredondado para cima), no qual n é o tamanho do arquivo ou tabela.
  3. CNa técnica Hash Code, o número de tentativas para localizar um registro quando o arquivo é grande não aumenta significativamente, tal como acontece na Pesquisa Sequencial.
  4. DNa técnica Hash Code, o número máximo de tentativas para localizar um registro depende do método empregado e do índice de ocupação do arquivo ou tabela em relação ao tamanho máximo estimado.
  5. ENa técnica Hash Code, os dados devem estar classificados pelo campo que é a chave de busca.
Revelar gabarito e comentário

GabaritoE — Na técnica Hash Code, os dados devem estar classificados pelo campo que é a chave de busca.

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”.

Pesquisa Binária e Hash Code

Gabarito: letra E. A afirmação incorreta é a que diz que os dados devem estar classificados pela chave de busca na técnica Hash. A pesquisa binária exige ordenação, mas hashing não — utiliza uma função hash para calcular o índice diretamente, sem necessidade de ordenação prévia.

Técnicas de busca
  • 1Pesquisa Binária
    • Dados ordenados pela chave
    • Tentativas: 1 a log₂(n)
    • Descarta metade a cada iteração
  • 2Hash Code
    • Função hash → índice direto
    • Não exige ordenação
    • Tempo O(1) em média
    • Colisões: método + fator de carga
LEVEL · soulevel.com.br

Alternativa A — ✅ Correta

A pesquisa binária realmente requer que os dados estejam ordenados pela chave de busca, pois o algoritmo compara o alvo com o elemento do meio e descarta metade do conjunto a cada iteração.

Alternativa B — ✅ Correta

O número mínimo de tentativas é 1 (quando o alvo está no meio) e o máximo é o teto de log₂(n), já que a cada passo o intervalo de busca é dividido pela metade.

Alternativa C — ✅ Correta

Hash possui tempo de busca aproximadamente constante (O(1) em média) para arquivos grandes, diferentemente da pesquisa sequencial que cresce linearmente com o tamanho.

Alternativa D — ✅ Correta

O número máximo de tentativas no hash depende do método de tratamento de colisões (ex.: encadeamento, endereçamento aberto) e do fator de carga (índice de ocupação).

Alternativa E — ❌ Incorreta ⟵ GABARITO

Hashing não exige que os dados estejam classificados. A função hash mapeia a chave a um índice, e a busca é feita nesse índice independentemente de qualquer ordenação.

Gabarito: letra E — a única incorreta.

Link permanente: /questoes/qq337151