ESTRUTURA DE DADOS 4º AULA

Prévia do material em texto

1.
		
Este vetor foi ordenado pelo método:
	
	
	
	Ordenação por seleção (selection sort).  
	
	
	Ordenação por inserção (insertion sort). 
	
	
	Mergesort.  
	
	
	Quicksort.  
	
	
	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.
	
	
	
	 
		
	
		2.
		Sobre o funcionamento da busca binária, é correto afirmar que dividindo seu vetor em duas metades.
	
	
	
	Se o item for menor que o item que está na metade do vetor, o item foi encontrado.
	
	
	Se o item for menor que o item que está na metade do vetor, procure na segunda metade, ou seja, a da direita.
	
	
	Se o item for maior que o item que está na metade do vetor procure na primeira metade, ou seja, a da direita.
	
	
	Se o item for igual ao item que está na metade do vetor, o item não foi encontrado.
	
	
	Se o item for igual ao item que está na metade do vetor, o item foi encontrado.
	
Explicação:
Neste tipo de busca, o vetor deve estar ordenado.
Divide-se o conjunto de dados ao meio e procura-se no meio do vetor. Se achou, retorna a posição do dado do meio. SE não achou, verifica-se se o valor procurado vem antes do  valor do meio. Se for verdade,  redefine-se o fim do vetor, voltando a realizar a busca à esquerda do meio. Se o valor procurado vier depois do valor do meio do vetor, então redefine-se o início e segue-se para a busca na parte à direita do meio do vetor.
		
	Gabarito
Comentado
	
	
	
	
	 
		
	
		3.
		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 sequêncial
	
	
	Pesquisa ordenada
	
	
	Pesquisa binária
	
	
	Tabela Hash
	
	
	Pesquisa de seleção
	
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
Comentado
	
	
	
	
	 
		
	
		4.
		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.
	
	
	
	7 e 1
	
	
	5 e 5
	
	
	6 e 1
	
	
	6 e 2
	
	
	6 e 4
		
	Gabarito
Comentado
	
	
	
	
	 
		
	
		5.
		Marque a afirmativa correta para a "inserção incremental".
	
	
	
	Os pivôs são escolhidos aleatoriamente.
	
	
	É um tipo de sequenciação por intercalação.
	
	
	É um tipo de ordenação por intercalação
	
	
	Consiste em adicionar um valor no vetor, mantendo a ordem existente e ajustando o total de elementos.
	
	
	A técnica é boa quando os dados ficam uniformemente distribuídos entre os seus compartimentos.
		
	Gabarito
Comentado
	
	
	
	
	 
		
	
		6.
		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.
	
	
	
	6 e 1
	
	
	7 e 1
	
	
	5 e 5
	
	
	6 e 4
	
	
	6 e 2
	
	
	
	 
		
	
		7.
		Sabendo-se que o método de ordenção bolha ou bubble sort realiza a troca de elementos adjacentes até que todos os elementos de um vetor esteja ordenado. Então, se submetermos a sequencia de inteiros armazenada em um vetor inicialmente na seguinte ordem : 4, 2, 5, 1.
Pode-se dizer que quando o maior elemento do vetor alcançar sua posição final, a ordenação apresentada no vetor é:
	
	
	
	2,4,1,5
	
	
	2,1,4,5
	
	
	1,2,4,5
	
	
	1,4,2,5
	
	
	4,1,2,5
		
	Gabarito
Comentado
	
	
	
	
	 
		
	
		8.
		Qual papel do for mais interno na função ordena abaixo ?
void ordena( int n, int v[])
{
   int i, j, x;
   for (j = 1; j < n; ++j) {
      x = v[j];
      for (i = j-1; i >= 0 && v[i] > x; --i)
         v[i+1] = v[i];
      v[i+1] = x;
   }
}
	
	
	
	Encontrar o valor de v[j] deve em v[0..j-1].
	
	
	Encontrar o menor valor v[j] que deve ser inserido em v[0..j-1].
	
	
	Encontrar o elmento a ser eliminado do vetor
	
	
	Encontrar o maior valor de x que deve ser inserido em v[0..j-1].
	
	
	Encontrar o ponto onde v[j] deve ser inserido em v[0..j-1].