Questão para a Prova Oral 121

Semana: 21/04/2003 a 25/04/2003

Assunto: Heap Binomial / Heap de Fibonacci

Enunciado
Em relação aos tempos de execução para operações sobre implementações de heaps intercaláveis, é CORRETO afirmar?

A) A operação Make-Heap possui tempo de execução no pior caso de Theta(1) para Heaps Binários, Heaps Binomiais e Heaps de Fibonacci.
B) A operação Extract-Min possui tempo de execução no tempo amortizado de Theta(lg n) para Heaps de Fibonacci.
C) A operação Union possui tempo de execução no pior caso de O(lg n) para Heaps Binomiais.
D) A operação Delete possui tempo de execução no tempo amortizado de Theta(1) para Heaps de Fibonacci.
E) N.D.A.

Marcelo Fantinato
RA: 000472