Atividade de Algoritmos Avancados

Prévia do material em texto

Ciência da Computação 
 
Questão 1 
Assinale a opção correta. Sobre o Mergesort é correto afirmar que : 
• Trabalha com um pivô para separar os dados, da mesma forma que o Quicksort. 
• Só pode ser implementado de forma recursiva. 
• Trabalha sem dividir a lista. 
• É 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. 
 
Questão 2 
Mostre quais dos algoritmos recursivos acha o elemento de máximo valor em um vetor: 
• function achaMaximo(x,n,vet){ if(n==0){ return x; }else{ y = vet[n]; if(y>x){ 
return(achaMaximo(x,n-1,vet)); }else{ return(achaMaximo(y,n-1,vet)); } } }. 
• function achaMaximo(x,n,vet){ if(n==0){ return x; }else{ y = vet[n]; if(y>x){ 
return(achaMaximo(y,n+1,vet)); }else{ return(achaMaximo(x,n+1,vet)); } } }. 
• function achaMaximo(x,n,vet){ if(n==0){ return x; }else{ y = vet[n]; if(y>x){ 
return(achaMaximo(y,n-1,vet)); }else{ return(achaMaximo(x,n-1,vet)); } } }. 
• function achaMaximo(x,n,vet){ if(n==0){ return x; }else{ y = vet[n-1]; if(y == x){ 
return(achaMaximo(y,n-1,vet)); }else{ return(achaMaximo(x,n-1,vet)); } } }. 
• function achaMaximo(x,n,vet){ if(n==0){ return y; }else{ x = vet[n]; if(y>x){ 
return(achaMaximo(y,n,vet)); }else{ return(achaMaximo(x,n-1,vet)); } } }. 
 
Questão 3 
Julgue os itens a seguir, acerca de algoritmos para ordenação. 
I - O algoritmo de ordenação por inserção tem complexidade O(n × log n). 
II - Um algoritmo de ordenação é dito estável caso ele não altere a posição relativa de elementos de 
mesmo valor. 
III - No algoritmo quicksort, a escolha do elemento pivô influencia o desempenho do algoritmo. 
IV - O bubble-sort e o algoritmo de ordenação por inserção fazem, em média, o mesmo número de 
comparações. 
• I e II. 
• I e III. 
• I, III e IV. 
• II e IV. 
• II, III e IV. 
 
Questão 4 
Complete a sentença: A ______________ é o ato de se colocar os elementos de uma sequência de 
informações, ou dados, em uma relação de ordem predefinida. 
• Refatoração 
• Inserção 
• Ordenação 
• Divisão 
• Manipulação 
 
Questão 5 
O algoritmo abaixo é responsável por intercalar dois vetores de forma ordenada. Ele é a base do 
algoritmo de MergeSort. Qual das opções 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-p]; 
• < 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];