SIMULADO AV1 - ALGORITMOS AVANÇADOS

Prévia do material em texto

Disc.: ALGORITMOS AVANÇADOS
Aluno(a): Acertos: 1,0 de 2,0 22/03/2021
Acerto: 0,0 / 0,2
O que devemos fazer para escrever a série de Fibonnacci ao inverso:
fibonacci(n){
 if(n==0){
 return(0);
 }else{
 if(n==1){
 return(1);
 }else{
 n1 = fibonacci(n-1);
 n2 = fibonacci(n-2);
 return n1 + n2;
 }
 }
}
Acrescentar:
 var n1 = 0, n2=0;
 colocar PRINT n1 antes das recursões e
 PRINT n2 após as recursões
Acrescentar:
 colocar PRINT n1 + n2 após as recursões
Acrescentar:
 var n1 = 0, n2=0;
 colocar PRINT n1 entre as recursões e
 PRINT n2 após as recursões
Acrescentar:
 var n1 = 0, n2=0;
 colocar PRINT n1 + n2 antes das recursões
Acrescentar:
 var n1 = 0, n2=0;
 colocar PRINT n1 antes das recursões e
 PRINT n2 entre as recursões
Acerto: 0,0 / 0,2
A funcao abaixo deveria inserir um nó ao fim de uma lista, porém tem um erro proposital, qual das opções
mostra a versão correta.
insereFim(lista,no){
Estácio: Alunos https://simulado.estacio.br/bdq_simulados_av1_resultado.asp?cod_hist...
1 of 4 10/05/2021 19:30
 if(lista == null){
 lista = no;
 no.proximo = null;
 }else{
 insereFim(lista.proximo,no);
 }
}
insereFim(lista,no){ if(lista.proximo == null){ lista.proximo = no.proximo; no.proximo = null;
}else{ insereFim(lista.proximo,no); } }
insereFim(lista,no){ if(lista == null){ lista = no; no.proximo = null; }else{
insereFim(lista.proximo,no.proximo); } }
insereFim(lista,no){ if(lista.proximo != null){ lista.proximo = no; no.proximo = null; }else{
insereFim(lista.proximo,no); } }
insereFim(lista,no){ if(lista.proximo == null){ lista.proximo = no; no.proximo = null; }else{
insereFim(lista.proximo,no.proximo); } }
insereFim(lista,no){ if(lista.proximo == null){ lista.proximo = no; no.proximo = null; }else{
insereFim(lista.proximo,no); } }
Acerto: 0,2 / 0,2
Analisando a Complexidade do Merge Sort. Consideramos " n "(número de dados a serem ordenados) uma
potência de 2 e a seguinte equação de recorrência, T(n) é o tempo para uma entrada de tamanho n.
T(1)=1(caso base)
T(n)=2T(n/2)+3(n-1)
Temos 2 chamadas recursivas como n/2 e um total de 3(n-1) intercalações por aproximação vamos
considerar n intercalações. Sendo assim faz sentido escrever
T(n) = 2T(n/2) + n
Uma vez que podemos substituir n/2 na equação principal.
2T(n/2) = 2(2T(n/4) + n/2)
2T(n/2) = 4T(n/4) + n
Logo:
T(n) = 2T(n/2) + n
T(n) = 4T(n/4) + n + n
T(n) = 4T(n/4) + 2n
Assim se continuarmos a análise da equação, chegaremos a conclusão que a complexidade de pior caso
para o MergeSort é
O(n^2) onde n^2 é n elevado a 2
O(1)
O(n)
O(log n)
O(n lg n) , onde lg é log na base 2
Acerto: 0,0 / 0,2
Assinale a opção correta :
A complexidade da busca sequencial é O(n) e a da busca binária é O(log2n), o que confirma que a
busca binária é mais eficiente do que a busca sequencial quando a lista está ordenada.
Todo trecho com passos elementares, que não dependem do tamanho da entrada, possue
complexidade constante, ou seja, é O(n).
Se tenho 2 algoritmos que resolvem um problema P, ambos com complexidade de tempo no pior
caso O(n), então sempre posso afirmar que os dois algoritmos terão tempos de execução idênticos
para entradas do mesmo tamanho.
A complexidade da multiplicação dos elementos de um vetor com n elementos é O(n2).
Estácio: Alunos https://simulado.estacio.br/bdq_simulados_av1_resultado.asp?cod_hist...
2 of 4 10/05/2021 19:30
Considere três trechos de um mesmo programa com complexidades O(n), O(log2n) e O(n2). A
complexidade do programa completo é, no pior caso, O(log2n)
Acerto: 0,2 / 0,2
Este recurso não é um comando, mas uma "habilidade" de uma função chamar a si mesma. Isto não é
privilégio apenas da linguagem C++, muitas outras linguagens como Java, Visual Basic, entre outras
também é possível ser feito isso. Estamos falando da: ______________________________.
reprocividade
recursividade
reconcividade
retrocidade
respeitabilidade
Acerto: 0,2 / 0,2
Um algoritmo tem complexidade O(3m3 + 2mn2 +10m +m2 ). Uma maneira simplificada de representar a
complexidade desse algoritmo é:
O(mn2)
O(m3)
O(m2)
O(m3 +mn2)
O(m3 + n2)
Acerto: 0,0 / 0,2
Sejam T1(n)=100n + 10, T2(n)=10n2 + 2n e T3(n)=0,5n3 + n2 +2 as questões que descrevem a
complexidade de tempo dos algoritmos Alg1, Alg2 e Alg3, respectivamente, para entradas de tamanho n. A
respeito da ordem de complexidade desses algoritmos, pode-se concluir que:
as complexidade assintóticas de Alg1, Alg2 e Alg3, estão, respectivamente em O(100), O(10) e
O(0,5)
Alg2 e Alg3 pertencem às mesmas classes de complexidade assintótica
as complexidade assintóticas de Alg1, Alg2 e Alg3, estão, respectivamente em O(n), O(n2) e O(n2)
Alg1 e Alg2 pertencem às mesmas classes de complexidades assintótica
as complexidade assintóticas de Alg1, Alg2 e Alg3, estão, respectivamente em O(n), O(n2) e O(n3)
Acerto: 0,2 / 0,2
Relacione a primeira coluna de algoritmos com a segunda coluna de complexidade para o pior caso. (Onde
lg é o log na base 2 e n^2 é n elevado a 2.)
( ) Busca Binária 1- O(n lg n)
( ) Busca Sequencial 2- O(n)
( ) Ordenação BubbleSort 3- O(lg n)
( ) Ordenação MergeSort 4- O(n^2)
Assinale a alternativa com a correlação correta entre as colunas<\p>
2 - 3 - 4 - 1
2 - 3 - 1 - 4
1 - 2 - 3 - 4
3 - 2 - 1 - 4
3 - 2 - 4 - 1
Estácio: Alunos https://simulado.estacio.br/bdq_simulados_av1_resultado.asp?cod_hist...
3 of 4 10/05/2021 19:30
Acerto: 0,2 / 0,2
São métodos (algoritmos) de busca em cadeias?
 d) Fusão direta e Knuth-Morris-Pratt.
a) Boyer-Moore e Knuth-Morris-Pratt.
 c) Knuth-Morris-Pratt e fusão balanceada multidirecional.
 b) Boyer-Moore e fusão natural.
 e)Boyer-Moore e ordenação polifásica.
Acerto: 0,0 / 0,2
Relacione as duas colunas seguintes e marque a sequencia correta:
1. Complexidade de Espaço ( ) Cálculo da complexidade recursiva.
2. Complexidade de Tempo ( ) Uso da Pilha de Execução.
3. Expansão Telescópica ( ) Ocupação de memória.
4. Recursão ( ) Custo de processamento.
4 - 3 - 1 - 2.
3 - 4 - 1 - 2.
2 - 1 - 4 - 3.
4 - 1 - 3 - 2.
3 - 1 - 2 - 4.
Estácio: Alunos https://simulado.estacio.br/bdq_simulados_av1_resultado.asp?cod_hist...
4 of 4 10/05/2021 19:30