SóProvas

Questões de Árvores

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.

ID
868393
Banca
CESPE / CEBRASPE
Órgão
TRE-MS
Ano
2013
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Acerca de tipos básicos de estruturas de dados, assinale a opção correta.

Alternativas
Comentários
  • Gabarito: letra e)

    Apesar de ter acertado (pois é a opção mais próxima do que seria uma informação correta), discordo da veracidade de parte da assertiva. Vejamos:

    " e) Árvores são grafos dirigidos mais específicos que os acíclicos, em que existe um nó raiz a partir do qual os demais vértices podem ser acessados e onde cada vértice, exceto o raiz, possui apenas um nó antecessor. "

    Opa! Árvores são grafos NÃO DIRIGIDOS. Vejamos o que diz o material de um professor da UFCG:

    "Uma árvore (livre) é um grafo acíclico, não orientado e conectado... "
    Fonte: http://www.dsc.ufcg.edu.br/~abrantes/CursosAnteriores/TG051/arvores.pdf

  • exceto o raiz, possui apenas um nó antecessor. 


    Que eu saiba a raiz não possui nenhum nó antecessor

  • Geraldo, temos um impasse. Em [1], temos:

    “As árvores são grafos dirigidos mais específicos que os acíclicos, onde existe um nó inicial, chamado raiz, a partir do qual os demais vértices podem ser acessados. Cada vértice, exceto o vértice raiz, tem apenas um nó antecessor" (meu grifo).

    Podemos ver que a letra E foi baseada nesse texto.

    Referência:

    [1] LOPES, Arthur Vargas. Estrutura de Dados para a construção de software. Volume 2 – Nível Intermediário. 1ª Edição. Editora da ULBRA, 1999.

    https://books.google.com.br/books?id=RVWwHdfNGp4C&pg=PA19&lpg=PA19&dq=%C3%A1rvores+s%C3%A3o+grafos+dirigidos+mais+espec%C3%ADficos+que+os+ac%C3%ADclicos&source=bl&ots=TZQttgWkU_&sig=CTH1t8D5BJ5KClfKZU_nQes94Tk&hl=pt-PT&sa=X&ved=0ahUKEwj287HIievJAhXHQZAKHTUvDygQ6AEIITAB#v=onepage&q=%C3%A1rvores%20s%C3%A3o%20grafos%20dirigidos%20mais%20espec%C3%ADficos%20que%20os%20ac%C3%ADclicos&f=false

  • Leandro Eiró, é justamente isso que a questão quis dizer. O "exceto o raiz" exclui a raiz dos campos que possuem nó antecessor. Ele está se referindo aos "Demais vértices".


    Abs.

  • a) Uma estrutura do tipo pilha, também conhecida como stack, permite que as operações sejam realizadas em seu topo a partir do primeiro elemento inserido por meio de acesso FIFO (first in first out) LIFO (LAST-IN-FIRST-OUT).

     

    b) os grafos AS PILHAS se assemelham às filas em termos de estrutura, mas, enquanto nas filas PILHAS as operações são realizadas no topo, nos grafos NAS FILAS elas podem ser realizadas tanto no início quanto no fim da estrutura”.

     

    d) Nas estruturas do tipo árvores PILHAS, as operações push( ) e pop( ) permitem INSERIR retirar e RETIRAR inserir nós, respectivamente.

  • Força Guerreiro!!!!!!

ID
1178020
Banca
CESGRANRIO
Órgão
Banco da Amazônia
Ano
2014
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Suponha uma árvore de pesquisa binária com números entre 10 e 200.

Se procurarmos pelo número 50, a única sequência válida de números visitados é:

Alternativas
Comentários
  • Todos os valores devem ser superiores ao nó raiz. Apenas a letra D satisfaz essa condição.

  • a) tem o numero 300

    b) raiz 40, então 50 estará a direita. e todos os numero seguintes deverão ser maiores que 40, mas 21 é menor, não pertencendo a subárvore direita, mas a esquerda.

    c) raiz 80, então 50 estará à esquerda, e todos o numero seguintes deverão ser menores que 80. 11 é menor, então 50 estará a direita de 11 e todos os numeros seguintes maiores que 11. 37 menor, então 50 estará a direita de 37 e todos os numeros seguintes deverão ser maiores que 37. 25 < 37, não deve estár no caminho em busca de 50, que é um numero maior.

    d)raiz 85: busca na sub esquerda, pois 50 <80. 11: busca na sub direita, pois 50 > 11. 76: busca na sub esquerda, pois 50 < 76. 33: busca na sub direita, pois 33 < 50. 50!

    e) buscar por 50 começando por 86, significa que os numeros seguintes deverão estar entre 86 e 50. 100 não está!

  • Força Guerreiro!!!!!!

ID
1208257
Banca
CESPE / CEBRASPE
Órgão
TJ-SE
Ano
2014
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Com relação a estruturas de dados e árvores, julgue os próximos itens.

Em uma árvore AVL (Adelson-Velsky e Landis), caso a diferença de altura entre as sub-árvores de um nó seja igual a 2 e a diferença de altura entre o nó filho do nó desbalanceado seja igual a -1, deve-se realizar uma rotação dupla com o filho para a direita e o pai para a esquerda a fim de que a árvore volte a ser balanceada.

Alternativas
Comentários

  • Concordo que seria uma rotação dupla. Porém, ele não disse qual árvore está desbalanceada (direita ou esquerda). Logo, el enão pode dizer que o filho vai para a direita e o pai para a esquerda.

  • Rosana, eu acho que é o seguinte:


    Primeiro ele afirma que a diferença de altura do nó pai para o nó desbalanceado é 2 ( árvore da direita do nó pai [2] - árvore da esquerda do nó pai [0] = 2 )

    Depois ele afirma que a diferença de altura do nó filho do nó desbalanceado é igual a -1 ( árvore da direita do nó filho [0] - árvore da esquerda do nó filho [1] = -1 )


    Ficou:


             Pai

    Filho

           Desb.


    Balanceando faz uma rotação dupla


    1° 

            Pai

       Desb

    Filho


    2º 

               Desb

    Filho              Pai



    Portanto, filho ficou na direito e o pai ficou na esquerda.


    Acho que é isso, bons estudos

  • Rotação dupla à direita

     

    Deve ser efetuada quando a diferença das alturas h dos filhos de P é igual a 2 e a diferença das alturas h dos filhos de FE é igual a -1. Nesse caso devemos aplicar uma rotação à esquerda no nó FE e, em seguida, uma rotação à direita no nó P.

     

    fonte: https://pt.wikipedia.org/w/index.php?title=%C3%81rvore_AVL§ion=18#Rota.C3.A7.C3.A3o_dupla_.C3.A0_direita

  • Olá meus queridos colegas de auditório!

    Infelizmente o CESPE deu essa assertiva como CORRETA... Vi outros guerreiros de auditório questionando essa afirmativa em alguns sites e realmente o final dela está COMPLETAMENTE EQUIVOCADO, vejam:

     

    Em uma árvore AVL (Adelson-Velsky e Landis), caso a diferença de altura entre as sub-árvores de um nó seja igual a 2 e a diferença de altura entre o nó filho do nó desbalanceado seja igual a -1, deve-se realizar uma rotação dupla (ATÉ AQUI CORRETO) com o filho para a direita e o pai para a esquerda (ERRADO... trocou as bolas) a fim de que a árvore volte a ser balanceada.

     

     

    O CESPE propôs isso (a forma do "JOELHO"): --> Pai só com nó esquerdo, Filho só com nó direito

     

                     PAI (+2)

    FILHO (-1)

                    NÓ DIREITO FILHO  (0)

     

     

    Lembrando que em uma árvore AVL, para qualquer nó, as alturas de suas duas subárvores, esquerda e direita, diferem em módulo de até uma unidade. Então no caso proposto pelo CESPE realmente precisamos utilizar rotações para voltar ao equilíbrio (não pode ter um nó +2).

    Nesse caso realmente aplicamos uma ROTAÇÃO DUPLA (forma de "joelho", sinais diferentes +2, -1).

    (PRA QUEM NÃO ESTÁ ENTENDENDO DIREITO, OU QUISER APRIMORAR ESSES CONCEITOS, ESSE VÍDEO É MUITO BOM: https://www.youtube.com/watch?v=JAeQuNsKQWk)

     

     

    Bom agora vamos para as rotações utilizadas para o equilíbrio e percebam o ERRO GROSSEIRO do CESPE:

    1) Primeira Rotação -->  FILHO para ESQUERDA

     

                           PAI (+2)

              NÓ DIREITO FILHO (+1)

    FILHO (0)

     

     Rodando o filho pela esquerda voltamos a ter uma reta (sinais iguais), porém ainda em desiquilíbrio! 

       

            

    2) Segunda Rotação -->  PAI para DIREITA

     

                  NÓ DIREITO FILHO (0)

    FILHO (0)                                     PAI (0)

     

    Pronto, alcançamos o equilíbrio na AVL (todos aqui estão com fator de balanceamento 0!).

     

     

    CONCLUINDO: Ao contrário do que o CESPE escreveu, na rotação, o FILHO vai para ESQUERDA, depois o PAI vai para DIREITA.

    Não sou nenhum EINSTEIN em Estrutura de Dados (tanto que minha especialidade é vender carnês do baú), e apesar de gostar da banca, infelizmente percebo nas diversas questões do tema que os examinadores do CESPE são muito fracos em estrutura de dados...

    Não podemos deixar gabaritos absurdos como esse passar, nas próximas vamos todos "fazer chover" de recursos!

     

     

    Continuem persistindo, forte abraço, fiquem com Deus, e não se esqueçam de comprar a Nova TeleSena de Natal, suas chances de ganhar 1 milhão dobraram

  • ÁRVORES AVL

     Uma árvore binária T é denominada AVL quando todos os seus nós estão regulados.
     O nó de uma árvore binária é considerado regulado quando as alturas de suas subárvores esquerda e direita diferem em até uma
    unidade. Caso contrário, consideramos que o nó esta desregulado.

     Um nó regulado tem fator de balanceamento igual a: -1, 0 ou 1.

     

    Fonte: Provas de TI

  • CERTO

    A princípio dei a questão como errada, porém há um peguinha nela.

    Notem que o CESPE usa a fórmula Altura da Sub-Árvore à Direita - Altura da Sub-Àrvore à Esquerda, sendo que o usual é usarmos a fórmula contrário ASAE - ASAD. As duas fórmulas produzem o mesmo resultado no final, uma árvore balanceada, então uma não é mais certa do que a outra.

    Baseado nisso podemos dizer que o Lado Direito da Árvore está desbalanceado e partir daí usamos o raciocínio do SS Concurseiro, mudando a apenas do formato do Joelho:

    10 10

    7 -> 13

    9 12

    A questão descreve a situação apresentada na segunda árvore, logo a resposta está correta.

  • A questão está correta, a CESPE não inverteu a fórmula de cálculo de balanceamento, a fórmula original segundo o autor é: FB(n) = H(D) - A(E), ou seja, é altura da sub árvore DA DIREITA menos altura da sub árvore DA ESQUERDA, e não ao contrário, NÃO EXISTE ISSO DE USUAL, EXISTE O QUE É REALMENTE DEFINIDO PELO AUTOR QUE CRIOU O ALGORITMO. Dessa forma, considerando os números dos desbalanceamento que a questão informou isso vai formar uma sub-árvore da direita desbalanceada (número 2). Logo é realizada uma rotação a direita e esquerda para balancear.

  • Força Guerreiro!!!!!!

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

