PESQUISA, ORDENAÇAO E TECNICAS DE ARMAZENAMENTO - ativ2

Prévia do material em texto

• Pergunta 1 
 
Analise o código do método abaixo e assinale a alternativa correta. 
public int metodo(int tam, int key) { 
 if(tam == 0) 
 return -1; 
 if(v[tam-1] == key) 
 return(tam-1); 
 else 
 return(metodo(tam-1, key)); 
} 
 
 
Resposta 
Selecionada: 
e. 
O método apresentado é uma busca 
binária recursiva 
Resposta Correta: d. 
O método apresentado é uma busca 
sequencial recursiva 
 
 
• Pergunta 2 
 
Sobre o método de busca binária, assinale a 
alternativa correta. 
 
Resposta 
Selecionada: 
b. 
O maior número de comparações 
executado pelo método de busca binária 
acontece quando o valor procurado não 
está presente no vetor 
Resposta 
Correta: 
b. 
O maior número de comparações 
executado pelo método de busca binária 
acontece quando o valor procurado não 
está presente no vetor 
Feedback 
da resposta: 
A Busca Sequencial tem uma vantagem sobre a Busca Binária, que é o 
fato de não precisar que o conjunto de dados seja ordenado. Mas as vantagens 
param por aí. Analisando o desempenho pelo número máximo de comparações 
necessárias para que cada uma delas localize uma chave dentro do conjunto de 
dados. 
 
Caso valor não esteja presente no vetor, n vezes. 
Caso valor esteja presente no vetor: 1 vez no melhor caso (valor está na 
primeira posição). 
n vezes no pior caso (valor está na última posição). 
n 2 vezes no caso médio. 
Quanto tempo a busca binária demora para executar? 
Em outras palavras, quantas vezes a comparação o valor == vetor[i] é 
executada? 
Caso valor não exista no vetor, log2(n) vezes. 
O logaritmo de base 2 aparece porque sempre dividimos o intervalo ao meio. 
Caso valor exista no vetor: 1 vez no melhor caso (valor é a mediana do vetor). 
log2(n) vezes no caso médio. 
Para n = 1000, o algoritmo de busca sequencial irá executar 1000 comparações 
no pior caso, 500 operações no caso médio. 
Por sua vez, o algoritmo de busca bináia irá executar 10 comparações no pior 
caso, para o mesmo n. 
O algoritmo de busca binária supõe que o vetor está ordenado. Ordenar um 
vetor também tem um custo, superior ao custo da busca sequencial. Se for para 
fazer uma só busca, não vale a pena ordenar o vetor. Por outro lado, se 
pretendermos fazer muitas buscas, o esforço da ordenação já poderá valer a 
pena. 
 
• Pergunta 3 
 
Seja o seguinte vetor, ordenado de forma 
ascendente: 
 
 
 
Caso se utilize um algoritmo de busca binária, 
quantas iterações serão necessárias para que o valor 
80 seja encontrado? 
 
Resposta Selecionada: c. 
4 
Resposta Correta: c. 
4 
Feedback da resposta: 2x = 9 ----> x = 4 
 
 
• Pergunta 4 
 
É um método de pesquisa ou busca, cujo algoritmo 
parte do pressuposto de que o vetor está ordenado e 
realiza sucessivas divisões do espaço de busca, 
comparando o elemento buscado (chave) com o 
elemento no meio do vetor. Se o elemento do meio 
 
do vetor for a chave, a busca termina com sucesso. 
Caso contrário, se o elemento do meio vier antes do 
elemento buscado, então a busca continua na metade 
posterior do vetor. E finalmente, se o elemento do 
meio vier depois da chave, a busca continua na 
metade anterior do vetor. Trata-se do método 
denominado busca 
. 
Resposta Selecionada: a. 
binária. 
 
Resposta Correta: a. 
binária. 
 
Feedback 
da 
resposta: 
Trata-se da busca Binaria onde a busca 
funciona da seguinte maneira: a chave de 
busca é comparada à chave do registro do 
meio da tabela. Se elas forem iguais, a busca 
termina com sucesso; caso contrário, a 
metade superior ou a metade inferior da 
tabela será pesquisada de modo semelhante. 
Para decidir qual metade da tabela 
será pesquisada, compara-se o valor da 
chave com o valor do meio do vetor. Como o 
vetor está ordenado, se o valor da chave for 
maior que o valor central da tabela, a busca 
deve seguir procurando do lado em que os 
valores são maiores. No caso do valor da 
chave ser menor, basta continuar a busca do 
outro lado. 
 
 
• Pergunta 5 
 
