Teste - Estruturas de dados - aula 4 pdf

Prévia do material em texto

1.
		Analisando o trecho de código a seguir:
inicio=0; 
fim= tamanho - 1;
meio=(inicio+fim)/2; 
while(procura != nomeVetor[meio] && inicio != fim)
{
  if(procura > nomeVetor[meio])            
   inicio=meio+1;
  else 
   fim=meio; 
  meio=(inicio+fim)/2;   
}
if(nomeVetor[meio]==procura)
 cout<<"\n....: "< < outroVetor[meio]<<endl;
else 
 cout<<"\nDado nao encontrado\n";</endl;
Pode-se afirmar que:
	
	
	
	trata-se da implementação do algortimo de ordenação por seleção.
	
	
	trata-se da implementação do algortimo de busca binária.
	
	
	trata-se da implementação do algortimo de busca sequencial
	
	
	trata-se da implementação do algortimo de ordenação por inserção.
	
	
	trata-se da implementação do algortimo de ordenação bolha.
	
	Gabarito
Coment.
	
	
	
	 
		
	
		2.
		
	
	
	
	if(vet[j-1] > vet[j] )
    { 
         aux=vet[j];
         vet[j]= vet[j-1];
         vet[j-1]=aux;      
     }
	
	
	if(vet[j] == vet[j-1] )
    { 
         aux=vet[j];
         vet[j]= vet[j-1];
         vet[j-1]=aux;      
     }
	
	
	if(vet[j] < vet[j-1] )
    { 
         aux=vet[j];
         vet[j]< vet[j-1];
         vet[j-1]=aux;      
     }
	
	
	if(vet[j] < vet[j-1] )
    { 
         aux=vet[j];
         vet[j-1]= vet[j];
         vet[j-1]=aux;      
     }
	
	
	if(vet[j-1] < vet[j] )
    { 
         aux=vet[j];
         vet[j]= vet[j-1];
         vet[j-1]=aux;      
     }
	
	
	
	 
		
	
		3.
		Entre os diversos algoritmos de pesquisa existentes, certamente os mais famosos são os da pesquisa sequencial e o da pesquisa binária. A busca ou pesquisa sequencial pode ser aplicada em vetores independente destes estarem ordenados, entretanto a busca binária só se aplica em vetores ordenados.
Seja o vetor A= {10,35,41,55,69,70,98}, suponha que o número 70 foi pesquisado pelo algoritmo da busca sequencial e também pelo algoritmo da busca binária, ambos algoritmos realizam testes nos elementos do vetor até achar o que procuram ou definirem que o elemento não se encontra no vetor. Sendo assim marque a alternativa que expressa o número de testes realizados pela busca sequencial e o número de testes realizados pela busca binária, respectivamente, até encontrarem o 70.
	
	
	
	5 e 5
	
	
	7 e 1
	
	
	6 e 4
	
	
	6 e 2
	
	
	6 e 1
	
	Gabarito
Coment.
	
	
	
	 
		
	
		4.
		Os algoritmos de busca são muito utilizados em estrutura de dados. Sendo assim, o algoritmo que realiza a busca em vetores e que exige acesso aleatório aos elementos do mesmo e que parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento que se deseja com o elemento do meio do vetor, é chamado de:
	
	
	
	Pesquisa de seleção
	
	
	Tabela Hash
	
	
	Pesquisa sequêncial
	
	
	Pesquisa binária
	
	
	Pesquisa ordenada
	
Explicação:
O enunciado descreve a busca binária.
A busca sequencial trabalha sequencialmente testando elemento a elemento.
Pesquisa de seleção ou ordenada não foram abordadas.
Tabela hash trabalha com função hash e não se encaixa na descrição feita.
	
	Gabarito
Coment.
	
	
	
	 
		
	
		5.
		
Este vetor foi ordenado pelo método:
	
	
	
	Mergesort.  
	
	
	Quicksort.  
	
	
	Ordenação por seleção (selection sort).  
	
	
	Ordenação por inserção (insertion sort). 
	
	
	Método da bolha (bubble sort).  
	
Explicação:
O bubblesort trabalha comparando e trocando, se preciso, duplas de dados vizinhos.  Portanto, pelo comportamento na sequÊncia descrita temos o método da bolha ou bubblesort.
	
	
	
	 
		
	
		6.
		Os métodos de ordenação são muito utilizados para facilitar a recuperação posterior de itens ordenados. Existem vários métodos de ordenação, por esse motivo, assinale corretamente a alternativa que mostra o nome do método que utiliza a estratégia de ordenação por trocas de vizinhos e é considerado o método mais simples.
	
	
	
	Seleção
	
	
	Hash
	
	
	Inserção
	
	
	Bolha
	
	
	Binária
	
	Gabarito
Coment.
	
	
	
	 
		
	
		7.
		Suponha uma listagem, contendo número de inscrição e pontuação (ordenada pelo número de inscrição) dos candidatos para o cargo de Analista de Sistemas de uma grande empresa pública. São 1024 candidatos inscritos e o sistema implementado para consulta do resultado, permite busca binária ou busca sequencial pelo número de inscrição. O número máximo de comparações executadas se fosse utilizada a busca binária e se fosse utilizada busca sequencial, respectivamente, seria de:
	
	
	
	1024 e 512
	
	
	10 e 1024
	
	
	9 e 10
	
	
	10 e 10
	
	
	9 e 9
	
	Gabarito
Coment.
	
	
	
	 
		
	
		8.
		Nos métodos de ordenação interna, quais são aqueles classificados como tipo método simples?
	
	
	
	Shell Sort, Quick Sort e Heap Sort
	
	
	Selection Sort, Insert Sort e Bubble Sort
	
	
	Insert Sort, Bubble Sort e Quick Sort
	
	
	Selection Sort, Shell Sort e Bubble Sort
	
	
	Insert Sort, Bubble Sort e Shell Sort
	
	Gabarito
Coment.
	
	
	Gabarito
Coment.
	
	
	Gabarito
Coment.