MO417 - Questão para a prova oral

Número: 104

Enunciado:
Com relação a Heaps Binomiais e de Fibonacci, e considerando as afirmações abaixo, assinale a alternativa correta:

1 - A inserção de um nó em Heaps Binomiais é mais complicada que a de Heaps de Fibonacci, pelo fato que este último apenas concatena este novo nó a ser inserido na lista de raizes e verifica se sua chave é menor que a da raiz atual.

2 - Heaps de Fibonacci apresentam limites de tempo assintóticos amortizados melhores do que Heaps Binomiais pois algumas de suas operações são mais simples, adiando o trabalho de consolidar as árvores e seus nós no heap.

3 - Heaps de Fibonacci não são recomendados quando é grande a quantidade de operações de "extrair o mínimo"(extrair nó com a chave mínima) e "Eliminação" de uma chave.

4 - As árvores binomiais, assim como as árvores nos heaps de Fibonacci, obedecem à propriedade de heap mínimo, contudo as árvores nos heaps de Fibonacci não são necessariamente ordenadas.

Alternativas:

1. Todas as afirmações são verdadeiras.
2. Somente as afirmações 1, 2 e 3 são verdadeiras.
3. Somente as afirmações 1 e 4 são verdadeiras.
4. Somente as afirmações 2, 3 e 4 são verdadeiras.
5. NDA

Autor(a): Nelson Luiz Geromel Ra: 958097