Os percursos em profundidade de uma árvore binária, conhecidos como pré-ordem e pós-ordem, são, respectivamente

Alternativas
Comentários

  • Bizu:

    Pré-Ordem: Raiz, Esquerda, Direita (RED)

    Em-Ordem: Esquerda, Raiz, Direita (ERD)

    Pós-Ordem: Esquerda, Direita, Raiz (EDR)


  • Gabarito B

    Pré-Ordem: Raiz, Esquerda, Direita 

    Em-Ordem: Esquerda, Raiz, Direita 

    Pós-Ordem: Esquerda, Direita, Raiz 

     

     

    "Retroceder Nunca Render-se Jamais !"
    Força e Fé !
    Fortuna Audaces Sequitur !

  •  Percurso Pré Ordem: Raiz, Sub-Árvore esquerda, Sub-Árvore Direita

    Percurso Pós Ordem: Sub-Árvore esquerda, Sub-Árvore Direita, Raiz

    Percurso Ordem: Sub-Árvore esquerda, Raiz, Sub-Árvore Direita

  • PRÉ ORDEM - RAIZ,  Sub-Árvore ESQUERDA,  Sub-Árvore DIREITA

    IN ou ORDEM -  Sub-Árvore ESQUERDA , RAIZ,  Sub-Árvore DIREITA

    PÓS ORDEM - Sub-Árvore ESQUERDA , Sub-Árvore DIREITA, RAIZ

  • Força Guerreiro!!!!!!

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

A sequência de chaves 20 – 30 – 25 – 31 – 12 – 15 – 8 – 6 – 9 – 14 – 18 é organizada em uma árvore binária de busca. Em seguida, a árvore é percorrida em pré-ordem.


Qual é a sequência de nós visitados?

Alternativas
Comentários

  • Resposta - B

     

    A árvore é formada com o primeiro elemento sendo a raiz (20). A partir disso, os menores elementos ( elemento < 20)  vão para a esquerda e maiores (elemento > 20) vão para a direita.

     

    .......................................[20]....................................

    .................[12].........................................[30]..........

    .......[8]....................[15].................[25]...........[31].

    ..[6].....[9].........[14].....[18].....................................

     

     

    Ao percorrer a árvore em PRÉ-ORDEM, a sequência fica VISITA o elemento, ESQUERDA e DIREITA.

    20 – 12 – 8 – 6 – 9 – 15 – 14 – 18 – 30 – 25 – 31 

     

     

     

    Além disso, pode-se percorrer uma árvore em:

     

    ORDEM - ESQUERDA, VISITA e DIREITA

    PÓS-ORDEM - ESQUERDA, DIREITA E VISITA

     

     

    @papirobizurado

  • Gabarito B

    Ótima resposta do amigo companheiro Victor Carlos ! Parabêns amigão !!!

     

    Vamos na fé !

     

    "Retroceder Nunca Render-se Jamais !"
    Força e Fé !
    Fortuna Audaces Sequitur !

  • A melhor aula de todos os tempos sobre o assunto, quem assistir nunca mais erra. Não recomendo muito a mulheres e menores de idade. Infelizmente,  essa foi a única forma de ensinar da forma mais intuitiva.

     

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

  • Victor carlos : como se sabe que o 20 seria a raiz da arvore ??

  • Kratos Silva ele escolheu o 20 como nó raiz pois é a sequência já dada na questão, daí começa-se a montar a árvore apartir dele.

  • Percursos em árvores binárias – Pré-ordem

    � O percurso pré-ordem segue recursivamente os seguintes passos para cada subárvore da árvore:
       � Visitar a raiz
       � Percorrer a subárvore esquerda em pré-ordem
       � Percorrer a subárvore direita em pré-ordem

     

    Fonte: Provas de TI

     

     

  • e se fosse pós ordem?

  • •[A] 6 – 9 – 8 – 14 – 18 – 15 – 12 – 25 – 31 – 30 – 20 Pós-ordem

    •[B] 20 – 12 – 8 – 6 – 9 – 15 – 14 – 18 – 30 – 25 – 31 Pré-ordem

    •[C] 6 – 8 – 9 – 12 – 14 – 15 – 18 – 20 – 25 – 30 – 31 Em-ordem

  • Força Guerreiro!!!!!!

ID
2724589
Banca
FUNDEP (Gestão de Concursos)
Órgão
CODEMIG
Ano
2018
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Referente à UML (unified modeling language), analise as seguintes afirmativas e assinale com V as verdadeiras e com F as falsas.

( ) O fator de ramificação de uma árvore pode variar entre pequeno e grande. B-árvores são árvores de busca balanceadas projetadas para funcionar em discos ou outros dispositivos de armazenamento secundário.
( ) Muitos sistemas de banco de dados usam B-árvores ou variantes para armazenar informações. B-árvores generalizam árvores de busca binária de modo natural.
( ) Executar uma busca em uma B-árvore é muito semelhante a executar uma busca em uma árvore de busca binária, exceto que, em vez de tomar uma decisão de ramificação binária ou de “duas vias” em cada nó, toma-se uma decisão de ramificação de várias vias, de acordo com o número de filhos do nó.
( ) Para simplificar, pode ser considerado que, nas árvores de busca binária, qualquer informação-satélite associada a uma chave reside em nós diferentes da chave. Pode-se armazenar com cada chave vários ponteiros para uma outra página de disco que contenha as informações satélites da chave.

Assinale a sequência CORRETA .

Alternativas
Comentários

  • que diabo isso tem a ver com uml?

  • Nada (a ver com UML).

    Provavelmente na prova ou na transcrição para o QC, o pré-enunciado ficou com esse erro "Referente à UML", e consequentemente a classificação do QC também ficou.

    Deveria estar em Tecnologia-da-informacao -> algoritmos-e-estrutura-de-dados -> estrutura-de-dados -> árvores.

     

  • Quem não tem acesso:  - -> C

  • Reportem essa questão como sendo de banco de dados.

  • Saudades quebra de linha

  • O enunciado da questão está errado, no entanto, todas as alternativas são referentes a conteúdos sobre árvores.

  • Força Guerreiro!!!!!!

ID
2768236
Banca
FAURGS
Órgão
TJ-RS
Ano
2018
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

__________ é um tipo específico de __________ em que os elementos só podem ser inseridos e retirados de uma das extremidades. Utilizamos uma __________ para armazenar dados segundo uma determinada chave de ordenação, que são submetidos com frequência à ___________ de elementos.

Assinale a alternativa que preenche correta e respectivamente as lacunas do parágrafo acima.

Alternativas
Comentários

  • Gabarito E

    PILHA é um tipo específico de LISTA em que os elementos só podem ser inseridos e retirados de uma das extremidades. Utilizamos uma ÁRVORE BINÁRIA para armazenar dados segundo uma determinada chave de ordenação, que são submetidos com frequência à PESQUISA de elementos. 

    Assinale a alternativa que preenche correta e respectivamente as lacunas do parágrafo acima.

    "Retroceder Nunca Render-se Jamais !"

    Força e Fé !

    Fortuna Audaces Sequitur !

  • "inseridos e retirados de uma das extremidades" == Pilha

    Deu pra matar a questão com esse trecho da afirmação

  • Força Guerreiro!!!!!!

ID
2771590
Banca
CS-UFG
Órgão
SANEAGO - GO
Ano
2018
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Uma profissional de TI precisa carregar uma grande quantidade de registros de pessoas. O uso mais constante desta estrutura será relacionado ao filtro das entradas pelo prefixo do nome das pessoas. Sabendo deste caso de uso, qual é a melhor escolha de estrutura de dados para facilitar essa filtragem?

