jor

MO417 - Questão para a prova oral

Número:

Enunciado: Considere o código de Huffman, transcrito abaixo a partir do livro:

  HUFFMAN(C)
  1  n = |C|
  2  Q = C
  3  for i = 1 to n-1
  4       allocate a new node z
  5       z.left = x = EXTRACT-MIN(Q)
  6       z.right = y = EXTRACT-MIN(Q)
  7       z.freq = x.freq + y.freq
  8       INSERT(Q,z)
  9  return EXTRACT-MIN(Q)    //return the root of the tree

Qual das seguintes afirmações é correta?

a. a escolha gulosa consiste em alocar os elementos de menor frequência no topo da árvore
b. pode executar em tempo O(n) se Q tiver os elementos ordenados em ordem crescente
c. executa em tempo O(n lg lg n) utilizando um heap para armazenar os valores de Q
d. o código avalia subproblemas anteriores para fazer as suas escolhas
e. NDA

Idéia original de: Jorge Augusto Hongo