Questão 5474683

• Banca: CESGRANRIO
• Órgão: Banco do Brasil
• Ano: 2021
• Provas: CESGRANRIO - 2021 - Banco do Brasil - Agente de Tecnologia
• Disciplina: Programação
• Assuntos: Java; Linguagens de programação

Desejam-se realizar buscas nas seguintes coleções de dados, representadas na linguagem Java:

I - Um array de 1.000 números inteiros ordenados de forma decrescente;

II - Uma lista encadeada desordenada e alocada dinamicamente, cujos 1.000 nós contêm strings (uma string por nó);

III - Uma lista encadeada, alocada dinamicamente, cujos 1.000 nós contêm números decimais (um número double por nó) ordenados de forma ascendente.

Levando-se em consideração a exequibilidade e a eficiência, quais métodos de busca devem ser empregados, respectivamente, em cada um dos três casos acima? 

• A. I – sequencial; II – sequencial; III – binária
• B. I – binária; II – sequencial; III – sequencial
• C. I – binária; II – sequencial; III – binária
• D. I – sequencial; II – sequencial; III – sequencial
• E. I – sequencial; II – binária; III – binária 

Gabarito: B

Comentários

• GAB B

  A ideia da questão é encontrar o melhor algoritmo para buscar um elemento nas estruturas de dados citadas. Não faz diferença se é Java ou qualquer outra linguagem

  Essa busca pode ser feita de forma sequencial ou binária. Mas a busca binária só será mais eficiente se estes dois pré-requisitos forem satisfeitos:

  1. A lista for ordenada (não importa se é crescente ou decrescente)
  2. Qualquer elemento da lista possa ser acessado em tempo constante

   

  I (binário) - Array ordenado de forma decrescente

  Qualquer elemento de um array pode ser acessado em O(1), e esse array está ordenado. Portanto, busca binária é mais eficiente

   

  II (sequencial) - Uma lista encadeada desordenada

  Se está desordenada, busca binária não é uma opção (precisaria ordenar primeiro). Portanto, deve-se usar busca sequencial

   

  III (sequencial) - Uma lista encadeada ordenada de forma ascendente

  Os elementos de uma lista encadeada não são acessados em tempo constante. O primeiro elemento é acessado em O(1) e o último em O(n). É possível sim realizar a busca binária, pois os elementos estão ordenados. Porém, o tempo gasto para se deslocar entre os elementos torna o tempo médio da busca binária maior se comparado a uma busca sequencial nessa estrutura