Alternativas
Comentários

  • Gab: "C"  Arvore..  (para quem consulta so gabarito)

  • TABELA HASH:  uma tabela de dispersão (também conhecida por tabela de espalhamento ou tabela hash, do inglês hash) é uma estrutura de dados especial, que associa chaves de pesquisa a valores. Seu objetivo é, a partir de uma chave simples, fazer uma busca rápida e obter o valor desejado. PORTANTO, NÃO PODERIA SER O ÍTEM D, POIS A CONSULTA NÃO SERIA POR UM ÍTEM ESPECÍFICO, E SIM POR UM CONJUNTO/REGISTRO  DE POSSÍVEIS NOMES DE PESSOAS.

  • Gabarito C

    Matei a questão com a palavra prefixo, rapidamente me veio na cabeça os nós da arvore.

    Vamos na fé !

    "Retroceder Nunca Render-se Jamais !"

    Força e Fé !

    Fortuna Audaces Sequitur !

  • Árvore patricia

  • Força Guerreiro!!!!!!

ID
2789584
Banca
CCV-UFC
Órgão
UFC
Ano
2016
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Com relação à uma árvore binária de busca, assinale a alternativa correta.

Alternativas
Comentários

  • Quem não tem acesso: --> D

  • Gabarito D

    Em Ciência da computação, uma árvore binária de busca (ou árvore binária de pesquisa) é uma estrutura de dados de árvore binária baseada em nós, onde todos os nós da subárvore esquerda possuem um valor numérico inferior ao nó raiz e todos os nós da subárvore direita possuem um valor superior ao nó raiz (esta é a forma padrão, podendo as subárvores serem invertidas, dependendo da aplicação).

    O objetivo desta árvore é estruturar os dados de forma a permitir busca binária.

    "Retroceder Nunca Render-se Jamais !"

    Força e Fé !

    Fortuna Audaces Sequitur !

  • Ao percorrer uma árvore fazemos uma visita sistemática em cada

    um de seus nós.

    A seguir as principais formas de se percorrer os nós de uma

    árvore binária: Em-ordem, pré-ordem, pós-ordem.

    Ou seja, há sim uma ordem pré-definida a ser seguida.

    Gabarito: D

  • a) 0, 1 ou 2 filhos

    b) A complexidade é menor ou igual

    c) Árvore binária de busca não precisa ser cheia nem completa

    d) Para ser uma árvore binária de busca, precisa ser ordenada

    e) Isso é em relação a um árvore binária genérica, não a de busca

  • Pequena correção no comentário do colega Leandro:

    Alternativa A: Uma arvore binaria de busca pode ter 0 ou 2 filhos.

  • Força Guerreiro!!!!!!

ID
2839405
Banca
FADESP
Órgão
IF-PA
Ano
2018
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Sejam [3, 1, 2, 7, 5, 4, 6], [3, 1, 2, 6, 4, 5, 7] e [4, 2, 1, 3, 6, 5, 7] as sequências produzidas pelo percurso em pré-ordem das árvores binárias de busca T1, T2 e T3, respectivamente, é correto afirmar que é(são) árvore(s) balanceada(s) do tipo AVL (Adelson-Velski e Landis)

Alternativas
Comentários

  • Não entendi pq a arvore t2 , está na resposta montando sua estrutura e depois percorrendo em pre ordem não consegui chegar a essa ordenação, o t1 realmente nao eh um t1, o t3 em pré-ordem bate certinho. Questão complicada de entender.

  • Essa questão tá sem coerência. Não tem como dizer que o T2 é uma árvore binária balanceada.

  • Gabarito, letra D

    Primeiramente devemos entender qual a sequência de pré-ordem que seria:

    Visitar a raiz;

    Percorrer sua subárvore esquerda, em pré-ordem;

    percorrer sua subárvore direita, me pré-ordem;

    Seguindo a percurso de pré-ordem em árvores binárias (maiores valores para subárvores direita e menores para subárvores esquerda. Lembrando que para ser uma árvore AVL, precisa ser uma árvore binária de busca onde seu Fator de Balanceamento - FB (diferença em altura da subárvore da direita pela esquerda) seja no máximo 1. :

    Agora construímos a árvore T1 [3, 1, 2, 7, 5, 4, 6]:

    ...........................................................3.................................... FB = +1 (3 - 2)

    ..................................................../.............. \....

    FB = +1 (1 - 0)........................1..................7 ......................... FB = -2 (0 - 2)

    ...................................................\................/....

    FB = 0 (folha).............................2............5............................. FB = 0 (1 - 1)

    ............................................................./..........\...

    FB = 0 (folha)...................................4.............6.......................FB = 0 (folha)

    Não é uma AVL pois, FB da subárvore 7 > 1

    Agora construímos a árvore T2 [3, 1, 2, 6, 4, 5, 7]

    ...........................................................3.................................. FB = +1 (3 - 2)

    ..................................................../.............. \...

    FB = +1 (1 - 0)........................1...................6 ..................... FB = -1 (1 - 2)

    ...................................................\............../........\..

    FB [2] = 0 (folha)... ....................2.........4............7............... FB [7] = 0 (folha)

    FB [4] = +1 (1 - 0)...................................\...

    ..................................................................5...........................FB = 0 (folha)

    É uma AVL pois todas FB das subárvores são no máximo +1

    o mesmo se segue para a árvore T3 [4, 2, 1, 3, 6, 5, 7]

    ...........................................................4................................. FB = 0 (2 - 2)

    ..................................................../.............\...

    FB = 0 (1 - 0)........................2....................6 .................... FB = 0 (1 - 1)

    ............................................/.......\............../........\..

    FB [1,3] = 0 (folhas).........1..........3..........5..........7............... FB [5,7] = 0 (folhas)

    fonte: Estrutura de dados e seus algoritmos, Jayme Szwarcfiter. 3ª Ed.

    instagram: @papirobizurado

  • Gabarito = D

    Uma árvore binária T é denominada AVL quando, para qualquer nó de T, as alturas de suas duas subárvores, esquerda e direita, diferem em módulo de até uma unidade.

    Fonte: Wikipédia

  • Usem esse simulador, é possível ver claramente que as árvores T2 e T3 estão balanceadas.

    https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

  • Dica para chegar na resolução: (1) ele disse que as árvores são binárias; (2) ele disse que a busca em PRÉ-ORDERM produziu os elementos que estão no vetor. Dessa forma, o primeiro elemento do vetor vai ser a raiz da árvore (pois a busca foi pré-ordem); (3) descobrindo-se a raiz, basta apenas montar a árvore toda e verificar quais delas estão balanceadas. Resposta T2 e T3.

  • Força Guerreiro!!!!!!

ID
2839408
Banca
FADESP
Órgão
IF-PA
Ano
2018
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Sobre as árvores balanceadas do tipo vermelho-preto, é correto afirmar que

Alternativas
Comentários

  • Algumas propriedades da Árvore red black:


    *Um nó é vermelho ou preto.

    *A raiz é preta. (Esta regra é usada em algumas definições. Como a raiz pode sempre ser alterada de vermelho para preto, mas não sendo válido o oposto, esta regra tem pouco efeito na análise.)

    *Todas as folhas(nil) são pretas.

    *Ambos os filhos de todos os nós vermelhos são pretos.

    *Todo caminho de um dado nó para qualquer de seus nós folhas descendentes contem o mesmo número de nós pretos.

  • https://www.slideshare.net/KholtarRasklof/rvores-rubro-negras

  • 1. Todo nó é vermelho ou preto

    2. A raiz é preta

    3. Toda folha (Nil) é preta

    4. Se um nó é vermelho, então os seus filhos são pretos

    5. Para cada nó, todos os caminhos do nó para folhas

    descendentes contém o mesmo número de nós PRETOS.

    Quanto à raiz: Ser sempre preta é uma regra usada em

    algumas definições. Como a raiz pode sempre ser

    alterada de vermelho para preto, mas não sendo válido o

    oposto, esta regra tem pouco efeito na análise.

    Resposta letra D

  • Força Guerreiro!!!!!!

ID
2839411
Banca
FADESP
Órgão
IF-PA
Ano
2018
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Considere uma árvore Patricia construída para armazenar as seguintes chaves: A = 011001; B = 110010; C = 100101; D = 001011; E = 011010; F = 110101. A altura da árvore Patricia resultante, considerando-se sua raiz no nível zero, é

Alternativas
Comentários

  • Gabarito, letra B

    Primeiramente transforma os valores binários em decimais, para facilitar a visualização:

    .........32........16........8.........4.........2..........1

    A=.... 0.........1..........1.........0..........0..........1 = 25

    B=....1..........1..........0.........0..........1..........0 = 50

    C=....1..........0..........0.........1..........0..........1 = 37

    D=....0..........0..........1.........0..........1..........1 = 11

    E=....0..........1..........1.........0..........1..........0 = 26

    F=....1..........1..........0.........1..........0..........1 = 53

    Agora construímos a árvore onde os maiores valores são encaixados nas subárvores direita e os menores nas subárvores esquerdas, que fica:

    ......................................25........................................................ Raiz = 0

    ................................/........... \....................................................

    .............................11 ............50 ...............................................altura = 1

    ........................................./............\...........................................

    .....................................37...............53..................................... altura = 2

    ..................................../............................................................

    .................................26........................................................... altura = 3

    A altura de uma árvore é a distância de sua raiz (0) até a o seu nó folha (nó sem filhos) mais distante, no caso 3.

    fonte: Estrutura de dados e seus algoritmos, Jayme Szwarcfiter. 3ª Ed.

    instagram: @papirobizurado

  • Gabarito B

    Excelente explicação do companheiro Irvin BM !

    "Retroceder Nunca Render-se Jamais !"

    Força e Fé !

    Fortuna Audaces Sequitur !

  • A inserção na árvore Patricia (Compressed Trie) é realizada a partir dos bits. Assim, após as duas primeiras inserções, a árvore fica:

    ...................................RAIZ....................................................... Raiz = 0

    ................................/........... \....................................................

    .........................011001 ....110010 ............................................altura = 1

    Isso porque pelo bit 0 a inserção ocorre à esquerda; pelo bit 1 à direita. A terceira inserção (100101) começa pelo bit 1. Assim ocorrerá a divisão do lado direito da árvore, que fica assim:

    ...................................RAIZ....................................................... Raiz = 0

    ................................/........... \....................................................

    .........................011001..........1.................................................altura = 1

    ........................................./............\...........................................

    ...................................00101.....10010..................................... altura = 2

    A árvore final fica da seguinte forma:

    ...................................RAIZ....................................................... Raiz = 0

    ............................/.................... \...............................................

    ...........................0......................1.............................................altura = 1

    ....................../..........\.........../............\.......................................

    ................01011......110....00101.......10................................... altura = 2

    .............................../......\................./........\................................

    .............................01......10..........010......101............................altura = 3

  • Força Guerreiro!!!!!!

ID
2926549
Banca
Quadrix
Órgão
CRA-PR
Ano
2019
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

No que se refere a vetores, matrizes, filas e árvores binárias, julgue o item.


Em uma árvore binária, nem os nós da direita nem os da esquerda podem possuir valores superiores ao nó do pai. 

Alternativas
Comentários

  • Errado

    Em uma árvore binária temos o nó raiz e os nós da direita e esquerda, onde os nós da subárvore esquerda possuem um valor inferior e o da direita possuem um valor superior exemplo:

    ............8 pai

    3 filhos.........10 filhos

  • Uma árvore binária de busca (ou árvore binária de pesquisa) é uma estrutura de dados de árvore binária baseada em nós, onde todos os nós da subárvore esquerda possuem um valor numérico inferior ao nó raiz e todos os nós da subárvore direita possuem um valor superior ao nó raiz esta é a forma padrão.

    https://pt.wikipedia.org/wiki/Árvore_binária_de_busca

  • Força Guerreiro!!!!!!

  • Força Guerreiro!!!!!!

ID
2940367
Banca
COSEAC
Órgão
UFF
Ano
2019
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Em relação a estrutura de dados árvore, avalie se são verdadeiras (V) ou falsas (F) as afirmativas a seguir.

I O número de nível mais alto de uma árvore é conhecido como grau de uma árvore.

II Quando um nó possui grau zero, diz-se que ele é um nó terminal ou folha.

III Árvores são estruturas de dados estáticas em que os dados possuem uma ordem pré-definida, os elementos são dispostos de acordo com uma hierarquia e existe um nó principal conhecido como raiz.

As afirmativas I, II e III são, respectivamente:

Alternativas
Comentários

  • Resposta: B

    I O número de nível mais alto de uma árvore é conhecido como grau de uma árvore.

    II Quando um nó possui grau zero, diz-se que ele é um nó terminal ou folha.

    III Árvores são estruturas de dados estáticas em que os dados possuem uma ordem pré-definida, os elementos são dispostos de acordo com uma hierarquia e existe um nó principal conhecido como raiz.

    I Altura de uma árvore

    ● corresponde ao maior nível

    ● maior distância entre a raiz e qualquer nó

    II Correto

    III A estrutura de dados associada a uma árvore é do tipo dinâmico

  • ÁRVORE:

     

    ∵ Relação de hierarquia;

    ∵ Bidimensional;

    ∵ Não Linear;

    ∵ Grau: nº de subárvores de um nó (Grau igual a zero ➻ Folha ou nó terminal)

    ∵ Níveis: nº de 'linhas' que liga à raiz ( Raiz ➻ nível 0);

    ∵ Altura: nível mais alto da árvore;

    ∵ Floresta: conjunto de zero ou mais árvores disjuntas (elimina-se o nó raiz, o que sobrar será uma floresta);

    ..

    Gabarito B;

    At.te

    Foco na missão ❢

  • Força Guerreiro!!!!!!

ID
2986744
Banca
CCV-UFC
Órgão
UFC
Ano
2019
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Sobre as árvores binárias, é correto afirmar:

Alternativas
Comentários

  • A) ERRADO. Uma árvore binária do tipo cheia é aquela onde todos os nós folhas estão no penúltimo e no último nível.

    Definição do Prof. Adriano Cruz da UFRJ que acredito ser bem tranquila de entender:

    B) ERRADO. Em uma árvore binária, todos os nós devem ter estritamente 0 ou 2 nós filhos, como forma de manter a árvore balanceada.

    Uma árvore estritamente binária é uma árvore binária em que cada nó tem 0 ou 2 filhos.

    C) ERRADO. Nas árvores binárias, uma árvore pode ter duas raízes simultâneas como forma de melhorar o desempenho nas operações realizadas sobre ela.

    Não encontrei literatura falando sobre raízes simultâneas.

    D) ERRADO. As árvores binárias somente podem ser implementadas através de alocação dinâmica, devido à impossibilidade de determinar a quantidade de elementos que a árvore terá.

    É possível determinar a quantidade de elementos.

    E) GABARITO

  • Força Guerreiro!!!!!!

