Resumêra

Questão 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-I; 2-III; 3-II. C) 1-II; 2-I; 3-III. D) 1-I; 2-II; 3-III. E) 1-III; 2-II; 3-I.

Resposta correta: A) 1-III; 2-I; 3-II

Questão 2

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) Apenas I. B) I e II. C) Apenas III. D) I e III. E) Apenas II.

Resposta correta: D) I e III

Questão 3

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) F - V - V B) V - V - F. C) V - F - F. D) V - F - V. E) F - F - V.

Resposta correta: B) V - V - F.

Questão 4

Considere o seguinte programa em Python:

def func(n):
    if n <= 1:
        return 1
    else:
        return n * func(n - 1)

print(func(4))

Assinale a alternativa correta:

A) O programa vai entrar em loop infinito. B) O programa irá retornar o fatorial de 4. C) O programa irá retornar 1. D) O programa irá retornar 4. E) O programa possui um ou mais erros e não vai executar.

Resposta correta: B) O programa irá retornar o fatorial de 4.

Questão 5

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) Memoização. B) Recorrência. C) Recursão. D) Cache. E) Função.

Resposta correta: A) Memoização.

Questão 6

Sobre funções recursivas, assinale V ou F para as alternativas:

( ) Uma função recursiva deve sempre ter um critério de parada.

( ) Uma função recursiva sempre será mais rápida que uma função não recursiva.

( ) Função recursiva é aquela que chama um método implementado em outra classe.

( ) Funções recursivas são úteis para resolver problemas cuja definição é também recursiva.

A) V-V-V-V B) F-F-F-F C) V-F-F-V D) V-V-F-F E) F-F-V-V

Resposta correta: C) V-F-F-V

Questão 7

As listas em Python permitem listar informações dentro de uma única variável para que elas sejam utilizadas dentro do código. Uma prática comum ao se trabalhar com listas é a utilização de informações dentro dela, já que uma lista comporta uma estrutura de dados com itens organizados linearmente que podem ser acessados por meio de um índice. Essa tarefa de acesso pode ser facilitada diante de uma ordenação que simplifica o trabalho das informações contidas na lista. Assinale a alternativa que representa a função cujo objetivo é a ordenação das informações de uma lista.

A) index() B) remove() C) list() D) pop() E) sorted()

Resposta correta: E) sorted()

Questão 8

Ao passar um valor x para uma função recursiva para realizar uma soma, o que acontece é que a função vai somar de 1 até o valor x, o que indica que ela está chamando a si mesma, porém, a cada vez, com um argumento diferente. Assinale a alternativa que representa a função citada de forma generalizada.

A) f(x) = f(x-1) B) f(x) = f(x+1) + x C) f(x) = f(x+1) - x D) f(x) = f(x-1) - x E) f(x) = f(x-1) + x

Resposta correta: E) f(x) = f(x-1) + x

Questão 9

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.

A) II e IV, apenas. B) II e III, apenas. C) III e IV, apenas. D) I e III, apenas. E) I e IV, apenas.

Resposta correta: E) I e IV, apenas.

Questão 10

Ao tentar resolver o problema do fatorial de um número, basta multiplicá-lo por todos os seus antecessores até chegar ao número 1. Com o uso da recursividade, esse problema pode ser resolvido inicialmente sendo dividido em subproblemas menores do mesmo tipo (multiplicando um número por seus antecessores) e tomando um ponto de parada da recursão que neste caso deve ser o retorno em 1. Mas isso exige cálculos repetidos. Após análise do problema apresentado, avalie as asserções a seguir e a relação proposta entre elas.

I. O uso da recursividade exigida em problemas como o cálculo de fatorial ou cálculo da série de Fibonacci podem ocasionar problemas.

PORQUE

II. Existem chances de que o subproblema resolvido na árvore de recursão já esteja resolvido e continue sendo resolvido provocando uma sobrecarga.

A) As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I. B) A asserção I é uma proposição verdadeira, e a II é uma proposição falsa. C) As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I. D) A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. E) As asserções I e II são falsas.

Resposta correta: C) As asserções I e II são verdadeiras, e a II é uma justificativa da I.

Questão 11

É necessário o entendimento sobre funções recursivas e funções iterativas para seu uso de forma adequada. Existem problemas naturalmente recursivos e aqueles definidos em termos recursivos. Uma função pode ser escrita como uma função recursiva sem o uso de iteração. Também há possibilidade de que um problema definido recursivamente de forma natural dê origem a uma função iterativa no código fonte. Identifique se são verdadeiras (V) ou falsas (F) as afirmativas a seguir.

I. ( ) Toda função recursiva deve conter uma condição que estabelece o ponto em que ela deve parar de chamar a si própria.

II. ( ) Funções recursivas usam repetição por meio de comandos e utilizam uma condição de teste que, ao falhar, finaliza a iteração.

III. ( ) Funções iterativas usam repetição por meio de várias chamadas a uma rotina e utilizam o alcance de um caso trivial (ou caso básico) para serem finalizadas.

IV. ( ) A recursão entra em loop infinito nos casos em que a condição de parada (ou caso básico) nunca for atingida.

Assinale a alternativa que apresenta a sequência correta.

A) F - V - V - F. B) V - F - F - V. C) V - F - F - F. D) F - F - F - V. E) V - V - F - F.

Resposta correta: B) V - F - F - V.

Algoritmos e Programação de Computadores II

Atividade Avaliativa