Questão de Algoritmos e Estrutura de Dados — Algoritmos — UFLA 2025
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg620159
Banca
UFLA
Órgão
UFLA
Ano
2025
Nível
Médio
Cargo
Técnico em Tecnologia da Informação
O objetivo de uma busca é encontrar uma ou mais ocorrências de registros com chaves iguais à chave de pesquisa. Quando o conjunto de registros a ser pesquisado é pequeno o suficiente para ser carregado todo de uma vez na memória principal (ou memória interna) do computador, métodos de busca interna podem ser utilizados.Considerando um conjunto de registros previamente ordenado e sem repetições, analise as seguintes proposições sobre métodos de busca interna:I. A aplicação de busca sequencial sobre esse conjunto exigirá a verificação de todos os registros do conjunto para o melhor caso.II. A aplicação de busca sequencial com sentinela sobre esse conjunto reduz o número de comparações, pois elimina a necessidade de testar a cada passo se o final do conjunto foi alcançado.III. A busca binária pode ser aplicada sobre esse conjunto de registros.Assinale a alternativa CORRETA:
AApenas as proposições II e III estão corretas.
BApenas a proposição II está correta.
CApenas a proposição III está correta.
DApenas as proposições I e III estão corretas.
Revelar gabarito e comentário▾
GabaritoA — Apenas as proposições II e III estão corretas.
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”.
Métodos de busca interna
Gabarito: letra A. Apenas as proposições II e III estão corretas. A proposição I é falsa porque, no melhor caso da busca sequencial, o elemento procurado está na primeira posição, exigindo apenas uma verificação, e não todos os registros. A proposição II é verdadeira: a busca sequencial com sentinela elimina a necessidade de testar a cada passo se o final do conjunto foi alcançado, reduzindo o número de comparações. A proposição III é verdadeira: a busca binária pode ser aplicada a conjuntos ordenados, condição satisfeita pelo enunciado.
Proposição
Afirmação
Análise
Correta?
I
A busca sequencial exige verificar todos os registros no melhor caso.
No melhor caso, o elemento está na primeira posição (1 verificação).
❌ Incorreta
II
A busca sequencial com sentinela reduz comparações ao eliminar teste de fim a cada passo.
A sentinela evita a verificação de fim de vetor a cada iteração, reduzindo comparações.
✅ Correta
III
A busca binária pode ser aplicada a conjuntos ordenados.
O conjunto está ordenado e sem repetições, condição necessária para busca binária.
✅ Correta
Busca sequencial: Melhor caso (Elemento na 1ª posição, Apenas 1 verificação); Pior caso (Elemento ausente ou no final, Todos os registros); Com sentinela (Elimina teste de fim, 1 comparação por iteração); Busca binária (Requer ordenação, O(log n))
Item I — ❌ Incorreta
A afirmação diz que a busca sequencial exigirá a verificação de todos os registros para o melhor caso. No melhor caso, o elemento está na primeira posição, exigindo apenas uma comparação. A verificação de todos os registros ocorre no pior caso (elemento não encontrado ou no final). Portanto, a proposição está errada.
Item II — ✅ Correta
Na busca sequencial com sentinela, o valor procurado é inserido ao final do vetor como sentinela. Assim, a cada iteração, basta comparar a chave com o elemento atual, eliminando a verificação de fim de vetor. Isso reduz o número de comparações (embora o total possa ser N+1 no pior caso, mas elimina uma comparação por iteração). A proposição está correta.
Item III — ✅ Correta
A busca binária requer que os dados estejam ordenados. Como o conjunto está previamente ordenado e sem repetições, a busca binária é perfeitamente aplicável, com complexidade O(log n). A proposição está correta.
NÃO CAIA NESSA!
A banca inverte o conceito de melhor caso da busca sequencial. Cuidado: no melhor caso, o elemento está na primeira posição (apenas 1 verificação); no pior caso, todos os registros são verificados. A proposição I mistura esses conceitos.
PEGA ESSA DICA!
Memorize: busca sequencial sem sentinela faz 2 comparações por iteração (chave e fim); com sentinela, apenas 1. Busca binária exige ordenação e é muito mais rápida para grandes volumes.