Questão para a Prova Oral 115

Semana 9: 23/04/2003
Assunto: Heaps Binomiais e Heaps de Fibonacci


Em se tratando de heaps binomiais, considere o pseudocódigo abaixo para obtenção do menor valor armazenado no heap H, de n elementos. Seja grau[z] o grau (número de filhos) do nó z.

BINOMIAL-HEAP-MINIMUM(H)

y <- NIL
x <- inicio[H]
min <- INFINITO

enquanto x <> NIL faça

   se chave[x] < min então
      min <- chave[x]
      y <- x
   fim-se

   x <- irmao[x]
fim-enquanto

devolver y


Qual das afirmativas abaixo está incorreta?

A) O tempo de execução do procedimento BINOMIAL-HEAP-MINIMUM é O(lg n)
B) inicio[H] aponta para a primeira raiz do heap H
C) grau[irmao[x]] é estritamente maior do que grau[x]
D) chave[irmao[x]] é estritamente maior do que chave[x]
E) NDA

Autor: Augusto Jun Devegili
RA: 25620