Algoritmos e Estrutura de Dados · CESGRANRIO · 2022 | Questão sqc-cg016958

Algoritmos e Estrutura de DadosAlgoritmos de Busca

Código: cg016958
Banca: CESGRANRIO
Órgão: ELETROBRAS-ELETRONUCLEAR
Ano: 2022
Nível: Superior

Cargo: Analista de Sistemas - Aplicação e Segurança de TIC

Seja uma função que realiza uma busca binária sobre um array de números inteiros ordenados. Não se sabe, em princípio, se os números estão ordenados ascendente ou descendentemente. O cabeçalho dessa função é o seguinte:int busca (int [ ] vet, int elem)Isto é, a função busca recebe um array de números inteiros (vet) e um número inteiro (elem) como parâmetros, e retorna um número inteiro. Caso exista em vet um inteiro igual a elem, a função retornará o índice desse inteiro no array; caso contrário, a função retornará -1.O algoritmo de busca binária produz um índice (ind) a cada iteração sobre o array, tendo em vista comparar o elemento que se deseja procurar (elem) com o elemento vet [ ind ]. Isto é:if ( vet [ ind ] == elem )return ind;No comando acima, diz-se que houve uma visita ao elemento vet [ ind ].Admita que a função busca foi chamada por meio do comando a seguir:int resp = busca (vet, 50);Sabendo-se que os elementos visitados foram 54, 17, 33 e 50, nesta ordem, qual array foi passado como parâmetro para a função busca?

A[ 95, 90, 87, 54, 52, 50, 33, 17, 11, 10 ]
B[ 5, 10, 11, 17, 33, 50, 54, 87, 90, 95 ]
C121, 111, 93, 87, 60, 54, 50, 33, 17 ,5 ]
D[ 5, 17, 33, 50, 54, 60, 87, 93, 111, 121 ]
E[ 130, 121, 111, 90, 70, 60, 54, 50, 33, 17 ]

Revelar gabarito e comentário

GabaritoD — [ 5, 17, 33, 50, 54, 60, 87, 93, 111, 121 ]

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 array ordenado (ascendente ou descendente)

Gabarito: letra D. A busca binária visita o elemento central e, conforme a comparação com o alvo, restringe a busca à metade esquerda ou direita. O problema fornece a sequência de visitas [54, 17, 33, 50] para o alvo 50, permitindo identificar o array que gera essa ordem.

A simulação em cada alternativa mostra que apenas a alternativa D ([5, 17, 33, 50, 54, 60, 87, 93, 111, 121]) produz a sequência correta:

Primeira visita: índice 4 (ponto médio) → valor 54. Como o array está em ordem crescente e 54 > 50, a busca segue para a metade esquerda.
Segunda visita: índice 1 → valor 17. 17 < 50, vai para a metade direita (índices 2 a 3).
Terceira visita: índice 2 → valor 33. 33 < 50, vai para a metade direita (índice 3).
Quarta visita: índice 3 → valor 50. Encontrado.

Alternativa A — ❌ Incorreta

Array: [95, 90, 87, 54, 52, 50, 33, 17, 11, 10] (ordem decrescente). Primeira visita no índice 4 (valor 52) ou no índice 5 (valor 50)? Depende do cálculo do ponto médio. Considerando o algoritmo padrão com baixo=0, alto=9, o ponto médio é 4 → valor 52, não 54. Logo, não corresponde à sequência.

Alternativa B — ❌ Incorreta

Array: [5, 10, 11, 17, 33, 50, 54, 87, 90, 95] (ordem crescente). Primeira visita no índice 4 → valor 33, não 54.

Alternativa C — ❌ Incorreta

Array: [121, 111, 93, 87, 60, 54, 50, 33, 17, 5] (ordem decrescente). Primeira visita no índice 4 → valor 60, não 54.

Alternativa D — ✅ Correta ⟵ GABARITO

Conforme demonstrado, a sequência de visitas coincide exatamente.

Alternativa E — ❌ Incorreta

Array: [130, 121, 111, 90, 70, 60, 54, 50, 33, 17] (ordem decrescente). Primeira visita no índice 4 → valor 70, não 54.

Gabarito: letra D

Link permanente: /questoes/cg016958