Numero:
Bob e Alice gostariam de troca mensagens entre eles sem que outras pessoas soubessem, assim eles estipularam o seguinte protocolo:
1. Converter toda a mensagem em representação numérica, ex: letra "A" se transforma 42.
2. Insere todas os números em uma árvore Red/Black
3. Definem em segredo qual número será a raiz e um caminhamento para a leitura desta árvore.
Desta forma, Bob envia para Alice o caminhamento pós-ordem da árvore, entretanto a mensagem, que nunca contém letras repetidas, só pode ser entendida caso seja feito o caminhamento inter-ordem para os nós a esquerda da raiz e pre-ordem para os nós a direita da raiz.
Em relação a uma algoritmo que implementaria essa pequena confusão na mensagem, é correto afirmar.
I. Só seria atingido o balanceamento ótimo da árvore caso a mensagem fosse ordenada, com o elemento na posição mediana sendo a raiz.
II. Custo de realizar todos os três caminhamentos na árvore será sempre o mesmo independente do balanceamento da árvore.
III. A mensagem {12,9,47,27,11,5} é válida para Bob e Alice
IV. Caso Bob enviasse [a,b...z], para Alice, todas as varreduras resultariam na mesma mensagem, dado que a arvore seria uma "tripa", ou com todos os nós a direta do pai.
a. I e III
b. II e IV
c. I e IV
d. II
e. N.D.A
Ideia original de: Otávio Augusto Araújo Silva
Nenhum comentário:
Postar um comentário