PESQUISA, ORDENAÇAO E TECNICAS DE ARMAZENAMENTO - Atividade 2

Prévia do material em texto

Pergunta 1
0,25 em 0,25 pontos
	
	
	
	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:
	a. 
pesquisa binária
	Resposta Correta:
	a. 
pesquisa binária
	Feedback da resposta:
	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 2
0,25 em 0,25 pontos
	
	
	
	Avalie se são verdadeiras (V) ou falsas (F) as afirmativas a seguir.
 I - O método de busca “pesquisa binária” necessita de um ordenamento prévio do vetor.
 II - O método “pesquisa binária” possui o tempo de busca maior que o método “busca sequencial”.
 III - O método “busca sequencial” é mais indicado quando se sabe antecipadamente que a maior parte dos registros necessita ser pesquisada.
 As afirmativas I, II e III são, respectivamente:
	
	
	
	
		Resposta Selecionada:
	e. 
V, F e V.
	Resposta Correta:
	e. 
V, F e V.
	
	
	
Pergunta 3
0,25 em 0,25 pontos
	
	
	
	Quanto ao problema da terminação de uma função recursiva comparado com o mesmo problema de uma função iterativa, podemos afirmar que:
	
	
	
	
		Resposta Selecionada:
	d. 
A não terminação em uma função recursiva provoca um erro no programa que será encerrado pelo sistema operacional e na função iterativa provoca um “congelamento” do programa mas não provoca o fim da execução.
	Resposta Correta:
	d. 
A não terminação em uma função recursiva provoca um erro no programa que será encerrado pelo sistema operacional e na função iterativa provoca um “congelamento” do programa mas não provoca o fim da execução.
	Feedback da resposta:
	Em uma função recursiva se as chamadas de funções não tiverem um ponto de parada? Nesse caso, as chamadas continuam a ser inseridas na pilha sucessivamente, mas a pilha tem um limite de espaço e, por este motivo, quando há um número muito grande de chamadas, ocorre um estouro de pilha (em inglês: stack overflow). O programa é então encerrado pelo sistema operacional com uma mensagem de erro.
Se um laço de uma função interativa é executado de forma que a condição de terminação nunca é atingida, a repetição entra no que é chamado de laço infinito, mas o sistema operacional não encerrará o programa, mas este ficará congelado.
	
	
	
Pergunta 4
0,25 em 0,25 pontos
	
	
	
	
Para poder ser aplicado, o algoritmo de pesquisa binária exige que os elementos do array:
	
	
	
	
		Resposta Selecionada:
	c. 
estejam ordenados
	Resposta Correta:
	c. 
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 5
0,25 em 0,25 pontos
	
	
	
	Considere uma lista ordenada com o nome de 1000 pessoas. Utilizando o método de pesquisa binária para localizar o nome de uma destas pessoas, serão necessárias, no máximo ?
	
	
	
	
		Resposta Selecionada:
	c. 
10 comparações.
	Resposta Correta:
	c. 
10 comparações.
	Feedback da resposta:
	O numero de comparações necessárias para se realizar uma busca Binária segue a seguinte equação:
log2 x = numero de comparações  --->  2x = 1000  --> x = 10
Onde x é o numero de elementos na lista
Portanto a alternativa correta é "b"
 
	
	
	
Pergunta 6
0,25 em 0,25 pontos
	
	
	
	Sobre o método de busca sequencial, assinale a alternativa correta.
	
	
	
	
		Resposta Selecionada:
	b. 
O maior número de comparações executado pelo método de busca sequencial 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 sequencial acontece quando o valor procurado não está presente no vetor
	
	
	
Pergunta 7
0,25 em 0,25 pontos
	
	
	
	É 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:
	e. 
binária.
 
	Resposta Correta:
	e. 
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 8
0,25 em 0,25 pontos
	
	
	
	
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:
	d. 
Busca sequencial interativa
	Resposta Correta:
	d. 
Busca sequencial interativa
	Feedback da resposta:
	O método mostrado a seguir é uma implementação da Busca Sequencial para
um vetor de números inteiros. 
public class VetorPesquisa {
private int v[ ]; //vetor da classe instanciado no construtor
public int buscaSeq(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
} }
O método mostrado aqui faz a Busca Sequencial de forma iterativa.
	
	
	
Pergunta 9
0,25 em 0,25 pontos
	
	
	
	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:
	a. 
O método apresentado é uma busca sequencial recursiva
	Resposta Correta:
	a. 
O método apresentado é uma busca sequencial recursiva
	Feedback da resposta:
	O raciocínio utilizado foi o método recursivo pois 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.
	
	
	
Pergunta 10
0,25 em 0,25 pontos
	
	
	
	Sobre o método de busca binária, assinalea alternativa correta.
	
	
	
	
		Resposta Selecionada:
	c. 
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:
	c. 
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.