Semana 3 - Algoritimo 2

Prévia do material em texto

PERGUNTA 1 
1. A recursividade em Python é apresentada como uma forma para solucionar problemas 
cujo fundamento é a fragmentação de um problema em subproblemas menores de tal 
forma que a função para trazer a solução chame a si mesma até chegar em um problema 
que tenha uma simplicidade que viabiliza sua resolução de uma forma trivial. Todos os 
algoritmos recursivos devem obedecer a três leis importantes, apontadas em 1, 2 e 3. 
Sobre tais leis, avalie as afirmações a seguir, e relacione-as adequadamente aos termos 
às quais se referem. 
 
 
1. Primeira lei. 
2. Segunda lei. 
3. Terceira lei. 
 
 
I. Deve mudar seu estado para se aproximar do caso básico. 
II. Deve chamar a si mesmo, recursivamente. 
III. Deve possuir um caso básico. 
 
 
Assinale a alternativa que correlaciona adequadamente os dois grupos de informação. 
 
a. 1-III; 2-I; 3-II. 
 
b. 1-III; 2-II; 3-I. 
 
c. 1-II; 2-I; 3-III. 
 
d. 1-I; 2-III; 3-II. 
 
e. 1-I; 2-II; 3-III. 
2 pontos 
PERGUNTA 2 
1. O algoritmo de busca binária considera um vetor ordenado de n elementos para realizar 
a varredura dos elementos, por isso é possível implementar um algoritmo mais eficiente 
do que aquele que utiliza a busca sequencial. Adotando o paradigma dividir para 
conquistar, o problema global é dividido em subproblemas, o que faz com que o espaço 
de busca se reduza à metade a cada iteração do algoritmo. 
 
 
Com relação ao algoritmo de busca binária apresentado, avalie as afirmações a seguir. 
 
I. Se n for um valor pequeno, o custo adicional para ordenar a lista pode não compensar. 
II. As comparações requeridas começam com uma lista de tamanho n/2, depois n/4, 
depois n/6, depois n/8 e assim sucessivamente enquanto o elemento procurado não 
tiver sido encontrado, e a lista não for vazia. 
III. O número máximo de comparações requeridas é dado por nlog(n). 
IV. A análise da busca binária elimina metade dos itens que restam a cada comparação. 
 
Está correto que se afirma em: 
 
a. III e IV, apenas. 
 
b. I e III, apenas. 
 
c. I e IV, apenas. 
 
d. II e IV, apenas. 
 
e. II e III, apenas. 
2 pontos 
PERGUNTA 3 
1. A recursão ocorre quando uma função chama a si própria. Vale destacar a importância 
de se saber identificar o ponto de parada da função, de modo a evitar que ela seja 
executada infinitamente. Esse ponto de parada é chamado de “caso base” ou "caso 
básico". 
 
 
Identifique se são verdadeiras (V) ou falsas (F) as afirmativas a seguir. 
 
 
I. ( ) O problema da Torre de Hanói é exemplo clássico de um problema resolvido com 
facilidade por meio da recursão. 
II. ( ) O caso base (ou caso básico) é necessário em toda função recursiva escrita 
corretamente. 
III. ( ) As funções recursivas em Python apresentam grandes benefícios em relação à 
melhora da eficiência. 
 
 
Assinale a alternativa que apresenta a sequência correta. 
 
a. V - V - F. 
 
b. F - V - V 
 
c. F - F - V. 
 
d. V - F - F. 
 
e. V - F - V. 
1 pontos 
PERGUNTA 4 
1. Considere as seguintes afirmativas em relação à recursão: 
 
I. A técnica de memoização tem como objetivo evitar chamadas repetidas a funções recursivas 
custosas. 
II. Uma função recursiva com memoização sempre executará mais rápido que sua respectiva 
função não recursiva. 
III. A técnica de memoização consome mais memória. 
 
Quais afirmativas estão corretas? 
 
a. I e II. 
 
b. Apenas III. 
 
c. Apenas II. 
 
d. Apenas I. 
 
e. I e III. 
1 pontos 
PERGUNTA 5 
1. Considere o seguinte programa em Python: 
2. def f(v, i): 
3. if i == 0: 
4. return v[i] 
5. else: 
6. return v[i] + f(v, i - 1) 
7. 
8. l = [5,4,6,8,1,2] 
print(f(l, len(l) - 1)) 
Assinale a alternativa correta: 
 
a. O programa irá imprimir 1. 
 
b. O programa irá imprimir 8. 
 
c. O programa irá imprimir 25. 
 
d. O programa irá imprimir 5. 
 
e. O programa irá imprimir 26. 
1 pontos 
PERGUNTA 6 
1. A busca binária confere inicialmente o elemento do meio da lista, que se encontra 
ordenada em ordem crescente. Caso o elemento procurado seja menor que o elemento 
intermediário, é feita a busca binária ao lado esquerdo do intermediário, porém caso o 
procurado seja maior que o intermediário, a busca ocorre ao lado direito. 
 
 
Assim, analise o algoritmo abaixo, que apresenta uma função iterativa que faz a busca 
binária. 
 
 
Fonte: Elaborada pela autora. 
 
Com relação ao algoritmo apresentado, avalie as afirmações a seguir. 
 
 
I. Trata-se de um algoritmo que adota a estratégia “dividir para conquistar”. 
II. As divisões são int, por isso a variável middle faz uso da função de retorno. 
III. Middle é um ponto médio que divide a matriz em duas partes. 
IV. Quando determinado número da lista apontado pela variável middle for igual ao 
conteúdo da variável key, encontra-se o elemento procurado. 
 
 
Está correto que se afirma em: 
 
a. I, II e III, apenas. 
 
b. II e IV, apenas. 
 
c. I, III e IV, apenas. 
 
d. I e III, apenas. 
 
e. III e IV, apenas. 
1,5 pontos 
PERGUNTA 7 
1. No programas que usam recursão, como no caso do Fibonacci que exemplifica uma 
sobrecarga de operador de chamada de função, faz-se necessário que quando uma 
função é chamada de forma repetida fazendo uso das mesmas entradas, o seu 
resultado seja carregado do cache ao invés de ser recomputado porque isso fará com 
que recursos da CPU sejam economizados. 
 
Analise as alternativas abaixo e indique qual delas contém a técnica citada no 
enunciado. 
 
a. Função. 
 
b. Recursão. 
 
c. Recorrência. 
 
d. Cache. 
 
e. Memoização.