ID
3007909
Banca
Marinha
Órgão
Quadro Técnico
Ano
2019
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

De acordo com Szwarcfiter e Markenzon (2010), assinale a opção correta.

Alternativas
Comentários

  • ERRADA - A - A idéia é justamente manter o custo de acesso na mesma ordem de grandeza de uma árvore ótima, ou seja, O(log n).

    ERRADA - B - Além das duas operações, existe ainda a seleção do elemento de maior prioridade.

    CORRETA - C - Na busca digital a chave é constituída de um conjunto de caracteres ou dígitos definidos em um alfabeto apropriado.

    ERRADA - D - No processamento de cadeias, o problema de codificação de mensagens é que aparece na transmissão de mensagens em uma rede. Dada uma cadeia de caracteres, denominada mensagem, o problema consiste em codificá-la através da atribuição de códigos a seus caracteres, de modo a minimizar o comprimento total da mensagem codificada.

    Já o problema de casamento de cadeias acontece, por exemplo, na edição de textos. Este problema tem duas soluções: método de força bruta e o algoritmo de Knuth, Morris e Pratt.

    ERRADA - E - Uma árvore estritamente binária é uma árvore binária em que cada nó possui 0 ou 2 filhos.

    Fonte: SZWARCFITER, Jayme L.; MARKENZON, Lilian. Estruturas de Dados e seus Algoritmos. 3.ed. LTC, 2010. 

  • Pega o bizu lá na mentoria @coach_bizurado

ID
3044470
Banca
FCC
Órgão
TRF - 4ª REGIÃO
Ano
2019
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

O Round-Robin é um tipo de escalonamento preemptivo mais simples e consiste em repartir uniformemente o tempo da CPU entre todos os processos prontos para a execução. Os processos são organizados em uma estrutura de dados, alocando-se a cada um uma fatia de tempo da CPU, igual a um número de quanta. Caso um processo não termine dentro de sua fatia de tempo, retorna para o fim da estrutura e uma nova fatia de tempo é alocada para o processo que está no começo da estrutura e que dela sai para receber o tempo de CPU.


A estrutura de dados utilizada nesse tipo de escalonamento é:

Alternativas
Comentários

  • Na realidade a remoção de um elemento da fila é realizada apenas alterando-se a informação da posição do último. Para evitar problemas de não ser capaz de inserir mais elementos na fila, mesmo quando ela não está cheia, as referências primeiro e último circundam até o inicio do vetor, resultando numa fila circular.

    Na fila simples o primeiro a entrar é o primeiro a sair, não havendo volta para o inicio da fila.

  • Todos os processos são armazenados em uma fila circular. O agendamento round-robin geralmente emprega tempo compartilhado, dando a cada tarefa um tempo definido chamado quantum. A tarefa é interrompida se esgotado o quantum e retomará de onde parou no próximo agendamento.

  • Força Guerreiro!!!!!!

  • Oi, tudo bem?

    Gabarito: C

    Bons estudos!

    -Se você não está disposto a arriscar, esteja disposto a uma vida comum. – Jim Rohn

ID
3044473
Banca
FCC
Órgão
TRF - 4ª REGIÃO
Ano
2019
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Determinada estrutura de dados foi projetada para minimizar o número de acessos à memória secundária. Como o número de acessos à memória secundária depende diretamente da altura da estrutura, esta foi concebida para ter uma altura inferior às estruturas hierarquizadas similares, para um dado número de registros. Para manter o número de registros armazenados e, ao mesmo tempo, diminuir a altura, uma solução é aumentar o grau de ramificação da estrutura (o número máximo de filhos que um nó pode ter). Assim, esta estrutura possui um grau de ramificação geralmente muito maior que 2. Além disso, a cada nó são associados mais de um registro de dados: se o grau de ramificação de um nó for g, este pode armazenar até g-1 registros.


Esta estrutura de dados é utilizada em banco de dados e sistema de arquivos, sendo denominada

Alternativas
Comentários

  • Em ciência da computação, uma árvore B é uma estrutura de dados em árvore, auto-balanceada, que armazena dados classificados e permite pesquisas, acesso sequencial, inserções e remoções em tempo logarítmico. A árvore B é uma generalização de uma árvore de pesquisa binária em que um nó pode ter mais que dois filhos.

  • Valei-me

  • Força Guerreiro!!!!!!

  • Olá!

    Gabarito: B

    Bons estudos!

    -As pessoas costumam dizer que a motivação não dura sempre. Bem, nem o efeito do banho, por isso recomenda-se diariamente. – Zig Ziglar

