MO417 - Questão para a prova oral

Número:

Enunciado: Seja a seguinte árvore vermelho e preto :

Depois de inserir o número 3 na árvore, indique a resposta CORRETA:


a) O nó 7 é preto e seu pai é o nó 13
b) O nó 2 é vermelho e não tem filho esquerdo
c) O nó 4 é preto e seu filho esquerdo é o nó 3
d) O nó 13 é a raiz e seu filho esquerdo é o nó 14
e) NDA

Idéia original de: Marleny Luque Carbajal

MO417 - Questão para a prova oral

Número:

Enunciado:
Um algoritmo top-down memoizado e um algoritmo bottom-up de programação dinâmica tiram proveito da propriedade de subproblemas superpostos. Na pratica, se todos os subproblemas devem ser resolvidos pelo menos uma vez, podemos AFIRMAR que:

a)  Um algoritmo bottom-up de programação dinâmica normalmente supera um algoritmo top-down memoizado por um fator constante.
b)  Um algoritmo top-down memoizado normalmente supera um algoritmo bottom-up de programação dinâmica.
c)  Nenhum algoritmo terá vantagem.
d)  Sempre que há sobrecarga para recursão o algoritmo top down é melhor.
e)  NDA

Idéia original de: Marleny Luque Carbajal

MO417 - Questão para a prova oral

Número:

Enunciado: Seja a seguinte versão do algoritmo Fibonacci:

FIBONACCI(n)
1 Criar arranjo Fib[0..n]
2 for i=0 to n
3    do Fib[i]=-1
4 Fib[0]=1
5 Fib[1]=1
6 return LOOKUP-FIB(Fib,n)

LOOKUP-FIB(Fib,n)
1 if (Fib[n]>0)
2   then return Fib[n]
3   else
4       return Fib[n]=LOOKUP-FIB(Fib,n-1) + LOOKUP-FIB(Fib,n-2)

Podemos AFIRMAR que:

a) É um algoritmo memoizado com tempo de execução O(n)
b) Não é um algoritmo memoizado mas seu tempo de execução é O(lg n)
c) Somente é um algoritmo recursivo com tempo de execução O(2^n)
d) É um algoritmo memoizado com tempo de execução O (lg n)
e) NDA


Idéia original de: Marleny Luque Carbajal