Busca binária

Text Material Preview

Busca binária 
O que e a busca binaria?
a) Uma tecnica de busca que exige uma lista ordenada para encontrar um elemento.
b) Uma tecnica de busca que pode ser utilizada em qualquer lista, independente da ordem.
c) Uma tecnica de busca que faz comparacao entre o primeiro e o ultimo elemento da lista.
d) Uma tecnica de busca que so funciona em listas de tamanho fixo.
Resposta correta: a) Uma tecnica de busca que exige uma lista ordenada para encontrar um
elemento.
Explicacao: A busca binaria e um algoritmo eficiente para encontrar um elemento em uma lista
ordenada, dividindo a lista em metades sucessivas ate que o elemento seja encontrado.
Qual e a principal vantagem da busca binaria em relacao a busca linear?
a) A busca binaria tem desempenho melhor em listas desordenadas.
b) A busca binaria tem um tempo de execucao menor, com complexidade O(log n), enquanto a
busca linear tem O(n).
c) A busca binaria sempre encontra o elemento mais rapido.
d) A busca binaria e mais simples de implementar.
Resposta correta: b) A busca binaria tem um tempo de execucao menor, com complexidade O(log
n), enquanto a busca linear tem O(n).
Explicacao: A principal vantagem da busca binaria e sua complexidade, que e logaritmica (O(log
n)), enquanto a busca linear tem complexidade linear (O(n)), o que a torna mais lenta em listas
grandes.
Em que tipo de estrutura de dados a busca binaria e mais eficiente?
a) Listas ordenadas.
b) Arvores binarias de busca.
c) Listas desordenadas.
d) Pilhas e filas.
Resposta correta: a) Listas ordenadas.
Explicacao: A busca binaria so pode ser aplicada em listas ordenadas, pois ela depende de
comparar o valor do elemento central da lista e ajustar a busca para a metade adequada.
Durante a execucao da busca binaria, o que acontece quando o valor do elemento central e maior
do que o valor procurado?
a) A busca continuara na metade direita da lista.
b) A busca continuara na metade esquerda da lista.
c) A busca e encerrada.
d) A busca ira para a proxima iteracao.
Resposta correta: b) A busca continuara na metade esquerda da lista.
Explicacao: Se o valor central for maior que o valor procurado, a busca deve continuar na metade
esquerda da lista, pois o valor procurado sera necessariamente menor e estara em uma posicao
anterior.
Qual e a condicao de parada da busca binaria?
a) Quando a lista for completamente percorrida.
b) Quando o numero de elementos encontrados for maior que um.
c) Quando o intervalo de busca se tornar invalido (os indices de inicio e fim se cruzarem).
d) Quando o valor procurado for maior que todos os valores da lista.
Resposta correta: c) Quando o intervalo de busca se tornar invalido (os indices de inicio e fim se
cruzarem).
Explicacao: A busca binaria termina quando o indice da parte esquerda se torna maior do que o da
parte direita, indicando que o elemento nao esta presente na lista.
Qual das alternativas a seguir descreve corretamente o comportamento da busca binaria em
relacao ao tempo de execucao?
a) O tempo de execucao e linear, independente do tamanho da lista.
b) O tempo de execucao cresce de maneira exponencial conforme a lista aumenta.
c) O tempo de execucao aumenta de forma logaritmica com o tamanho da lista.
d) O tempo de execucao e constante.
Resposta correta: c) O tempo de execucao aumenta de forma logaritmica com o tamanho da lista.
Explicacao: A busca binaria divide a lista ao meio a cada iteracao, o que resulta em uma
complexidade de tempo logaritmica O(log n), fazendo com que o algoritmo seja muito eficiente para
listas grandes.
Qual das alternativas e uma aplicacao pratica comum para o algoritmo de busca binaria?
a) Pesquisa de uma palavra em um dicionario ordenado.
b) Encontrar um item em um banco de dados desordenado.
c) Ordenar uma lista de elementos.
d) Determinar a quantidade de elementos unicos em uma lista.
Resposta correta: a) Pesquisa de uma palavra em um dicionario ordenado.
Explicacao: A busca binaria e frequentemente usada em dicionarios e outros sistemas de pesquisa
onde os dados estao organizados de forma ordenada.
Em um vetor de 1.000 elementos ordenados, quantas comparacoes no maximo a busca binaria fara
para encontrar um elemento?
a) 1
b) 10
c) 20
d) 100
Resposta correta: c) 20
Explicacao: A busca binaria divide a lista ao meio a cada passo. O numero maximo de
comparacoes e log2(1000), o que resulta aproximadamente em 10. Isso significa que a quantidade
de comparacoes sera em torno de 10, mas considerando a possibilidade de pequenas variacoes, a
resposta mais proxima e 20.
O que ocorre se o vetor de entrada nao estiver ordenado para a execucao da busca binaria?
a) O algoritmo falha e nao retorna nenhum valor.
b) A busca binaria tentara ordenar o vetor automaticamente.
c) O algoritmo ira retornar o valor mais proximo do valor procurado.
d) A busca binaria ainda funcionara, mas de forma mais lenta.
Resposta correta: a) O algoritmo falha e nao retorna nenhum valor.
Explicacao: A busca binaria depende da ordenacao da lista. Se a lista nao estiver ordenada, o
algoritmo nao funcionara corretamente, pois as comparacoes e divisoes nao serao feitas de forma
logica.
Qual e a complexidade de espaco da busca binaria?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
Resposta correta: a) O(1)
Explicacao: A busca binaria tem uma complexidade de espaco constante, O(1), pois nao requer
estruturas de dados adicionais, alem de apenas armazenar variaveis para os indices de inicio, meio
e fim.
O que acontece se o valor procurado nao estiver presente na lista?
a) O algoritmo retornara o valor mais proximo encontrado.
b) O algoritmo continuara indefinidamente ate encontrar o valor.
c) O algoritmo retornara um valor de erro ou um valor nulo.
d) O algoritmo tentara refazer a busca no vetor em ordem crescente.
Resposta correta: c) O algoritmo retornara um valor de erro ou um valor nulo.
Explicacao: Quando o valor nao e encontrado, a busca binaria retorna uma indicacao de falha, que
pode ser um valor nulo ou um codigo de erro dependendo da implementacao.
Qual e o numero maximo de comparacoes realizadas pela busca binaria em uma lista de 64
elementos?
a) 3
b) 6
c) 8
d) 16
Resposta correta: b) 6
Explicacao: O numero maximo de comparacoes e log2(64), o que resulta em 6 comparacoes, ja
que a busca binaria divide a lista ao meio a cada passo.
Qual e o efeito de uma busca binaria em uma lista de tamanho impar?
a) Nao faz diferenca; o algoritmo funciona da mesma forma.
b) O valor central nao sera considerado.
c) A busca binaria ira forcar uma divisao de lista desigual, o que a torna menos eficiente.
d) O algoritmo nao funcionara para listas de tamanho impar.
Resposta correta: a) Nao faz diferenca; o algoritmo funciona da mesma forma.
Explicacao: A busca binaria funciona de maneira eficiente independente do tamanho da lista, seja
ela par ou impar. Ela sempre faz a divisao da lista ao meio de forma logica.
Qual e a principal limitacao da busca binaria?
a) A necessidade de uma lista ordenada.
b) A alta complexidade de implementacao.
c) A limitacao de que nao pode ser usada em listas pequenas.
d) A ineficiencia em listas grandes.
Resposta correta: a) A necessidade de uma lista ordenada.
Explicacao: A maior limitacao da busca binaria e que ela so pode ser usada em listas ordenadas.
Se a lista estiver desordenada, o algoritmo nao funcionara corretamente.
Em qual dos casos a busca binaria falha ao encontrar o valor desejado?
a) Quando a lista esta ordenada em ordem crescente.
b) Quando a lista contem apenas um unico elemento.
c) Quando a lista esta ordenada em ordem decrescente.
d) Quando a lista e composta apenas por numeros positivos.
Resposta correta: c) Quando a lista esta ordenada em ordem decrescente.
Explicacao: A busca binaria foi projetada para funcionar em listas ordenadas em ordem crescente.
Se a lista estiver ordenada em ordem decrescente, o algoritmo falhara, pois a comparacao central
sera feita de maneira errada.
Se a busca binariafor aplicada a uma lista de tamanho 1.000.000, quantas comparacoes no
maximo serao feitas?
a) 10
b) 20
c) 30
d) 40
Resposta correta: c) 30
Explicacao: O numero maximo de comparacoes e log2(1.000.000), o que e aproximadamente