ID
3067798
Banca
CS-UFG
Órgão
Fundação Unirg
Ano
2017
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Árvores de pesquisa são estruturas de dados que podem ser usadas para a busca de elementos presentes em seus nós. Um exemplo de árvore binária de pesquisa é a árvore

Alternativas
Comentários

  • Árvore AVL é uma árvore binária de busca balanceada, ou seja, uma árvore balanceada são as árvores que minimizam o número de comparações efetuadas no pior caso para uma busca com chaves de probabilidades de ocorrências idênticas.

  • Força Guerreiro!!!!!!

ID
3067801
Banca
CS-UFG
Órgão
Fundação Unirg
Ano
2017
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

A altura de um nó em uma árvore binária é a distância entre o nó e o seu descendente mais afastado. A altura de uma árvore binária é a altura da raiz da árvore. Se a árvore possui somente o nó raiz, então sua altura é 0 (zero). Dentre as árvores binárias que possuem sete nós, a maior altura de árvore possível é:

Alternativas
Comentários

  • " Uma árvore binária de altura n−1 é um tronco sem galhos: cada nó tem no máximo um filho."

    Fonte: https://www.ime.usp.br/~pf/algoritmos/aulas/bint.html

    Altura= n-1

    Altura = 7 -1

    Altura = 6

    GABARITO ALTERNATIVA B

  • Força Guerreiro!!!!!!

ID
3067804
Banca
CS-UFG
Órgão
Fundação Unirg
Ano
2017
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

O caminhamento em árvores binárias envolve percorrer a árvore de forma a visitar cada nó somente uma vez. No caminhamento pré-fixado à esquerda, a sequência considerada é:

Alternativas
Comentários

  • Quando a banca diz "pré-fixado à esquerda", leia-se: "Pré-Ordem".

    Pré-Ordem

    Percorrer uma árvore binária em pré-ordem:

    1 Vistar a raiz.

    2 Percorrer a sua subárvore esquerda em pré-ordem.

    3 Percorrer a sua subárvore direita em pré-ordem.

    Visitar um nó significa executar uma certa ação no nó.

    In-ordem

    Percorrer uma árvore binária em in-ordem:

    1 Percorrer a sua subárvore esquerda em in-ordem.

    2 Vistar a raiz.

    3 Percorrer a sua subárvore direita em in-ordem.

    A in-ordem visita a raiz entre as ações de percorrer as duas

    subárvores. É conhecida também pelo nome de ordem

    simétrica.

    Pós-ordem

    Percorrer uma árvore binária em pós-ordem:

    1 Percorrer a sua subárvore esquerda em pós-ordem.

    2 Percorrer a sua subárvore direita em pós-ordem.

    3 Vistar a raiz.

  • Agregando conhecimento:

    a)visitar a raiz, percorrer a subárvore esquerda, percorrer a subárvore direita.

    GABARITO, pré-ordem ( prefixado) raiz-esquerda-direita;

    .

    b) percorrer a subárvore esquerda, visitar a raiz, percorrer a subárvore direita.

    Incorreta, percursos em-ordem( percurso simétrico) esquerda-raiz-direita

    .

    C) Incorreta, pra fins de provas e concursos, não existe tal possibilidade

    d) Incorreta, pra fins de provas e concursos, não existe tal possibilidade

  • Comentário correto é o do Thiago Trigo.

  • Força Guerreiro!!!!!!

ID
3067807
Banca
CS-UFG
Órgão
Fundação Unirg
Ano
2017
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

A árvore de pesquisa que busca melhorar a eficiência das operações, tal que os nós mais frequentemente acessados são mantidos na parte superior da árvore, é denominada árvore

Alternativas
Comentários

  • Árvore Splay é uma árvore binária de busca autoajustável, com a propriedade adicional de tornar os elementos recentemente acessados, fáceis de acesso novamente, pois os mantém em sua raiz. 

  • árvore ordenada é uma árvore de derivação em que os filhos de cada nó estão ordenados, ao serem rotulados com os lados esquerdos das produções, além de que o filho de cada nó representa seus correspondentes lados direitos.

    árvore B é uma estrutura de dados em árvore, auto balanceada, que armazena dados classificados e permite pesquisas, acesso sequencial, inserções e remoções em tempo logarítmico. A árvore B é uma generalização de uma árvore de pesquisa binária em que um nó pode ter mais que dois filhos.

    árvore Rubro-negra é complexa, mas tem um bom pior-caso de tempo de execução para suas operações e é eficiente na prática: pode-se buscar, inserir, e remover em tempo O(log n), onde n é o número total de elementos da árvore. De maneira simplificada, uma árvore rubro-negra é uma árvore de busca binária que insere e remove de forma inteligente, para assegurar que a árvore permaneça aproximadamente balanceada.

    árvore splay é uma árvore binária de busca autoajustável, com a propriedade adicional de tornar os elementos recentemente acessados, fáceis de acesso novamente, pois os mantém em sua raiz. Suas operações básicas, como remoção e inserção, são executadas em O(log n). Todas as suas operações colocam o elemento envolvido na operação na raiz, através de rotações. Para muitas sequências de operações não aleatórias, as árvores splay têm melhor desempenho do que outras árvores de busca, mesmo quando o padrão específico da sequência é desconhecido.

  • Força Guerreiro!!!!!!

ID
3097177
Banca
Quadrix
Órgão
CREA-GO
Ano
2019
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Acerca das estruturas homogêneas de dados vetor e matriz e dos conceitos de pilhas, filas e árvores binárias, julgue o item.


Nas árvores binárias, os nós da direita sempre possuem valor superior ao do nó‐pai.

Alternativas
Comentários

  • Verdade, os nós da direita possuem valor maior e os da esquerda valor menor que o nó raiz

  • Estou com uma dúvida, não seria menor à esquerda e maior ou IGUAL à direita?

  • Questão com dupla interpretação, mas com um pouco de cuidado dá para respondê-la. Percebam que ele fala nó-pai e não nó-raiz. E SIM, todos os nós à direita são maiores que o seu pai seja do lado esquerdo ou direito da árvore.

  • Corrigindo a 'dúvida' do Bruno, sim é maior ou IGUAL a direita.

    O que não anula a questão.

    GABARITO: CERTO

  • RESOLUÇÃO:

    Assertiva correta, os nós da direita d árvore, sempre possui valores maior que os da esquerda do nó pai.

    Resposta: Errado

  • Em árvores binárias de BUSCA, cuidado!

  • Força Guerreiro!!!!!!

  • Essa questão deveria ser anulada! Em nenhum momento a questão fala que a arvore está ordenada. Logo não tem como inferir nada a respeito de seus nós. Uma árvore binárias não, necessariamente, precisa estar ordenada.

ID
3136033
Banca
Exército
Órgão
EsFCEx
Ano
2019
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Árvores binárias podem ser usadas para representar expressões aritméticas. Como um exemplo de expressão, podemos ter: a * b + f sen – h * j com os elementos enumerados “Em-ordem”. Nesse caso, a árvore binária terá como raiz

Alternativas
Comentários

  • Acredito que a anulação da questão seja pelos os átomos + e o - poderem ser raízes da expressão.

    O átomo + (mais) como raiz (representação por ponteiros):

    .........................................................(+)

    ........................................................./...\

    .....................................................(*)......(-)

    ..................................................../...\....../....\

    .................................................(a)..(b).(sen).(*)

    ....................................................................../..\

    ....................................................................(h).(j)

    O átomo - (menos) como raiz:

    .........................................................(-)

    ......................................................../....\

    ...................................................(+).......(*)

    ................................................../...\......../..\

    ..............................................(*)..(sen).(h).(j)

    ................................................./..\

    .............................................. (a).(b)

  • Em expressões de arvores binarias devemos respeitar a seguinte ordem:

    Operadores: Raízes

    Operandos: Folhas

    já de cara descartamos a A e J pq não podem ser raízes pq não são operando.

    em seguida montamos a raiz e depois seguimos em-ordem e vemos a raiz.

    R: +

  • O átomo +.

ID
3172810
Banca
IF-PE
Órgão
IF-PE
Ano
2019
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Sobre estruturas de dados, assinale a alternativa CORRETA.

Alternativas
Comentários

  • a) Correta - GABARITO DA QUESTÃO.

    b) Incorreta, filas são estruturas lineares, não são implementadas sobre grafos;

    c) Incorreta, árvores binárias de busca são estruturas em que os filhos da esquerda( nós da subárvore esquerda) possuem valores numericamente inferior ao nó pai, por sua vez, os filhos da direita( nós da subárvore direita) possuem valores numericamente superior ao nó pai.

    d) Incorreta, apesar de o examinador não fazer menção a grafo não direcionados, eles existem, e por sua vez, possuem relações bidirecionais com os demais nós.

    e)Listas duplamente ligadas são estruturas em que cada nó possui uma referência tanto ao nó que o antecede quanto ao nó que o sucede. Além disso, o último nó da lista também possui uma referência para o primeiro nó da lista.

    Incorreta, no trecho final, uma lista duplamente encadeada( ligada) não necessariamente possui referência para o primeiro nó da lista, quem faz esta referência é a lista circular

  • Aparentemente, algumas instituições consideram TIPOS DE DADOS sinônimo de ESTRUTURA DE DADOS.

  • Resposta Correta: Pilhas são tipos de dados abstratos caracterizadas pela política "primeiro a entrar, último a sair". 

  • Força Guerreiro!!!!!!

ID
3180448
Banca
CESGRANRIO
Órgão
Transpetro
Ano
2018
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Uma árvore binária foi percorrida em ordem simétrica, e os valores de seus nós exibidos no console. O resultado desse procedimento foi o seguinte:

