Número: 033
Enunciado:
Considerando as árvores PQ, assinale a alternativa incorreta:
- Uma árvore PQ que representa 96 permutações possui pelo menos um nó P.
- A altura máxima de uma árvore PQ própria é igual ao número de folhas menos 2.
- A raiz de uma árvore universal é um nó do tipo P.
- Ao se aplicarem reduções sucessivas em uma árvore universal, é possível surgir um nó do tipo Q em qualquer das reduções.
- NDA
1. Verdadeiro.
ResponderExcluirNós Q só possuem duas possibilidades. Invertido ou não. Portanto, o número de permutações de uma árvore que só contivesse nós Q seria uma potência de 2.
Como
96 = 2^5 * 3
deve haver ao menos 1 nó P para permitir um múltiplo de 3.
2. Falso.
O termo "altura" não está precisamente bem definido nessa questão. Poderemos considerar a altura da árvore como a distância da raiz até a folha mais distante, ou podemos considerar a altura como o numero máximo de níveis da árvore.
Porém, o item não é verdadeiro em nenhum desses casos.
Uma árvore simples, com duas folhas, teria altura 1 ou 2, dependendo da definição, e não 0 como o item afirma:
P
a b
3. Verdadeiro.
O nó P permite qualquer permutação de suas folhas. Uma árvore universal possui todos as folhas ligadas a um único nó P.
4. Falso.
Na primeira redução não é possível obter um nó Q. A primeira redução sempre gera um nó P cujos filhos são os itens da restrição.
A questão apresenta portanto dois itens corretos (1 e 3) e dois itens incorretos(2 e 4).
Bons comentários. Refletem bem o que foi discutido em aula.
ResponderExcluir