David Castilho
EQUIPE
23/10/2025 • 02:50
Gabarito: a)
Inicialmente, temos dois vetores A e B, cada um com N elementos ordenados, e a propriedade A[N-1] < B[0], ou seja, todos os elementos de A são menores que todos os elementos de B.
Ao inserir todos os elementos de A e depois de B em uma árvore binária de busca (ABB), a árvore resultante conterá todos os 2N elementos, mantendo a propriedade da ABB: para cada nó, os elementos à esquerda são menores e os da direita são maiores.
O percurso pós-ordem da ABB visita primeiro a subárvore esquerda, depois a subárvore direita e por último a raiz. Ao inserir os elementos retirados do percurso pós-ordem em uma pilha, a ordem dos elementos na pilha será o inverso do pós-ordem.
Ao retirar os elementos da pilha e inseri-los nos vetores A e B, começando pelo índice 0 de A, os elementos serão inseridos em ordem crescente, pois o percurso pós-ordem invertido corresponde a um percurso em ordem crescente dos elementos da ABB.
Portanto, os vetores A e B estarão ordenados, e como originalmente todos os elementos de A eram menores que os de B, essa propriedade será mantida para cada índice i, ou seja, A[i] < B[i] para todo i de 0 a N-1.
Uma segunda análise confirma que a ABB contém todos os elementos ordenados, e o processo descrito reorganiza os elementos em ordem crescente nos vetores, preservando a relação entre os elementos correspondentes dos vetores A e B.
Assim, a alternativa correta é a letra a).
Inicialmente, temos dois vetores A e B, cada um com N elementos ordenados, e a propriedade A[N-1] < B[0], ou seja, todos os elementos de A são menores que todos os elementos de B.
Ao inserir todos os elementos de A e depois de B em uma árvore binária de busca (ABB), a árvore resultante conterá todos os 2N elementos, mantendo a propriedade da ABB: para cada nó, os elementos à esquerda são menores e os da direita são maiores.
O percurso pós-ordem da ABB visita primeiro a subárvore esquerda, depois a subárvore direita e por último a raiz. Ao inserir os elementos retirados do percurso pós-ordem em uma pilha, a ordem dos elementos na pilha será o inverso do pós-ordem.
Ao retirar os elementos da pilha e inseri-los nos vetores A e B, começando pelo índice 0 de A, os elementos serão inseridos em ordem crescente, pois o percurso pós-ordem invertido corresponde a um percurso em ordem crescente dos elementos da ABB.
Portanto, os vetores A e B estarão ordenados, e como originalmente todos os elementos de A eram menores que os de B, essa propriedade será mantida para cada índice i, ou seja, A[i] < B[i] para todo i de 0 a N-1.
Uma segunda análise confirma que a ABB contém todos os elementos ordenados, e o processo descrito reorganiza os elementos em ordem crescente nos vetores, preservando a relação entre os elementos correspondentes dos vetores A e B.
Assim, a alternativa correta é a letra a).