Questão 599701

• Banca: CESGRANRIO
• Órgão: Petrobras
• Ano: 2011
• Provas: CESGRANRIO - 2011 - Petrobras - Analista de Sistemas Júnior - Engenharia de Software
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Estrutura de Dados; Vetores

Dois vetores, v1 e v2, armazenam N inteiros cada um, estão ordenados de forma crescente e têm a propriedade de que o último elemento de v1 (v1[N-1]) é menor que o primeiro elemento de v2 (v2[0]). É retirado um elemento de cada vez de cada um desses vetores alternadamente, e cada elemento retirado é colocado em uma fila. Posteriormente, os elementos são retirados da fila e inseridos em uma árvore binária de busca. A árvore é percorrida em ordem simétrica, e os elementos são inseridos, assim que retirados, em uma pilha. Depois, cada elemento é retirado da pilha e inserido alternadamente em um dos vetores, começando por v1.

Diante do exposto, conclui-se que

• A.
• B.
• C. v1[N-1] > v2[0]
• D. as listas não estão mais ordenadas.
• E. todos os elementos de v1 estão armazenados em v2 e vice-versa.

Gabarito: A

Comentários

•  Alternativas conforme constam na prova
  
  A)     V1[i]≥ v2[i], ∀ =0,1,..., N-1
  B)     V1[i] ≤ v2[i], ∀ =0,1,..., N-1
  C)     V1[N-1] > v2[0]
  D)    as listas não estão mais ordenadas.
  E)      todos os elementos de v1 estão armazenados em v2 e vice-versa.
• É só fazer por partes:
  
  Dois vetores, v1 e v2, armazenam N inteiros cada um, estão ordenados de forma crescente e têm a propriedade de que o último elemento de v1 (v1[N-1]) é menor que o primeiro elemento de v2 (v2[0]).
  
  v1: 1 2 3
  v2: 4 5 6
  
  É retirado um elemento de cada vez de cada um desses vetores alternadamente, e cada elemento retirado é colocado em uma fila.
  (inicio) 1 4 2 5 3 6 (fim da fila)
  
  Posteriormente, os elementos são retirados da fila e inseridos em uma árvore binária de busca.
    1
             4
      2             5
           3              6
  
  A árvore é percorrida em ordem simétrica (esquerda, visita, direita), e os elementos são inseridos, assim que retirados, em uma pilha.
  (topo da pilha) 6 5 4 3 2 1
  
  Depois, cada elemento é retirado da pilha e inserido alternadamente em um dos vetores, começando por v1.
  v1: 6 4 2
  v2: 5 3 1
  
  Resposta: alternativa A
• Apenas complementando os colegas, essa questão tem um macetinho que economizaria muito tempo na hora da prova, então é bom ficar atento aos detalhes. Basicamente, se ele usa uma árvore binária de busca, isso quer dizer que a remoção em ordem simétrica sempre vai retornar dados em odem crescente, independente de como eles foram inseridos. Dessa forma, inserir em uma pilha reverteria a ordem, nos dando uma sequência decrescente (ex: 10, 9, 8, 7, 6, 5). Distribuindo alternadamente começando pelo v1 teríamos:
  v1={10,8,6}
  v2={ 9,7,5}
  Ou seja, v1[i]>v2[i]