15 12 10 19 20 13 34

Dentre as árvores apresentadas, a única capaz de produzir o resultado acima é

Alternativas
Comentários

  • a leitura está invertida da direita pra esquerda. Pode isso Arnaldo?

  • A questão inverteu a ordem, o correta da simétrica é esquerda , raiz e direita. Alguém pode explicar se estou equivocado?

  • Ordem de Leitura

    1.Pré-ordem: raiz; esquerda; direita

    2.Em-ordem: esquerda; raiz; direita (Também chamada de simétrica)

    3.Pós-ordem: esquerda; direita; raiz

    https://www.ime.usp.br/~song/mac5710/slides/05tree

    Acredito que o enunciado esteja incorreto. Tem que ver se não foi anulada

  • A Cesgranrio tem um entendimento diferente quanto ao percurso dos elementos.

  • da direita pra esquerda é nova

  • Aprendi com esse vídeo https://www.youtube.com/watch?v=CBXrsb8Yvnw&ab_channel=DicaseResolu%C3%A7%C3%B5es

  • Força Guerreiro!!!!!!

  • Da direita para a esquerda não acho correto.

  • CESGRANRIO Inventou a própria forma dela de ORDENAR árvores.

    GABARITO B

ID
3186238
Banca
COMPERVE
Órgão
UFRN
Ano
2019
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Estruturas de dados básicas como listas, filas e árvore são componentes fundamentais em muitos programas de computador. Sobre essas estruturas de dados, é correto afirmar:

Alternativas
Comentários

  • Força Guerreiro!!!!!!

ID
3263122
Banca
AOCP
Órgão
Prefeitura de Juiz de Fora - MG
Ano
2016
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Um heap é uma estrutura de dados representada por uma árvore binária T, que armazena uma coleção de chaves em seus nodos internos, satisfazendo duas propriedades: uma relacional e outra estrutural. Sabendo disso, assinale a alternativa que apresenta corretamente a propriedade de ordem do heap.

Alternativas
Comentários

  • Propriedade de ordem do heap: Em um heap T, para cada nodo v diferente da raiz, a chave em v é maior ou igual à chave armazenada no nodo pai de v.

    (Estrutura de dados & Algoritmos, 5ª ed)

    .

    Gab A;

    At.te

    Foco na missão ❢

  • Força Guerreiro!!!!!!

ID
3292144
Banca
AOCP
Órgão
FUNPAPA
Ano
2018
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Na computação, uma estrutura de dados é um modo particular de armazenamento e organização de dados em um computador, de modo que possam ser usados eficientemente, facilitando sua busca e modificação. Sobre estrutura de dados, é correto afirmar que

Alternativas
Comentários

  • Lista Duplamente Encadeada   

    - A lista duplamente encadeada é percorrida em ambos os sentidos.

    - Cada nó aponta para dois outros nós da lista, um anterior e um posterior.

    Alternativa: A

  • Força Guerreiro!!!!!!

ID
3343801
Banca
CS-UFG
Órgão
UFG
Ano
2019
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

O caminhamento com percurso pós-ordem em uma árvore binária resultou na sequência “A X K D C J B”, em que cada caractere refere-se a um nó visitado. Nesse caso, o nó raiz refere-se ao caractere

Alternativas
Comentários

  • Pré-Ordem: RAIZ - Esquerda - Direita

    In-Ordem: Esquerda - RAIZ - Direira

    Pós-Ordem: Direita - Esquerda - RAIZ

    Gabarito: Letra D

  • Pós-Ordem é ESQUERDA - DIREITA - RAIZ <<<<<<<<<<<<<<, não tem K nem J nas opções, então óbvio :D

    a - x- K d - c - J B

  • Não precisamos montar toda a arvore, basta lembrar que, como cita a colega Luciana:

    "Pós-Ordem: Direita - Esquerda - RAIZ"

    Ou seja, o último elemento será a raiz

    A sequência proposta foi esta: “A X K D C J B”.

    Portanto a raiz será o elemento B

    GABARITO ALTERNATIVA D

  • Força Guerreiro!!!!!!

ID
3379132
Banca
INSTITUTO AOCP
Órgão
UFOB
Ano
2018
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Sobre as Estruturas de Dados, seus conceitos e usos, julgue, como VERDADEIRO ou FALSO, os itens a seguir.

Para um nó raiz de uma árvore binária qualquer, sempre há dois nós filhos: esquerdo e direito.

Alternativas
Comentários

  • GABARITO ERRADO

    Para a árvore binária, pode haver ATÉ dois filhos: esquerdo e direito.

  • Uma árvore binária é um conjunto finito de zero ou mais elementos (nós), tais que existe um elemento raiz da árvore e cada elemento pode ter zero, um ou duas subárvores (nós filhos), conhecidas como subárvore esquerda e subárvore direita.

     

  • Força Guerreiro!!!!!!

ID
3379138
Banca
INSTITUTO AOCP
Órgão
UFOB
Ano
2018
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Sobre as Estruturas de Dados, seus conceitos e usos, julgue, como VERDADEIRO ou FALSO, os itens a seguir.

A árvore B+ é um tipo de árvore na qual todos as chaves estão armazenadas nas folhas.

Alternativas
Comentários

  • GABARITO CERTO

    A árvore B+ é uma variação da árvore B, atente-se as características:

    1)Todas as chaves são mantidas em folhas;

    2)As chaves são repetidas em nós não folhas, formando um índice;

    3)As folhas são ligadas formando um índice;

    FONTE: https://marciobueno.com/arquivos/ensino/ed2/ED2_04_Arvore_B+.pdf

  • Árvore B+: As chaves podem ser armazenadas em qualquer nó, mas os dados só podem ser armazenados nas folhas.

    Árvore B: As chaves e os dados podem ser armazenados tanto nos nós internos da árvore quanto nas folhas da árvore

  • Força Guerreiro!!!!!!

  • Força Guerreiro!!!!!!

ID
3504118
Banca
IBFC
Órgão
Prefeitura de Cruzeiro do Sul - AC
Ano
2019
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Sobre alguns tipos de estruturas de dados utilizadas em computação, assinale a alternativa incorreta.

Alternativas
Comentários

  • Força Guerreiro!!!!!!

ID
3590209
Banca
CESPE / CEBRASPE
Órgão
TRE-MS
Ano
2012
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Acerca de tipos básicos de estruturas de dados, assinale a opção correta.

Alternativas
Comentários

  • Um grafo é uma união de vértices (nós) conectados par a par pelas arestas, portanto possuem esse nó antecessor.

    Na letra A, ele tenta confundir com LIFO = PILHA = STACK

    FIFO = FILA

    Na letra D, a resposta correta seria Pilha.

  • Força Guerreiro!!!!!!

  • A: Uma estrutura do tipo pilha, também conhecida como stack, permite que as operações sejam realizadas em seu topo a partir do primeiro elemento inserido por meio de acesso LIFO (Last in first out).

    B: Os grafos se assemelham às filas em termos de estrutura, mas, enquanto nas filas as operações são realizadas no início e fim, nos grafos elas podem ser realizadas tanto no início quanto no fim da estrutura.

    C: Nos grafos, devido à sua estrutura, há operações possíveis para a determinação de vértices adjacentes, os vértices que estão no início (topo) e no fim (base) podem ser determinados.

    D: Nas estruturas do tipo árvores, as operações push ( ) e pop ( ) permitem Inserir e Remover nós, respectivamente.

    E: CERTO

ID
3597337
Banca
IPAD
Órgão
COMPESA
Ano
2009
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Em uma árvore binária completa:

Alternativas
Comentários

  • ===Letra A===

    Cada nó possui zero ou dois filhos.(ERRADO)

    Essa é uma característica de uma arvore estritamente binária

    ===Letra B===

    Todo nó que possui alguma subárvore árvore vazia se localiza no último ou penúltimo nível da árvore. (CERTO)

    ===Letra C===

    Todo nó que possui alguma subárvore árvore vazia se localiza no último nível da árvore. (ERRADO)

    Essa é uma característica de uma arvore binária cheia

    ===Letra D===

    Todas as chaves da subárvore esquerda são maiores que a chave da raiz. (ERRADO)

    Todas as chaves da subárvore esquerda são menores que a chave da raiz.

    ]===Letra E===

    Todas as chaves da subárvore direita são menores que a chave da raiz (ERRADO)

    Todas as chaves da subárvore direita são maiores que a chave da raiz

  • A = Estritamente Binária

    B = Árvore Binária Completa

    C = Árvore Binária Cheia

    D = Refere-se A ÁRVORE BINÁRIA DE BUSCA e ESQUERDA É MENOR

    E = Refere-se A ÁRVORE BINÁRIA DE BUSCA e DIREITA É MAIOR

    GABARITO B

ID
3635935
Banca
IPAD
Órgão
COMPESA
Ano
2009
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Qual das seguintes definições sobre a estrutura de dados denominada árvore está incorreta?  

Alternativas
Comentários

  • ===Letra A===

    Uma árvore é uma estrutura que contém um conjunto finito de elementos denominados nós ou vértices. (CERTO)

    ===Letra B===

    Grau de um nó é o número de sub-árvores de um nó.(CERTO)

    ===Letra C===

    Um nó que não tem sub-árvores é chamado de nó-folha.(CERTO)

    ===Letra D===

    Altura de um nó v é o número de nós do caminho da raiz até o nó v. (ERRADO)

    A altura de um nó v é o número de nós do maior caminho de v até um de seus descendentes. 

    ===Letra E===

    Nível de um nó v é o número de nós do caminho da raiz até o nó v(CERTO)

  • na verdade é até o seu descendente mais afastado.

