domingo, 13 de fevereiro de 2011

120-2008

MO640 - Questão para a prova oral
Número: 120
Enunciado:
No último passo do algoritmo quase-linear para adição de uma nova restrição a uma árvore PQR, quais são os nós que precisarão ser descoloridos?
  1. Todos os nós P pretos da árvore
  2. Todos os nós P cinzas da árvore
  3. Todos os nós pretos da árvore
  4. Todos os nós cinzas da árvore
  5. NDA
Autor(a): Priscila do Nascimento Biller

Um comentário:

  1. Antes de comentar cada alternativa, é importante ressaltar que deve-se mexer no mínimo de nós possíveis para não estourar a complexidade do algoritmo. Por esta razão, os nós brancos são considerados incolores e não são descoloridos.
    O último passo do algoritmo limpa os estados dos nós mexidos na árvore, inclusive acima do LCA.

    Sobre as alternativas ...

    A alternativa "a" é incorreta, pois todos os nós pretos são descoloridos, independente se é P.

    A alternativa "b" é incorreta, pois o terceiro passo do algoritmo já eliminou todos os nós cinzas.

    A alternativa "c" é a CORRETA, porque no último passo, só restam nós pretos na árvore a serem descoloridos.

    A alternativa "d" é incorreta, pois o terceiro passo do algoritmo já eliminou todos os nós cinzas.

    A alternativa "e" é incorreta, já que a alternativa "c" já foi validada como correta.

    ResponderExcluir