SóProvas

ID
5437
Banca
CESGRANRIO
Órgão
Petrobras
Ano
2006
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Insira as chaves {Lina, Ana, Lia, Ada, Lua, Sol, Cris, Bia, Rita, Mel, Rosa, Val} em uma árvore binária de busca (considere que a árvore está inicialmente vazia). Considere agora, a execução dos seguintes percursos sobre a estrutura após a inserção das chaves.

I - Um percurso em pré-ordem seria: { Ada, Bia, Cris, Lia, Ana, Mel, Rosa, Rita, Val, Sol, Lua, Lina}

II - Um percurso em ordem simétrica seria: {Val, Sol, Rosa, Rita, Mel, Lua, Lina, Lia, Cris, Bia, Ana, Ada}

III - Um percurso em nível seria: {Lina, Ana, Lua, Ada, Lia, Sol, Cris, Rita, Val, Bia, Mel, Rosa}

IV - Um percurso em pós-ordem seria: {Lina, Ana, Ada, Lia, Cris, Bia, Lua, Sol, Rita, Mel, Rosa, Val}

Estão corretos apenas os percursos indicados em:

Alternativas
Comentários
  • Pré-order: root, then left sub-tree, then right sub-tree
    Post-order: then left sub-tree, then right sub-tree, root
    symetric order: left sub-three, root, then right sub-tree
  • Os percursos em pré-ordem e pós-ordem estão invertidos (I é um percurso em pós-ordem e IV é um percurso em pré-ordem). Os outros dois estão corretos.
  • 1º) Ordenar alfabeticamente os nomes.2º) Substituir os nomes ordenados por números (1,2,3,4,5,6,7,8,9,10,11,12).3º) Substituir pelos números os nomes da lista original, ficando assim (6,2,5,1,7,11,4,3,9,8,10,12) onde 6 é Lia, 2 é Ana, 5 é Lia e assim por diante.4º) Distribuir na árvore binária lembrando que, se um número é menor que raiz ele fica a esquerda se é maior fica a direita e assim o número vai descendo os níveis tomando a direita ou esquerda do nó seguinte até se tornar folha (nó sem filho)IMAGEM DA ÁRVORE: http://img405.imageshack.us/img405/4049/screenhunter002.gifCom isso temos:I) ERRADO: na Pré Ordem comecaria pelo raiz (6) LinaII) CERTO: Se considerarmos que este percurso simetrico comecou pela esquerdaIII) CERTO: De cima para baixo da esquerda para a direitaIV) ERRADO: na Pós ordem o primeiro item seria (1) Ada.
  • O percurso simétrico (in ordem): E - D - V sempre retorna as chaves em ordem crescente.... Portanto o item 2 estaria errado. Na minha opnião esta questão deveria ter sido anulada.
  • também não concordo que o item II esteja correto. Ele está mostrando os elementos em ordem decrescente, o que nãocaracteriza a ordem simétrica.
  • Árvore Resultante:


    Pré-Ordem:     LINA ANA ADA LIA CRIS BIA LUA SOL RITA MEL ROSA VAL
    IN-Ordem:       ADA ANA BIA CRIS LIA LINA LUA MEL RITA ROSA SOL VAL
    POS-ORDEM: ADA ANA BIA CRIS LIA MEL ROSA RITA VAL SOL LUA LINA

    Simétrico: Já respondido no Ítem 2 (Segue a lógica: Da direita para a esquerda, visitando o PAI. Se filho esquerdo tem filho, visita o filho mais a direita, depois o seu Pai, e assim por diante.) Olhem a ilustração para facilitar o entendimento:

    Nível: Respondido item 3(Basta pegar de cima para baixo olhando a árvore resultante.

  • A questão deveria ser anulada pois o item II não está em ordem,(está invertido) . Quanto ao percurso em nível eu nunca ouvi falar , mas pela explicação do colega Leonardo eu tive uma idéia do que seja. A propósito na minha resolução em pós ordem ANA vem depois de LIA . Como não pude identificar nenhuma que estivesse correta, eu marcaria a b , pois apesar de invertida a ordem do item II bate, e eu não sei o percurso em nível mais sei que os outros itens estão incorretos.
  • Questãozinha complicada de se desenhar numa prova! A sugestão do amigo Ricardo de transformar em números é ótima! Depois de aplicar essa sugestão e de ver o link dele do desenho da árvore consegui matar a questão.
    O percurso em-ordem é sub-árvore esquerda, raiz e sub-árvore direita, mas na questão tem que ser usado o invertido (em-ordem simétrica). Por isso o item II está correto.
    A questão é muito boa para reforçar os conhecimentos sobre árvore de busca binária!

  • O comentário dessa questão está detalhadamente no link abaixo , página 13:

    https://issuu.com/liberbooksbr/docs/quest__es_comentadas_de_ti_para_con_9e2cd361f37179

  • A maneira mais fácil que eu encontrei pra fazer essa questão sem ter que montar toda a arvore em tabela alfabética é a seguinte:

    1 - Toda arvore binária criada do zero começa com o primeiro termo inserido

    ( com isso, sabemos que Lina é a raiz da árvore)

    2-Todo percurso Pré-Ordem começa com a Raiz da árvore, que seria Lina

    ( Isso já descarta a I , logo ACD estão erradas )

    Entre B e D, a única alternativa distinta entre ela é a IV

    3- Analisando IV:

    Sabe-se que percurso Pós-Ordem não começa com a raiz da árvore

    ( logo a IV está falsa pq sabemos que Lina é a Raiz da Arvore )

    Gabarito: B

    Assista esse vídeo que vc NUNCA MAIS vai esquecer como é feito os percursos(Pré-Ordem, In Ordem, Pós-Ordem)

    https://www.youtube.com/watch?v=OvMuKaG4Qhk&ab_channel=NetupProvedor

  • Questão errada, a única alternativa correta é a alternativa 3, que fala da busca em nível. Quanto a ordem simétrica, é a mesma coisa que o percurso in-order: E,R,D, a qual retornaria as chaves em ordem.