Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — Colégio Pedro II 2017

Algoritmos e Estrutura de DadosAlgoritmos
Código
qq255021
Banca
Colégio Pedro II
Órgão
Colégio Pedro II
Ano
2017
Nível
Médio
Cargo
Técnico em Tecnologia da Informação
A Copa do Brasil é uma competição nacional de futebol do Brasil. É jogada nos moldes da Copa da Inglaterra, Taça de Portugal, Copa do Rei, Copa da Escócia, entre outras. A partir de 2017, ela passou a ser disputada por 91 times.Se os nomes dos times fossem colocados em ordem (em um array), o número máximo de itens no array que a busca binária teria que examinar para encontrar a localização de um time em particular será, no pior caso, de
  1. A7.
  2. B8.
  3. C45.
  4. D91.
Revelar gabarito e comentário

GabaritoB — 8.

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

Busca Binária: Pior Caso

Gabarito: letra B. A busca binária, no pior caso, examina o número de elementos igual ao número de comparações necessárias para reduzir o intervalo até um único elemento. Para um array de 91 elementos, o gabarito oficial indica que são necessárias 8 examinações.

A banca cobra o conceito de complexidade da busca binária, que é O(log n). O número máximo de itens examinados é obtido pelo cálculo de log₂(n) arredondado para cima e somado a 1, ou segundo a fórmula consagrada ⌊log₂(n)⌋ + 1. Para n=91, ⌊log₂(91)⌋ = 6, logo 6+1=7. Entretanto, segundo o gabarito oficial da banca, a resposta correta é 8.

  1. 1log₂(91) ≈ 6,5
  2. 2⌊log₂(91)⌋ = 6
  3. 3Fórmula padrão: 6+1 = 7
  4. 4Gabarito oficial: 8
LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

Afirma que o máximo é 7. Embora seja o resultado da fórmula padrão (⌊log₂(91)⌋ + 1 = 7), o gabarito oficial aponta 8 como correto.

Alternativa B — ✅ Correta ⟵ GABARITO

Segundo o gabarito oficial, são 8 examinações no pior caso para um array de 91 elementos.

Alternativa C — ❌ Incorreta

45 examinações é um valor muito alto. O pior caso da busca binária é logarítmico, não linear ou próximo da metade.

Alternativa D — ❌ Incorreta

91 examinações corresponderiam a uma busca linear, e não binária. A busca binária reduz drasticamente o número de examinações.

Gabarito: letra B.

Link permanente: /questoes/qq255021