Seja um vetor de inteiros com 400 elementos 
distintos ordenados em ordem crescente. Qual é o 
número máximo de iterações necessárias para 
encontrar um elemento qualquer do vetor caso seja 
utilizado o algoritmo de busca binária? 
 
 
Resposta Selecionada: e. 
9 
 
Resposta Correta: e. 
9 
 
Feedback da resposta: 2x = 400 
x = 9 
 
 
• Pergunta 6 
 
 
 
Analise o trecho de código a seguir: 
public class VetorPesquisa { 
private int v[ ]; //vetor da classe instanciado no 
construtor 
public int metodo(int key) 
{ 
int i; 
for(i=0; i < v.length; i++) { 
if(key == v[i]) 
return(i); //posição no vetor 
} 
return(-1); //Não encontrou 
} } 
A qual algoritmo esse código pertence? 
 
Resposta Selecionada: e. 
Busca binária 
 
 
Resposta Correta: b. 
Busca sequencial interativa 
 
• Pergunta 7 
 
 
 
Para poder ser aplicado, o algoritmo de pesquisa 
binária exige que os elementos do array: 
 
Resposta Selecionada: b. 
estejam ordenados 
Resposta Correta: b. 
estejam ordenados 
Feedback 
da 
resposta: 
A Busca Binária é um método de busca mais 
eficiente que a Busca Sequencial, porém 
apresenta a restrição de que somente pode 
ser aplicado em um conjunto ordenado de 
dados. 
 
 
• Pergunta 8 
 
Considere que um algoritmo de pesquisa, em um 
arquivo previamente ordenado, é caracterizado por 
realizar comparação de chaves e sucessivas divisões 
no espaço de busca até encontrar o termo 
pesquisado ou até haver um único registro. Trata-se 
de um algoritmo de: 
 
 
 
 
 
Resposta Selecionada: b. 
árvore de busca binária. 
Resposta Correta: e. 
pesquisa binária 
 
 
• Pergunta 9 
 
 
 
 
Dada uma coleção de n elementos ordenados por 
ordem crescente, pretende-se saber se um 
determinado elemento x existe nessa coleção. 
Supondo que essa coleção está implementada como 
sendo um vetor a[0...n-1] de n elementos inteiros, 
utilizando-se um algoritmo de pesquisa binária, o 
número de vezes que a comparação x==a[i] será 
executada, no pior caso, é calculada por: 
Resposta Selecionada: b. 
log2(n) 
Resposta Correta: a. 
n/2 
 
Feedback da resposta: log2(n) = numero de comparações 
 
 
• Pergunta 10 
 
Analise o trecho de código a seguir. 
public class VetorPesquisa { 
private int v[ ]; 
public int busca(int key) { 
return metodo(v.length, key); 
} 
private int metodo(int tam, int key) 
{ 
if(tam == 0) //chegou ao final e não 
encontrou o valor 
return -1; 
if(v[tam-1] == key) //encontrou o valor 
return(tam-1); 
else 
return(metodo(tam-1, key)); //continua procurando 
} 
} 
 
 
A qual algoritmo esse código pertence? 
Resposta Selecionada: e. 
Busca sequencial Recursiva 
 
Resposta Correta: e. 
Busca sequencial Recursiva 
 
Feedback 
da 
resposta: 
A seguir, temos o método de Busca Sequencial agora implementado de forma 
recursiva. 
O raciocínio utilizado para escrever este método recursivo foi o seguinte: o 
problema inicial é encontrar um valor dentro de um vetor de tamanho tam. A 
cada chamada recursiva, o problema é reduzido para encontrar este valor em um 
vetor de tamanho tam-1. Ou seja, a cada passo, a chamada recursiva consiste em 
reduzir uma unidade no tamanho do vetor até que o valor seja 
encontrado, ou até que se chegue ao final do vetor. Caso o número não 
seja encontrado, o tamanho do vetor fica valendo zero. 
public class VetorPesquisa { 
private int v[]; 
public int buscaRec(int key) { 
return buscaSeqR(v.length, key); 
} 
private int buscaSeqR(int tam, int key) 
{ 
if(tam == 0) //chegou ao finale não encontrou o valor 
return -1; 
if(v[tam-1] == key) //encontrou o valor 
return(tam-1); 
else 
return(buscaSeqR(tam-1, key)); //continua procurando 
} 
} 
Portanto a alternativa correta é "c".