Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — CESGRANRIO 2025

Algoritmos e Estrutura de DadosEstrutura de Dados
Código
cg023517
Banca
CESGRANRIO
Órgão
BANESE
Ano
2025
Nível
Médio
Cargo
Técnico Bancário III - Desenvolvimento
A lista a seguir contém uma coleção de números inteiros ordenados descendentemente.lst=[15, 13, 9, 7, 5, 2, -2, -5, -6, -10, -12, -14]Suponha que uma função, chamada busca, execute uma busca binária sobre a lista lst. O algoritmo implementado em busca contém uma pequena diferença, quando comparado com o algoritmo de busca binária tradicional, pois ele retorna o somatório de todos os elementos da lista que forem visitados até que o elemento procurado seja encontrado. O somatório irá incluir o elemento que se procura, caso ele esteja presente na lista.Qual será o valor retornado pela função busca quando ela for chamada para realizar uma busca sobre a lista lst à procura do valor -11?
  1. A-16
  2. B-24
  3. C-22
  4. D-26
  5. E-38
Revelar gabarito e comentário

GabaritoD — -26

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 em lista descendente com somatório de visitados

Gabarito: D ( -26 ). A função busca implementa uma busca binária sobre a lista lst ordenada descendentemente, retornando a soma de todos os elementos visitados durante a busca até que o alvo seja encontrado ou o intervalo se esgote. Como -11 não está na lista, a busca termina com low > high, e o somatório dos elementos acessados é -26.

A lista fornecida é:

lst = [15, 13, 9, 7, 5, 2, -2, -5, -6, -10, -12, -14] (índices 0 a 11).

O algoritmo de busca binária adaptado para ordem descendente funciona invertendo a direção da comparação: se o alvo é menor que o elemento do meio, a busca continua à direita (pois os valores decrescem); se é maior, continua à esquerda.

Simulação passo a passo da busca pelo valor -11:

  1. low=0, high=11 → mid=5 (valor 2). -11 < 2 → direita. Soma acumulada = 2.

  2. low=6, high=11 → mid=8 (valor -6). -11 < -6 → direita. Soma = 2 + (-6) = -4.

  3. low=9, high=11 → mid=10 (valor -12). -11 > -12 → esquerda. Soma = -4 + (-12) = -16.

  4. low=9, high=9 → mid=9 (valor -10). -11 < -10 → direita. Soma = -16 + (-10) = -26.

  5. Agora low=10, high=9 → busca encerra, pois low > high. Soma final = -26.

Portanto, o valor retornado é -26.

  1. 1mid=5 (2) → direitaSoma: 2
  2. 2mid=8 (-6) → direitaSoma: -4
  3. 3mid=10 (-12) → esquerdaSoma: -16
  4. 4mid=9 (-10) → direitaSoma: -26
  5. 5low>high → fimRetorno: -26
LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

-16 corresponde ao valor da soma após o terceiro passo, mas a busca ainda não terminou.

Alternativa B — ❌ Incorreta

-24 não é obtido em nenhum momento da simulação.

Alternativa C — ❌ Incorreta

-22 também não corresponde à soma acumulada em nenhum passo.

Alternativa D — ✅ Correta ⟵ GABARITO

-26 é exatamente a soma dos elementos visitados (2, -6, -12, -10) até o fim da busca.

Alternativa E — ❌ Incorreta

-38 seria a soma se outros elementos fossem visitados, o que não ocorre.

Gabarito: letra D.

Link permanente: /questoes/cg023517