MO417 - Questão para a prova oral

Número: 040

Enunciado:
Considerando o algoritmo MAX_HEAPIFY abaixo, que leva um elemento para baixo até satisfazer a condição de heap máximo:

    MAX_HEAPIFY(A, i)
      l ← LEFT(i)
      r ← RIGHT(i)
      if (l ≤ tamanho_do_heap[A]) e (A[l] > A[i]) then
        maior ← l
      else
        maior ← i
      if (r ≤ tamanho_do_heap[A]) e (A[r] > A[maior]) then
        maior ← r
      if maior ≠ i then
        trocar A[i] ↔ A[maior]
        MAX_HEAPIFY(A, maior)
e considerando também o algoritmo BUILD_MAX_HEAP abaixo, que transforma um vetor qualquer num heap máximo:
    BUILD_MAX_HEAP(A)
      tamanho_do_heap[A]) ← comprimento[A]
      for i ← piso(comprimento[A]/2) donwto 1 do
        MAX_HEAPIFY(A, i)
responda:
Quantas chamadas recursivas serão feitas a MAX_HEAPIFY se for dado como entrada para BUILD_MAX_HEAP o vetor A = [5, 5, 5, 5, 5, 5, 5, 5, 5, 5] com 10 elementos? Isto é, quantas vezes a última linha da rotina MAX_HEAPIFY será executada?
  1. 1
  2. 10
  3. 0
  4. 5
  5. NDA

Autor(a): F?bio de Souza Azevedo