mig

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Após transformar um heap máximo em uma árvore binária, observou-se que ela possuía no máximo k elementos. Então a altura da árvore binária é:

a) lg(k+1) - 1
b) lgk
c) lgk +1
d) lg(k-1) + 1
e) NDA

Ideia original de: Lucas Miguel de Carvalho

wal

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: O professor Astolfo, palmeirense fanático, decidiu criar uma árvore alviverde, com as seguintes propriedades:

1. Todo nó é verde ou branco;
2. A raiz é verde;
3. Toda folha (NIL) é verde;
4. Se um nó é branco, então ambos os seus filhos são verdes.
5. Para cada nó, todos os caminhos desde um nó até as folhas descendente contêm o mesmo número de nós verdes.

É correto afirmar que:

a. Todo nó verde na árvore alviverde equivale a todo nó vermelho na árvore vermelho-preto.
b. As operações feitas sobre uma árvore vermelho-preto são assintoticamente menores que as operações feitas sobre uma árvore alviverde.
c. A árvore alviverde e a árvore vermelho-preto se equivalem, sendo as cores dos nós a única diferença entre ambas, onde os nós verdes equivalem aos vermelhos, e os nós brancos equivalem aos nós pretos.
d. Um árvore vermelho-preto gerada, a partir de uma entrada de n chaves, é a mesma para uma árvore alviverde, sobre a mesma entrada.
e. NDA

Ideia Original: Wallace Felipe Francisco Cardoso

jul

MO417 - Questão para a prova oral

Número:

Enunciado:

Considere as seguintes cidades em uma árvore de pesquisa binária, de altura 3.

Belém	Fortaleza	Recife
Belo Horizonte	Goiânia	Rio de Janeiro
Brasília	Guarulhos	Salvador
Campinas	Manaus	São Luís
Curitiba	Porto Alegre	São Paulo

 

Qual é a sequência correta de pesquisa nesse árvore,
se procuramos a cidade Natal?

 
De acordo com a resposta, assinale a alternativa correta:

1. Guarulhos, Rio de Janeiro, Porto Alegre, Manaus.
2. Guarulhos, Campinas, Fortaleza, Goiânia.
3. Guarulhos, Rio de Janeiro, Porto Alegre, Recife.
4. Guarulhos, Rio de Janeiro, São Luis, Salvador.
5. NDA 

Ideia original de: Julián Esteban Gutiérrez Posada

2013-04-19

daf

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Sejam dois problemas A e B.
Problema A: exibe subestrutura ótima.
Problema B: exibe subestrutura ótima e existe uma escolha localmente ótima que leva a uma solução globalmente ótima.
Assinale a alternativa falsa:
a) É possível implementar algoritmo de programação dinâmica para A.
b) É possível implementar algoritmo de programação dinâmica para B.
c) É possível implementar algoritmo guloso para A.
d) É possível implementar algoritmo guloso para B.
e) N.D.A

Ideia original de: Danielle Furtado dos Santos Dias

dav

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Para um conjunto finito de possiveis valores de moedas, deseja-se resolver o problema: "Encontrar o menor numero de moedas para compor o troco de uma compra"

Utiliza-se  um algoritmo guloso que segue os passos:

1. Escolhe-se a moeda de maior valor possivel  que seja menor do que o troco
2. Resolve-se o problema novamente descontando do troco inicial o valor da moeda escolhida no passo 1.

Qual dos conjuntos de valores de moedas faz com que o algoritmo leve a soluções ótimas?

1. {1, 5, 10, 25, 50} 
2. {1, 2, 10, 25, 50}
3. {1, 2, 10, 15, 30}
4. O Algoritmo sempre retorna soluções ótimas
5. NDA

Ideia original de: Daniel Vidal

fab

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: Usando código de Huffman, qual seria uma codificação ótima para os caracteres {a, b, c, d, e, f} que aparecem com frequências {40, 20, 15, 10, 10, 5}?

A) {1, 10, 110, 1110, 11110, 11111}
B) {0, 10, 110, 1110, 11110, 11111}
C) {0, 100, 101, 110, 1110, 1111}
D) {0, 10, 101, 110, 1110, 1111}
E) NDA

Ideia original de: Fabrício Matheus Gonçalves