MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Podemos representar uma expressão contendo operadores e operandos binários em uma árvore binária de forma que a raiz contem um operador que deve ser aplicado ao resultado das expressões das sub-árvores esquerda e direita. Uma expressão em Notação Polonesa os operadores devem preceder os dois valores numéricos associados.

Dado uma expressão e sua árvore correspondente:

5+3*2

Assinale a alternativa que contém o percurso utilizado na árvore e a notação polonesa da expressão:

a) Percorrer a árvore em pós-ordem: 5+3*2

b) Percorrer a árvore em pré-ordem: 532*+

c) Percorrer a árvore em pós-ordem: +5*32

d) Percorrer a árvore em pré-ordem: +5*32

e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - QUESTÃO PARA A PROVA ORAL - 2ª QUESTÃO

Número:
Enunciado: Comparando os pseudo-códigos abaixo que calculam a sequência de Fibonacci podemos afirmar que:
a) Fib1 e Fib2 possuem o mesmo tempo de execução, pois calculam a sequência de Fibonacci resolvendo os mesmos subproblemas várias vezes.
b) Fib1 e Fib2 utilizam a técnica de divisão e conquista, pois esta técnica é utilizada quando o problema é dividido em subproblemas dependentes.
c) Se adicionarmos a Fib1 a técnica de memoização, Fib1 tem tempo de execução menor que Fib2, pois nem todos os subproblemas são resolvidos para encontrar a solução do problema geral.
d) Fib2 utiliza a técnica de programação dinâmica, pois esta técnica é utilizada quando há uma repetição dos mesmos subproblemas os quais não são independentes, ou seja, os subproblemas compartilham subsubproblemas.
e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - QUESTÃO PARA A PROVA ORAL - 1ª QUESTÃO

Número:
Enunciado: Sobre programação dinâmica assinale a alternativa correta marcando V para verdadeiro e F para falso:
( ) Ao contrário da divisão e conquista as técnicas de programação dinâmica utilizam um enfoque tabular de baixo para cima que resolve todos os subproblemas uma única vez. Este enfoque gera algoritmos mais eficientes.
 ( ) Problemas onde a divisão de um problema de tamanho n resulta em a subproblemas de tamanho n-1 geralmente nos levam a algoritmos recursivos exponenciais O(a^n). A programação dinâmica aplicada a estes problemas não gera algoritmos eficientes.
( ) A construção de um algoritmo utilizando programação dinâmica supõe quatro etapas: definição da subestrutura ótima, definição da recursividade, resolução dos subproblemas (bottom-up) e construção da solução ótima.
( ) A programação dinâmica geralmente é aplicada a problemas de otimização, quando os subproblemas são dependentes e superpostos, buscando todas as soluções ótimas para o problema.

a) V – F – V – F
b) V – V – V – F
c) F – F – F – V
d) F – V – V – F
e) NDA

Ideia original de: Lucas Oliveira Batista