(AS-III) ESTRUTURA DE DADOS LINEARES

Prévia do material em texto

Pergunta 1
Resposta Selecionada: e. 
Respostas:
a. 
b. 
c. 
d. 
e. 
Comentário da resposta:
Considere o vetor V=[9,4,3,5,1,2] e o procedimento Partition() descrito a seguir. Após a execução do
procedimento, assinale a alternativa que descreve CORRETAMENTE o novo estado do vetor.
Partition(V,p,r)
1 - x←V[r]
2 - i←p-1
3 - para j←p até r-1
4 -    se V[j]≤x
5 -      i←i+1
6 -      trocar V[i] e V[j]
7 -  trocar V[i+1] e V[r]
8 - retornar i+1
[1, 2, 3, 5, 9, 4].
[1, 2, 3, 4, 5, 9].
 
[9, 2, 3, 4, 1, 5].
[9, 1, 2, 4, 3, 5].
[1, 4, 3, 5, 9, 2].
 
[1, 2, 3, 5, 9, 4].
O valor 2 separa os subvetores.
Pergunta 2
Resposta Selecionada: c. 
Respostas: a. 
b. 
c. 
Considere as seguintes afirmações.
I - A ideia fundamental por trás de um algoritmo recursivo é a transformação do problema (instância)
original em outro menor ou mais simples, de modo que seu tamanho ou sua simplicidade permita uma
nova chamada recursiva.
II - A condição de parada de um algoritmo recursivo é denominada de caso base.
III - Todo algoritmo recursivo terá uma versão baseada na abordagem da divisão e conquista para
executar a mesma tarefa.
IV - Os algoritmos recursivos são mais simples de compreender e apresentam um número menor de
instruções.
É CORRETO o que se afirma APENAS em:
I e II.
II e IV.
I e III.
 
I e II.
0,2 em 0,2 pontos
0 em 0,2 pontos
d. 
e. 
Comentário
da
resposta:
II e III.
 
I e IV.
 
A ideia fundamental por trás de um algoritmo recursivo é a transformação do problema
(instância) original em outro menor ou mais simples, de modo que seu tamanho ou sua
simplicidade permita uma solução direta e todo algoritmo recursivo terá uma versão
iterativa para executar a mesma tarefa.
Pergunta 3
Resposta
Selecionada:
a.
Respostas: a.
b.
c.
d.
e.
Comentário
da
resposta:
Considere o texto a seguir e assinale a alternativa que
preenche CORRETA e RESPECTIVAMENTE as lacunas.
“As desvantagens de se utilizar __________ estão ligadas ao __________. É muito comum que
__________ acabem por consumir muita memória, por conta do __________ de cada chamada
realizada. Além disso, os algoritmos recursivos são mais difíceis de serem depurados.”
um algoritmo recursivo; consumo de recursos; instâncias muito grandes;
empilhamento.
um algoritmo recursivo; consumo de recursos; instâncias muito grandes;
empilhamento.
empilhamento; consumo de recursos; instâncias muito grandes; algoritmo
recursivo.
empilhamento; algoritmo recursivo; instâncias muito grandes; consumo de
recursos.
consumo de recursos; empilhamento; instâncias muito grandes; algoritmo
recursivo.
consumo de recursos; algoritmo recursivo; instâncias muito grandes;
empilhamento.
As desvantagens de se utilizar um algoritmo recursivo estão ligadas ao consumo de
recursos. É muito comum que instâncias muito grandes acabem por consumir muita
memória, por conta do empilhamento de cada chamada realizada. Além disso, os
algoritmos recursivos são mais difíceis de serem depurados.
Pergunta 4
Considere o vetor V=[1,7,2,6,3,5,4] e o procedimento Partition() descrito a seguir. Após a execução do
procedimento, assinale a alternativa que descreve CORRETAMENTE o novo estado do vetor.
Partition(V,p,r)
1 - x←V[r]
2 - i←p-1
3 - para j←p até r-1
0,2 em 0,2 pontos
0,2 em 0,2 pontos
Resposta Selecionada:
a. 
Respostas:
a. 
b. 
c. 
d. 
e. 
Comentário da resposta:
4 -    se V[j]≤x
5 -     i←i+1
6 -     trocar V[i] e V[j]
7 - trocar V[i+1] e V[r]
8 - retornar i+1
[1, 2, 3, 4, 7, 5, 6].
 
[1, 2, 3, 4, 7, 5, 6].
 
[1, 7, 2, 6, 3, 5, 4].
[1, 2, 3, 4, 6, 7, 5].
[1, 2, 7, 6, 3, 5, 4].
 
[1, 2, 3, 4, 5, 6, 7].
Realize o teste de mesa do algoritmo para identificar o novo estado.