ID
3681376
Banca
AOCP
Órgão
PRODEB
Ano
2008
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Uma árvore de expressão para representação não ambígua de expressões aritméticas utiliza a estrutura de uma árvore

Alternativas
ID
3764047
Banca
INSTITUTO AOCP
Órgão
Prefeitura de Betim - MG
Ano
2020
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Considerando uma árvore de busca binária, assinale a alternativa correta.

Alternativas
Comentários

  • Força Guerreiro!!!!!!

ID
3845575
Banca
Avança SP
Órgão
Câmara Municipal de Taboão da Serra - SP
Ano
2019
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Considerando uma estrutura de dados do tipo “lista”, se tanto as operações de inserção quanto as operações de remoção são realizadas somente em um de seus extremos, então pode-se afirmar que essa estrutura recebe o nome de:

Alternativas
Comentários

  • Força Guerreiro!!!!!!

ID
3845593
Banca
Avança SP
Órgão
Câmara Municipal de Taboão da Serra - SP
Ano
2019
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Como se sabe, existe uma estrutura de dados muito utilizada como forma de armazenamento em memória secundária e empregada por diversos sistemas de Banco de Dados. Trata-se da árvore B, que é uma árvore ordenada que possui uma estrutura:

Alternativas
Comentários

  • Arvores B

    A árvore B, utilizando o recurso de manter mais de uma chave em cada nó da estrutura, proporciona uma organização de ponteiros tal que as operações mencionadas são executadas rapidamente. Além disso, sua construção assegura que as folhas se encontram todas em um mesmo nível, não importando a ordem de entrada de dados.

    Possui uma estrutura que minimiza o tempo de acesso para operações de busca, inserção e remoção.

    As árvores B são largamente utilizadas como forma de armazenamento em memória secundária. 

    Alternativa: B

  • Força Guerreiro!!!!!!

ID
3871105
Banca
FAURGS
Órgão
UFCSPA - RS
Ano
2018
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Uma árvore binária é caracterizada por ter

Alternativas
Comentários

  • Árvores Binárias (B-trees)

    - São árvores em que o grau de cada nó é menor ou igual a dois

    - Nunca haverá um terceiro nó em árvores binárias.

    - Uma arvore binária é uma árvore em que, abaixo de cada nó existem no máximo duas subárvores

    - São eficientes para realizar busca, pois parte-se do princípio que se têm dados organizados.

    - Toda árvore binária com n nós possui exatamente n + 1 subárvores vazias entre suas subárvores esquerdas e direitas.

    Alternativa: C

  • Força Guerreiro!!!!!!

ID
3880942
Banca
Instituto UniFil
Órgão
Prefeitura de Cunha Porã - SC
Ano
2020
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Sobre o tema, Estrutura de Dados, analise as assertivas e assinale a alternativa correta.


I. Pilhas - São estruturas de dados do tipo LIFO (last-in first-out), onde o último elemento a ser inserido, será o primeiro a ser retirado. Assim, uma pilha permite acesso a apenas um item de dados - o último inserido. Para processar o penúltimo item inserido, deve-se remover o último.

II. FILAS - São estruturas de dados do tipo FIFO (first-in first-out), onde o primeiro elemento a ser inserido, será o primeiro a ser retirado, ou seja, adiciona-se itens no fim e remove-se do início.

III. Lista linear é uma estrutura de dados na qual elementos de um mesmo tipo de dado estão organizados de maneira sequencial. Não necessariamente, estes elementos estão fisicamente em sequência, mas a ideia é que exista uma ordem lógica entre eles.

IV. Árvore é uma estrutura de dados que herda as características das topologias em árvore. Conceitualmente diferente das listas encadeadas, em que os dados se encontram numa sequência, nas árvores os dados estão dispostos de forma hierárquica. Uma árvore é formada por um conjunto de elementos que armazenam informações chamados nodos. Toda a árvore possui o elemento chamado raiz, que possui ligações para outros elementos denominados ramos ou filhos. Estes ramos podem estar ligados a outros elementos que também podem possuir outros ramos. O elemento que não possui ramos é conhecido como nó folha, nó terminal ou nó externo.

Alternativas
Comentários

  • Força Guerreiro!!!!!!

ID
4112881
Banca
CESPE / CEBRASPE
Órgão
Prefeitura de Boa Vista - RR
Ano
2004
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

A respeito de estrutura de dados, julgue o item que se segue.


Uma árvore binária é dita equilibrada se a diferença entre as alturas das subárvores de cada nó — valor absoluto da diferença entre as alturas da subárvore direita e da subárvore esquerda — é, no máximo, igual a 1.

Alternativas
Comentários

  • Obrigado pelos comentários caros colegas, e obrigado ao quadrado pra equipe do QCONCURSOS que não deixa nenhuma questão sem explicação lógica.

  • certa, para os que não são assinantes

  • Gabarito: Certo

    Primeiro, conceitos importantes de uma estrutura de árvore:

    1) Uma estrutura de árvore é constituída de um conjunto finito de elementos, em que cada elemento é um nó que se subdivide em subárvores.

    2) Existe um nó chamado de raiz, que dá início à árvore, e os outros nós geram subconjuntos denominados de subárvores.

    3) A altura de uma árvore (ou de subárvore) corresponde ao maior nível. Em outras palavras, é a maior distância entre o nó e o seu último elemento.

    Agora conceituando uma árvore binária:

    1) Uma árvore binária é um conjunto finito de elementos que ou é vazio ou é composto de três conjuntos disjuntos

    ● Árvore binária vazia: Só contém um único elemento, a raiz.

    ● Árvore binária não vazia: Composta da raiz e de outros dois subconjuntos -> a subárvore da esquerda e subárvore da direita. As subárvores da esquerda ou da direita podem estar vazias.

    Agora a definição de árvore binária balanceada: Uma árvore binária é considerada balanceada quando as alturas das duas subárvores (esquerda e direita) nunca difere em mais de 1, ou seja, é no máximo igual a 1. O balanceamento de um nó é definido como a altura de sua subárvore esquerda menos a altura de sua subárvore direita.

    Com isso, pode-se concluir que a questão traz exatamente a definição de árvore binária balanceada estando, portanto, correta.

    Fonte:

    1) http://www.ic.uff.br/~boeres/slides_ed/ed_ArvoresPercursos.pdf

    2) http://wiki.icmc.usp.br/images/f/f0/AVL.pdf

    Espero ter ajudado. Qualquer erro, me mandem mensagem.

    Bons estudos!

ID
4180906
Banca
CETRO
Órgão
AMAZUL
Ano
2015
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Sobre estruturas de dados do tipo árvore binária, analise as assertivas abaixo.


I. Diferente das listas simplesmente encadeadas, as árvores binárias permitem que cada nó tenha dois nós sucessores (filhos).

II. Raiz (root) é o nó mais inferior da árvore binária que não possui sucessores (filhos).

III. Folha (leaf) é qualquer nó da árvore binária que não tenha sucessores (filhos).


É correto o que se afirma em

Alternativas
Comentários

  • Árvores Binárias (B-trees)

    - São árvores em que o grau de cada nó é menor ou igual a dois

    - Nunca haverá um terceiro nó em árvores binárias.

    - Uma arvore binária é uma árvore em que, abaixo de cada nó existem no máximo duas subárvores.

    - São eficientes para realizar busca, pois parte-se do princípio que se têm dados organizados.

    - Toda árvore binária com n nós possui exatamente n + 1 subárvores vazias entre suas subárvores esquerdas e direitas.

  • Força Guerreiro!!!!!!

ID
4184023
Banca
MPE-RS
Órgão
MPE-RS
Ano
2015
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Assinale a alternativa que preenche corretamente a lacuna do enunciado abaixo.


Denomina-se ________de um nodo de uma árvore o número de subárvores que são subordinadas diretamente a este nodo, ou seja, à quantidade de subárvores para as quais este nodo é raiz.

Alternativas
Comentários

  • Denomina-se grau de um nodo de uma árvore o número de subárvores que são subordinadas diretamente a este nodo, ou seja, à quantidade de subárvores para as quais este nodo é raiz.

    Grau: Quantidade de subárvores de um nó. O grau de cada nó é o número de subárvores que ele possui.

  • Força Guerreiro!!!!!!

ID
4968037
Banca
IBADE
Órgão
Prefeitura de Itapemirim - ES
Ano
2019
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Estruturas de dados são métodos para armazenagem de dados de forma eficiente. Das estruturas abaixo, a utilizada pelos bancos de dados hierárquicos é:

Alternativas
Comentários

  • "Uma base de dados hierárquica é um tipo de sistema de gerenciamento de banco de dados que conecta registros numa estrutura de dados em árvore através de ligações de tal modo que cada tipo de registro tenha apenas um possuidor." - https://pt.wikipedia.org/wiki/Modelo_hier%C3%A1rquico_de_banco_de_dados.

    Gabarito: E

  • Força Guerreiro!!!!!!

ID
4985320
Banca
COPESE - UFT
Órgão
MPE-TO
Ano
2012
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Com relação às árvores binárias, analise as assertivas a seguir.


I. Uma árvore é estritamente binária quando cada nó possui 2 filhos;

II. Em uma árvore completa, se v é um nó tal que alguma subárvore de v é vazia, então v se localiza no último ou no penúltimo nível da árvore;

III. Uma árvore cheia, se v é um nó com alguma de suas subárvores vazias, então v se localiza no último nível;

IV. Uma árvore binária completa T com n > 0 nós. Então T possui altura mínima h = 1 + ⌊log n⌋;

V. Uma árvore binária cheia T com n > 0 nós. Então T possui altura máxima h = 2n -1;


