Algoritmos Avançados - Avaliando Aprendizado - 3

Prévia do material em texto

isc.: ALGORITMOS AVANÇADOS   
	Aluno(a): 
	Matríc.: 
	Acertos: 0,1 de 0,5
	11/10/2020 (Finaliz.)
		1
          Questão
	Acerto: 0,0  / 0,1
	
	Assinale a opção correta.  Sobre o Mergesort é correto afirmar que :
		
	 
	Trabalha com um pivô para separar os dados que depois serão intercalados.
	 
	É uma ordenação por intercalação que no pior caso tem complexidade O(nlog2 n)
	
	É uma ordenação por trocas que no pior caso tem complexidade O(log2 n)
	
	Trabalha dividindo a lista apenas uma vez.
	
	Só pode ser implementado de forma recursiva, pois usa a técnica de divisão e conquista.
	Respondido em 11/11/2020 10:54:11
	
Compare com a sua resposta: bool Verifica( char str[], int len) { if (len <= 1) return TRUE; if (str[0] != str[len-1]) return FALSE; return Verifica( str + 1, len - 2); }
	
		2
          Questão
	Acerto: 0,0  / 0,1
	
	Assinale a opção correta.   Sobre o Mergesort é correto afirmar que :
		
	
	Só pode ser implementado de forma recursiva.
	 
	É uma ordenação por intercalação que no pior caso tem complexidade O(nlog2 n)
	
	Não usa a técnica de divisão e conquista.
	
	Trabalha sem dividir a lista
	 
	Trabalha com um pivô para separar os dados, da mesma forma que o Quicksort
	Respondido em 11/11/2020 10:55:05
	
Compare com a sua resposta:
i = 0;          --------------------------------------  1
for (  ; i <= 4;  )   ---------------------------  6 vezes      
{     ----------------------------------------------------------------------------------------------------------
       j = 0;  --------------------------------------------------------------- 1    
      for ( ; j < n-1 ; )  ----------------------------------------------  n testes
      {
          cout <<  i  << " - "  <<  j ;         ----  1         (n-1) vezes                   Entro 5 vezes  no 1o. for
           j++;                                      -----  1        (n-1) vezes
       }
      i++;    ---------------------------------------------------------------- 1
     -------------------------------------------------------------------------------------------------------------
}
 
No. de passos :  1 + 6  + 5.(1 + n + 2.(n-1) + 1)  = 15n + 7
Complexidade : O(n)
 
	
		3
          Questão
	Acerto: 0,0  / 0,1
	
	Assinale a resposta certa.  Sobre o Quicksort é correto afirmar que :
		
	 
	É uma ordenação por trocas que no pior caso tem complexidade O(n2)
	
	Trabalha com ou sem um pivô para fazer a partição.
	
	Não usa a técnica de divisão e conquista
	 
	Trabalha intercalando os dados, assim como o Mergesort
	
	Só pode ser implementado de forma recursiva
	Respondido em 11/11/2020 11:10:11
	
Compare com a sua resposta:
int contaNos(notree *r)
{
     if (r == NULL)
         return 0;
     if (r ->dado % 2 == 0)   //testa se é par
         return (1 + contaNos(r ->esq) + contaNos(r ->dir));
     return (contaNos(r ->esq) + contaNos(r ->dir));
}
 
	
		4
          Questão
	Acerto: 0,1  / 0,1
	
	O Algoritmo de QuickSort tem como principio:
		
	
	  Achar o elemento que está na metade e ordenar os dois elementos a direita e a esquerda deste e repetir para as duas metades.
	
	 Varrer os elementos da direita para e esquerda trocando os elementos colocando o menor a direita o maior a esquerda
	 
	 Jogar todos os valores menores para um lado e os maiores para o outro e repetir outra vez com a metade da direita e a metade da esquerda.
	
	 Varrer os elementos da direita para e esquerda trocando os elementos colocando o menor a esquerda e o maior a direita.
	
	 Jogar todos os valores maiores para a direita e os menores apra a direita e repetir o mesmo com a metade da direita.
	Respondido em 11/11/2020 11:05:22
	
Compare com a sua resposta:
	
		5
          Questão
	Acerto: 0,0  / 0,1
	
	O algoritmo abaixo é responsável por intercalar dois vetores de forma ordendada. Ele é a base do algoritmo de MergeSort. Qual das opcoes abaixo completa propriamente o algoritmo ?
intercala (int p, int q, int r, Vetor v)
{
   Vetor w;                                
   
   int i = p, j = q;                      
   int k = 0;                             
   while (i < q AND j < r) {                
      if (v[i] <= v[j])  
          w[k++] = v[i++];  
      else  
          w[k++] = v[j++];               
   }                                       
   while (i < q)  
      w[k++] = v[i++];        
   while (j < r)  
      w[k++] = v[j++];
       < SENTENÇA >
  
}
		
	
	< SENTENÇA > = for (i = p; i < k; ++i) v[i] = w[i-k];
	
	< SENTENÇA > = for (i = 0; i < r; ++i) v[i] = w[i];
	 
	< SENTENÇA > = for (i = p; i < r; ++i) v[i] = w[i-p];
	 
	< SENTENÇA > = for (i = 0; i < r; ++i) v[i] = w[p];
	
	< SENTENÇA > = for (i = p; i < k; ++i) v[i] = w[i-p];
	Respondido em 19/11/2020 19:39:56
	
Compare com a sua resposta: