Aula 4 ORDENAÇÃO E PESQUISA

Prévia do material em texto

ESTRUTURA DE DADOS
4a aula
		
	 
	Lupa
	 
	 
	
Vídeo
	
PPT
	
MP3
	 
	
	 
	Exercício: CCT0753_EX_A4_201709084006_V1 
	29/05/2018 23:18:51 (Finalizada)
	Aluno(a): WELLYNGTON ORTIZ
	2018.1 - F
	Disciplina: CCT0753 - ESTRUTURA DE DADOS 
	201709084006
	 
	Ref.: 201709938758
		
	
	 1a Questão
	
	
	
	
	"Algoritmo de ordenação por trocas  que varre um vetor um certo número de vezes, comparando os elementos vizinhos dois a dois. A cada varredura, se o par de elementos está em ordem crescente, nada é feito, caso contrário os elementos do par são permutados". Esta definição está descrevendo o algoritmo de ordenação conhecido por :
		
	 
	BubbleSort
	
	QuickSort
	
	MergeSort
	
	SelectionSort
	
	InsertionSort
	
Explicação:
Das opções apresentadas, as únicas que são ordenações por troca são Bubblesort e Quicksort.
Dessas  duas ordenações, a única que trabalha com duplas de elementos  vizinhos é o Bubblesort. O Quicksort, que está fora do escopo da disciplina, trabalha com pivô.
	
	 
	Ref.: 201709120186
		
	
	 2a Questão
	
	
	
	
	Marque a afirmativa correta para a "inserção incremental".
		
	
	É um tipo de sequenciação por intercalação.
	 
	É um tipo de ordenação por intercalação
	
	Os pivôs são escolhidos aleatoriamente.
	
	A técnica é boa quando os dados ficam uniformemente distribuídos entre os seus compartimentos.
	 
	Consiste em adicionar um valor no vetor, mantendo a ordem existente e ajustando o total de elementos.
	
	 
	Ref.: 201709830168
		
	
	 3a Questão
	
	
	
	
	Caso seja empregada uma busca binária em uma lista sequencial ordenada com 2048 valores, qual seria o número máximo de comparações para encontrar um valor que esteja na lista?
		
	 
	11
	
	9
	 
	8
	
	10
	
	12
	
Explicação:
Como a busca binária sai continuamente dividindo o conjunto de dados ao meio (em duas partes), então vamos fatorar e organizar o resultado como potência de base 2.
 Fatorando 2048 temos 2 11
 Portanto, a resposta é 11.
	
	 
	Ref.: 201709708819
		
	
	 4a Questão
	
	
	
	
	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 maior valor de x que deve ser inserido em v[0..j-1].
	
	Encontrar o elmento a ser eliminado do vetor
	
	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 ponto onde v[j] deve ser inserido em v[0..j-1].
	
	 
	Ref.: 201709120181
		
	
	 5a Questão
	
	
	
	
	Qual a importância de se entender a "ordenação" de dados ?
		
	 
	A ordenação é a base na qual, muitos algoritmos são construídos. Entendendo a ordenação, tem-se conhecimento para resolver outros problemas.
	
	A ordenação é a base na qual, muitos algoritmos são construídos. Entendendo a ordenação, tem-se conhecimento para manter outros problemas.
	
	A ordenação é a base na qual, muitos programas são construídos. Entendendo a ordenação, tem-se conhecimento para manter outros problemas.
	 
	A ordenação é a base na qual, muitos sistemas são construídos. Entendendo a ordenação, tem-se conhecimento para resolver outros problemas.
	
	A ordenação é a base na qual, muitos sistemas são construídos. Entendendo a ordenação, tem-se conhecimento para manter outros problemas.
	
	 
	Ref.: 201709123351
		
	
	 6a Questão
	
	
	
	
	Para consultarmos uma estrutura de dados, normalmente, empregamos um tipo de pesquisa de dados. O trecho de programa a seguir refere-se a uma pesquisa por um elemento único (sua primeira ocorrência), em um conjunto de elementos de dados armazenado em uma estrutura de acesso indexado e aleatório. Selecione a opção correspondente ao algoritmo utilizado, no programa, para a referida pesquisa:
int busca(float v[], float valor, int n) {
int ini = 0, fim = n -1, meio;
while (ini <= fim) {
meio = (ini + fim)/2;
if (v[meio] == valor)  return meio;
if (valor < v[meio]) fim = meio -1;
  else ini = meio+1;
}
return -1;
}
		
	
	pesquisa de cadeias
	 
	pesquisa sequencial
	
	pesquisa cadeias indexada
	 
	pesquisa binária
	
	pesquisa indexada
	
	 
	Ref.: 201709954921
		
	
	 7a Questão
	
	
	
	
	Qual característica NÃO podemos atribuir a PESQUISA BINÁRIA.
		
	
	Quando o valor pesquisado é maior do que a chave do MEIO da lista, devemos dispensar  a metade que vem antes do meio da lista.
	 
	A lista pode estar desordenada.
	 
	São realizadas sucessivas divisões da lista ao meio.
	
	É eficiente quando se trata de listas ordenadas
	
	A lista precisa estar ordenada.
	
Explicação: Na pesquisa binária a lista obrigatoriamente deverá estar ORDENADA.
	
	 
	Ref.: 201710272772
		
	
	 8a Questão
	
	
	
	
	Considere as afirmativas a seguir.
I. Uma forma muito simples de fazer uma busca em um vetor consiste em percorrer o vetor, elemento a elemento, para verificar se o elemento procurado é igual a um dos elementos do vetor.
II. A pesquisa sequencial é extremamente simples e eficiente quando o número de elementos do vetor for muito grande.
III. Na pesquisa binária, a cada interação do algoritmo o tamanho do vetor é dividido ao meio.
IV. A pesquisa binária funciona corretamente quanto o conjunto de dados estiver desordenado.
Assinale a alternativa correta.
		
	
	Somente as afirmativas I e II são corretas.
	
	Somente as afirmativas I e IV são corretas.
	
	Somente as afirmativas II, III e IV são corretas.
	 
	Somente as afirmativas I e III são corretas.
	
	Somente as afirmativas III e IV são corretas.
	
Explicação:
Analisando cada afirmativa :
I. Uma forma muito simples de fazer uma busca em um vetor consiste em percorrer o vetor, elemento a elemento, para verificar se o elemento procurado é igual a um dos elementos do vetor.
Correto. SEria uma busca sequencial.
II. A pesquisa sequencial é extremamente simples e eficiente quando o número de elementos do vetor for muito grande.
Falso. Se tivermos que procurar um elemento que está no fim do vetor ou que não seja encontrado, o tempo de execução será proporcional ao número de elementos. Então, quanto maior a lista, mais tempo levaremos.
III. Na pesquisa binária, a cada interação do algoritmo o tamanho do vetor é dividido ao meio.
Correto.
IV. A pesquisa binária funciona corretamente quanto o conjunto de dados estiver desordenado.
Falso. Por definição, a busca binária só pode atuar em listas ordenadas.
Logo, apenas as afirmativas I  e   III estão corretas.