Questão de Algoritmos e Estrutura de Dados — Algoritmos — INSTITUTO AOCP 2019
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq514142
Banca
INSTITUTO AOCP
Órgão
IBGE
Ano
2019
Nível
Superior
Cargo
Analista Censitário - Análise de Sistemas - Desenvolvimento de Aplicações Web Mobile
Formalmente, um algoritmo de busca é aquele que aceita um argumento e tenta encontrar o registro cuja chave seja igual ao argumento. Assim, analisando o seguinte passo a passo de um algoritmo de busca, é correto afirmar que se trata de um algoritmo1. Defina que min= 1 e max = n.2. Encontre a média de max e min, arredondando para baixo para que seja um inteiro.3. Se você tiver adivinhado o número certo. Pare – Fim algoritmo!4. Se o palpite foi muito baixo, defina o min como 1 a mais do que o palpite.5. Se o palpite foi muito alto, defina o max como 1 a menos do que o palpite.6. Volte ao passo dois.
Abusca sequencial.
Bbusca binária.
Cbusca por interpolação.
Dbusca em árvore.
Ehash.
Revelar gabarito e comentário▾
GabaritoB — busca binária.
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”.
Algoritmos de Busca
Gabarito: letra B. O algoritmo descrito é a busca binária, que a cada iteração reduz o intervalo de busca pela metade, calculando o ponto médio entre min e max e ajustando os limites conforme a comparação com a chave. Essa é a definição clássica do algoritmo.
A banca testa o reconhecimento dos principais algoritmos de busca. O passo a passo fornecido segue exatamente a lógica da busca binária: definir limites inferior e superior, calcular a média (piso), comparar e ajustar. Nenhum outro algoritmo listado possui essa estrutura.
Algoritmo
Característica principal
Estrutura de dados
Complexidade típica
Busca sequencial
Percorre elementos um a um do início ao fim
Lista/array não ordenado
O(n)
Busca binária
Divide intervalo ao meio a cada iteração, calcula ponto médio
Array ordenado
O(log n)
Busca por interpolação
Estima posição por interpolação linear baseada no valor da chave
Array ordenado
O(log log n) em média
Busca em árvore
Percorre nós comparando chave, decide ramo esquerdo/direito
Árvore binária de busca
O(log n) em árvore balanceada
Hash
Calcula índice diretamente por função de espalhamento
Tabela hash
O(1) em média
1min=1, max=n
2Média (piso)
3Acertou? Fim
4Palpite baixo? min=média+1
5Palpite alto? max=média-1
6Volta ao passo 2
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
A busca sequencial percorre os elementos um a um, do início ao fim, sem divisão do intervalo nem cálculo de ponto médio. O algoritmo descrito não corresponde a essa abordagem.
Alternativa B — ✅ Correta ⟵ GABARITO
A busca binária é exatamente o algoritmo descrito: ela exige que os dados estejam ordenados e, a cada passo, descarta metade do espaço de busca, tornando-a muito eficiente (complexidade O(log n)). O passo a passo do enunciado é uma implementação típica.
Alternativa C — ❌ Incorreta
A busca por interpolação utiliza uma fórmula de interpolação linear para estimar a posição do elemento, baseada no valor da chave e nos valores nos extremos. Ela não usa simplesmente a média aritmética entre min e max, mas sim uma ponderação. O algoritmo apresentado não corresponde a essa técnica.
Alternativa D — ❌ Incorreta
A busca em árvore (geralmente árvore binária de busca) organiza os dados em uma estrutura hierárquica, onde cada nó possui dois filhos. A busca percorre a árvore comparando a chave com o nó atual e decidindo o próximo ramo. O algoritmo linear apresentado não descreve esse processo.
Alternativa E — ❌ Incorreta
O hash utiliza uma função de espalhamento para mapear chaves a posições em uma tabela. A busca é feita pelo cálculo direto do índice, sem comparações sucessivas ou ajuste de intervalos. Não se aplica ao algoritmo descrito.
PEGA ESSA DICA!
A busca binária é um dos algoritmos mais cobrados em concursos. Memorize sua essência: dados ordenados + divisão sucessiva ao meio + comparação com o elemento médio. Compare com a busca por interpolação, que usa uma fórmula mais elaborada, e com a busca sequencial, que é linear.