Questão 1062634

• Banca: CESGRANRIO
• Órgão: Petrobras
• Ano: 2012
• Provas: CESGRANRIO - 2012 - Petrobras - Analista de Sistemas Júnior - Processos de Negócios-2012
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Estrutura de Dados; Vetores

Existem dois vetores, chamados A e B, que estão ordenados e contêm N elementos cada, respeitando a propriedade A[N-1]<B[0], onde os índices de ambos os vetores vão de 0 a N-1. Retiram-se primeiro todos os elementos de A na ordem em que se apresentam e inserem-se esses elementos em uma árvore binária de busca, fazendo o mesmo depois com os elementos de B, que são inseridos na mesma árvore de busca que os de A. Depois, retiram-se os elementos da árvore em um percurso pós ordem, inserindo-os em uma pilha. Em seguida retiram-se os elementos da pilha, que são inseridos de volta nos vetores, começando pelo elemento 0 do vetor A e aumentando o índice em 1 a cada inserção, até preencher todas as N posições, inserindo, então, os N elementos restantes no vetor B da mesma maneira. 

Ao final do processo, tem-se que os vetores

• A. estão ordenados e A[i] < B[i], para todo i=0,...., N-1.
  
• B. estão ordenados e A[i] > B[i], para todo i=0,...., N-1.
  
• C. estão ordenados e não existe mais uma propriedade que relacione A[i] e B[i].
  
• D. não estão ordenados e A[i] < B[i], para todo i=0,...., N-1.
  
• E. não estão ordenados e A[i] > B[i], para todo i=0,...., N-1.

Gabarito: A

Comentários

• Olá pessoal bom dia!!!

   

  Para melhor entendimento dessa questão, o aluno tem que ter claros conhecimentos a respeito:

   

  Árvore binária de busca (pré-ordem, in-ordem e pós ordem) e valores menores a esquerda e maiores a direita;

  Pilha (LIFO - Last in, First Out).

   

  Vamos lá, organizei dois vetores ordenados, assumindo o que foi dito na questão A[N-1] e coloquei 2 elementos, como exemplo, em cada para não ficarem extensos:

   

  A[1,2] e B[4,5]

   

  Colocando os valores em uma árvore binária de busca, tem-se (VALORES MAIORES SEMPRE A DIREITA DO NÓ RAIZ):

   

  1

    2

      4

         5

   

  Colocando-os numa pilha, assumindo o princípio pos-ordem - EDR (esquerda, direita e raiz) - dito na questão:

   

  Pilha[5,4,2,1]

   

  Assumindo o princípio LIFO da pilha, retiraremos todos os elementos de volta para os dois vetores:

  A[1,2] e B[4,5]

   

  Temos no final de tudo isso os vetores da mesma forma que criamos, então pode-se deduzir que A[i] < B[i]

  Com isso, a resposta é a letra A.

   

  Pessoal, se eu tiver cometido algum equívoco, favor expor seus comentários, pois estamos aqui para que em união possamos aprender numa boa.

   

  Faço esse tipo de comentário, pois eu diariamente também faço uso de diversos bons comentários aqui deixados.

   

  Abraços.

   

  Go ahead!!!!

• A única ressalva que faço quanto ao comentário do Marcelo é no que diz respeito ao percuso pós-ordem. Nesse tipo de percurso, o caminho percorrido é Esquerda - Direita - Raíz, e não Esquerda - Raíz - Direita, que neste caso, seria o percurso em Ordem. No mais, a explicação dele está correta e bem clara. Obrigado!

  Resumindo:

  Pré-ordem: Você deve visitar primeiro a raiz, depois a sub-árvore esquerda e por último a sub-árvore direita. 
  Em-ordem: Você deve visitar primeiro a sub-árvore esquerda, depois a raiz e por último a sub-árvore direita. 
  Pós-ordem: Você deve visitar primeiro a sub-árvore esquerda, depois a sub-árvore direita e por último a raiz. 

   

   

• Força Guerreiro!!!!!!