MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dada a árvore de busca binária abaixo, assinale a alternativa que contém a sequência dos elementos do caminho 'postorder'.

A) 02, 07, 11, 27, 33, 38, 41, 62, 67, 81, 82, 84, 92

B) 82, 92, 84, 62, 67, 81, 33, 38, 02, 11, 07, 27, 41

C) 41, 27, 81, 07, 38, 67, 84, 02, 11, 33, 62, 82, 92

D) 02, 11, 07, 33, 38, 27, 62, 67, 82, 92, 84, 81, 41

E) N.D.A.

Ideia original de: Tiago Pedroso da Cruz de Andrade

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Através da análise do algoritmo da função LCS-LENGTH abaixo, podemos afirmar que o tempo de execução e o espaço auxiliar requerido por este algoritimo são, respectivamente:

LCS-LENGTH(X,Y)
 m = X.length
 n = Y.length
 let c[0 ... MIN(m,n)] be a new table
 for i = 0 to MIN(m,n)
  c[i] = 0
 for i = 1 to MAX(m,n)
  previous = c[0]
  for j = 1 to MIN(m,n)
   if Xi == Yj
    c[j] = previous + 1
   else if c[j] >= c[j - 1]
    previous = c[j]
   else
    previous = c[j]
    c[j] = c[j - 1]
 return c[MIN(m,n)]

A) theta(m + n) e theta(m * n)

B) theta(m + n) e theta(MIN(m,n))

C) theta(m * n) e theta(m + n)

D) theta(m * n) e theta(MIN(m,n))

E) N.D.A.

Ideia original de: Tiago Pedroso da Cruz de Andrade