É CORRETO afirmar que:

Alternativas
Comentários

  • Força Guerreiro!!!!!!

ID
5164258
Banca
VUNESP
Órgão
TJM-SP
Ano
2021
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Em uma árvore binária de busca balanceada do tipo AVL, as alturas das duas sub-árvores de um nó qualquer diferem em no máximo 1. A construção de uma árvore desse tipo, inicialmente vazia, por meio da inserção sucessiva de nós, utiliza uma certa operação para manter o balanceamento desejado quando necessário. Essa operação é

Alternativas
Comentários

  • Árvore AVL (ou árvore balanceada pela altura) é uma árvore de busca binária auto-balanceada. Em tal árvore, a altura de dois nós folha difere no máximo em uma unidade.

    Já a Rotação é a operação básica em uma árvore AVL que geralmente envolve os mesmos algoritmos de uma árvore de busca binária desbalanceada. A rotação na árvore AVL ocorre devido ao seu desbalanceamento.

    Fonte: https://pt.wikibooks.org/wiki/Algoritmos_e_Estruturas_de_Dados/%C3%81rvores_AVL#Rota%C3%A7%C3%A3o

  • Boa Sorte

ID
5371975
Banca
FADESP
Órgão
Câmara de Marabá - PA
Ano
2021
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Seja T uma árvore balanceada do tipo AVL (Adelson-Velski e Landis) vazia. Supondo que os elementos 5, 10, 12, 8, 7, 11 e 13 sejam inseridos nessa ordem em T, a sequência que corresponde a um percurso de T em pré-ordem é

Alternativas
Comentários

  • Durante a inserção dos elementos na árvore é necessário fazer o balancemanto por meio da rotação dos nós, mantendo assim as alturas das subárvores de todos os nós com a diferença máxima de 1.

    Estado da árvore ao final da inserção:

    --------------(10)----------------

    -----(7)--------------(12)-------

    --(5)---(8)------(11)---(13)--

    Leitura no percurso pré-ordem: 10, 7, 5, 8, 12, 11 e 13

    Gabarito B

  • Boa Sorte

  • Oi!

    Gabarito: B

    Bons estudos!

    -As pessoas costumam dizer que a motivação não dura sempre. Bem, nem o efeito do banho, por isso recomenda-se diariamente. – Zig Ziglar

  • Resolução:

    Inserindo os elementos:

         5 ——

     —— 10 ——

    — 8       ——12——

    7        11       13

    Há desequilíbrio em (5). Fazendo a rotação à esquerda:

       ——— 10 ———

      5 ——      ——12——

       —— 8     11       13

       7

    Há desequilíbrio em (5) novamente. Fazendo a rotação dupla à esquerda 

         —— 10 ——

    ——7 ——   ——12——

    5 8    11      13

    A árvore está equilibrada.

    Fazendo a pré-ordem: 10, 7, 5, 8, 12, 11, 13.

    Bons estudos e que caia uma menor pra resolver na nossa prova :p

ID
5474677
Banca
CESGRANRIO
Órgão
Banco do Brasil
Ano
2021
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Um programador escreveu uma função para percorrer, em pós-ordem, uma árvore binária e exibir, no console, os valores referentes aos nós dessa árvore.

Após essa função ter sido executada, foi exibido o seguinte resultado:

41 44 33 47 55 52 36 30

Que árvore essa função percorreu para exibir o resultado acima?

Alternativas
Comentários

  • Pós ordem: Comece na subárvore da esquerda, vá subindo mas vá pegando os nós da direita que estão mais em baixo. Por fim visite a raiz.

    Link que me ajudou:

    https://tecnologiadacomputacao.wordpress.com/2017/04/10/pre-ordem-e-pos-ordem-de-uma-arvore-binaria/

    Faz uma par de vez na mão pq explicando é difícil, assim como 98% de todo o universo de ti.

  • - Pré-Ordem/Profundidade/Pré-Fixada= Visita a raiz, percorre a subárvore esquerda em pré-ordem, percorre a subárvore direita em pré-ordem.

    - In-Ordem/Simétrica/Infixada/Central= Percorre a subárvore esquerda em in-ordem, visita a raiz, percorre a subárvore direita em in-ordem.

    - Pós-Ordem/Pós Fixada = Percorre a subárvore esquerda em pós-ordem, percorre a subárvore direita em pós-ordem, visita a raiz.

    GABARITO E.

ID
5509675
Banca
VUNESP
Órgão
Semae de Piracicaba - SP
Ano
2021
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Considere uma estrutura de dados T como sendo uma árvore binária do tipo AVL. Como característica, essa estrutura de dados é uma árvore binária

Alternativas
Comentários

  • Uma árvore binária T é denominada AVL quando, para qualquer nó de T, as alturas de suas duas subárvores, esquerda e direita, diferem em módulo de até uma unidade.

    Pela definição fica estabelecido que todos os nós de uma árvore AVL devem respeitar a seguinte propriedade:

    |h(u) - h(u)| ≤ 1, onde h(u) é a altura da subárvore direita do nó u e h(u) é a altura da subárvore esquerda do nó u.

    O valor h(u) - h(u) é denominado fator de balanço do nó. Quando um nó possui fator de balanço com valor -1, 0 ou 1 então o mesmo é um nó regulado. Todos os nós de uma árvore AVL são regulados, caso contrário a árvore não é AVL.

  • GABARITO A

    Balanceamento Dinâmico (AVL): São árvores binárias de busca auto balanceada;

    • Mais eficientes para buscas;
    • A cada nó que é inserido, alterado ou excluído, é necessário realizar todo o trabalho de balanceamento de novo para que permaneça com as características da árvore AVL;
    • Possuem complexidade O(log n);
    • Inserções e exclusões podem requerer um rebalanceamento, por meio de rotações;
    • Toda árvore completa é AVL;
    • Para cada nó da árvore, a diferença entre as alturas das suas subárvores (direita e esquerda) sempre será igual a -1, 0 ou 1.

  • GABARITO A

    Balanceamento Dinâmico (AVL): São árvores binárias de busca auto balanceada;

    • Mais eficientes para buscas;
    • A cada nó que é inserido, alterado ou excluído, é necessário realizar todo o trabalho de balanceamento de novo para que permaneça com as características da árvore AVL;
    • Possuem complexidade O(log n);
    • Inserções e exclusões podem requerer um rebalanceamento, por meio de rotações;
    • Toda árvore completa é AVL;
    • Para cada nó da árvore, a diferença entre as alturas das suas subárvores (direita e esquerda) sempre será igual a -1, 0 ou 1.
ID
5535898
Banca
CESGRANRIO
Órgão
Caixa
Ano
2021
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Qual árvore binária pode ser classificada como árvore binária de busca?

Alternativas
Comentários

  • GAB C

    Toda árvore binária de busca é ordenada; logo, para cada nó avaliado, as subárvores da esquerda devem possuir valor menor e os da direta devem possuir valor maior.

    A árvore da letra C também é uma árvore binária degenerada (ou zigue-zague) devido a seu formato

ID
5538376
Banca
FGV
Órgão
IMBEL
Ano
2021
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Considere uma árvore B+ com as seguintes características.


I. A raiz é uma folha ou um nó que contém, no mínimo, dois filhos.

II. Cada nó diferente do nó raiz e das folhas possui no mínimo d filhos.

III. Cada nó tem no máximo 2d filhos. Cada nó possui entre d-1 e 2d-1 chaves, exceto o raiz que possui entre 1 e 2d-1 chaves.

IV. Somente os nós folhas contêm dados associados às chaves.


Assinale o número máximo de acessos necessários para localizar uma chave, com d=10, num universo de 10 milhões de chaves. 

Alternativas
Comentários

  • Gabarito: b

    A questão esta querendo saber qual o nivel da hierarquia será para o nó 10 milhoes.

    Ex.:

    | - Nível 1 = 1

    | | - Nível 2 = 2

    | | | | - Nível 3 = 4

    ....

    - Nível 4 = 8

    ....

    Vamos usar um paralelo de tabela binária, níveis da árvore B+ e valor desejado.

    N 7 6 5 4 3 2 1

    ... 64 32 16 8 4 2 1

    10 .0 0 0 . 0 0 0

    Resultado: 10 está no nível 7.

  • D é igual ao número de filhos.

    Se D = 10, então a cada nível a árvore terá um múltiplo de 10 filhos.

    Nível 1 = 10, nível 2 = 10 nodos com possibilidade de 10 filhos cada, ou seja 10x10 = 100.

    Para ir direto ao ponto, utilizando dois níveis (2 acessos) com D = 10, eu posso ter 100 nodos (1 + 2 zeros).

    Ou seja, com 10 milhões de nodos (7 zeros) eu vou precisar percorrer pelo menos 7 níveis.

  • Partindo do pressuposto que uma árvore binária o acesso a ser dado pelos nós seria 2^n. Poderíamos fazer para árvore B+ que possui 10 índices, o seguinte: 10^n. Portanto, para resolvermos a questão faríamos assim:

    10^n = 10.000.000

    10^n = 10^7

    n = 7

ID
5551438
Banca
OBJETIVA
Órgão
Prefeitura de Santa Maria - RS
Ano
2021
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Em conformidade com CORMEN et al., considerar uma estrutura de dados ligada, na qual cada nó é um objeto. Além de uma chave e de dados satélites, cada nó contém atributos “esquerda”, “direita” e “p”, que apontam para os nós correspondentes ao seu filho à esquerda, ao seu filho à direita e ao seu pai, respectivamente. Essa estrutura refere-se à:

Alternativas
Comentários

  • A) Árvores de busca binárias.