Algoritmos Avançados Avaliando Aprendizado

Prévia do material em texto

Disc.: 
Aluno(a): Matríc.: 
Acertos: 0,2 de 0,5 
 
 
 
1 
 Questão 
Acerto: 0,0 / 0,1 
 
 
Um algoritmo tem complexidade O(3m3 + 2mn2 +10m +m2 ). Uma maneira simplificada de 
representar a complexidade desse algoritmo é: 
 
 
 O(m3) 
 O(m3 +mn2) 
 
O(m2) 
 
O(mn2) 
 
O(m3 + n2) 
Respondido em 17/09/2021 20:51:12 
 
 
Compare com a sua resposta: Sim. Pois obedece a todas as propriedades da árvore binária e 
em que cada nó apresenta a diferença de altura entre as sub-árvores direita e esquerda de 
1,0 ou -1 
 
 
2 
 Questão 
Acerto: 0,0 / 0,1 
 
 
Dadas as funções de complexidade, marque a alternativa em que esta função represente 
uma relação de recursividade. 
 
 
 
T(n) = n² + n + 1. 
 
T(n) = T(1)+n. 
 T(n) = n³. 
 
T(n) = 2(n-1)+1. 
 T(n) = T(n/2)+2. 
Respondido em 05/10/2021 21:01:58 
 
 
Compare com a sua resposta: 
notree *menorElemento(notree *raiz) // trabalha apenas na sub-árvore esquerda 
{ 
 if (raiz != NULL) 
 while (raiz->esq != NULL) 
 raiz = raiz->esq; 
 return(raiz); 
} 
 
 
3 
 Questão 
Acerto: 0,0 / 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 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. 
 
 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. 
Respondido em 05/10/2021 20:58:29 
 
 
Compare com a sua resposta: 
 
 
4 
 Questão 
Acerto: 0,1 / 0,1 
 
 
Assinale a notação assintótica mais adequada para o algoritmo MergeSort 
 
 
 O (n log2 n) 
 
O (n*n) 
 
O(n) 
 
O (n*n*n) 
 
O ( log3 n) 
Respondido em 05/10/2021 21:00:44 
 
 
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); } 
 
 
5 
 Questão 
Acerto: 0,1 / 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) 
 < SENTENÇA > 
 for (i = p; i < r; ++i) 
 v[i] = w[i-p]; 
} 
 
 
 
 SENTENÇA > = w[j++] = v[i++]; 
 
< SENTENÇA > = w[j++] = v[k++]; 
 < SENTENÇA > = w[k++] = v[j++]; 
 
< SENTENÇA > = w[i++] = v[j++]; 
 
< SENTENÇA > = w[i++] = v[i++]; 
Respondido em 05/10/2021 21:01:36 
 
 
Compare com a sua resposta: