Em uma árvore binária de busca, foram inseridos os seguintes nós, nessa ordem: 5, 25, 6, 24, 7, 23, 8, 22, 9, 21, 10, 20, 11, 19, 12, 18, 13, 17, 14, 16, 15. Sobre essa árvore, é possível afirmar que:
a) No pior caso, a inserção de um nó demandará O(log n), sendo n o número de nós.
b) No pior caso, a remoção de um nó demandará O(log n), sendo n o número de nós.
c) A árvore gerada não é balanceada. Entretanto, as buscas, inserções e remoções podem ser feitas de forma eficiente em O(log n).
d) A árvore gerada não será binária de busca, dado que existe um padrão na inserção dos nós.
e) A árvore gerada não é balanceada. Nesse caso, as buscas ocorrerão com tempo proporcional ao número de nós na árvore.
Soluções para a tarefa
Resposta: 9/10
PERGUNTA 1
Sobre remoções em árvores binárias de busca, assinale a alternativa correta.
Se o nó removido possui apenas um filho, removemos o nó e colocamos o filho no lugar dele.
PERGUNTA 2
Dados os percursos pré-ordem, pós-ordem e in-ordem a seguir, qual alternativa corretamente identifica a árvore em questão.
Pré-ordem: A C E F D G H
Pós-ordem: F E G H D C A
In-Ordem: E F C G D H A
RESPOSTA - IMAGEM NO ANEXO
PERGUNTA 3
Sobre árvores, assinale a alternativa correta.
A profundidade de um nó pode ser computada pela distância deste nó até a raiz.
PERGUNTA 4
Em uma árvore binária de busca, foram inseridos os seguintes nós, nessa ordem: 5, 25, 6, 24, 7, 23, 8, 22, 9, 21, 10, 20, 11, 19, 12, 18, 13, 17, 14, 16, 15. Sobre essa árvore, é possível afirmar que:
A árvore gerada não é balanceada. Nesse caso, as buscas ocorrerão com tempo proporcional ao número de nós na árvore.
PERGUNTA 5
Sobre árvores binárias de busca, assinale a alternativa correta.
Inserções, remoções e buscas possuem complexidade de tempo proporcional ao número de nós em árvores de busca balanceadas.
PERGUNTA 6
Em sala de aula, vimos o seguinte trecho de código usado em um dos casos da deleção de nó:
O método getSuccessoré mostrado a seguir:......
O código não entrará em looping infinito e realmente removerá o nó. Entretanto, a árvore binária gerada violará propriedades de árvore binária de busca no que diz respeito a ter os filhos menores do lado esquerdo e os filhos maiores do lado direito.
PERGUNTA 7
Sobre árvores binárias, assinale a alternativa correta.
Em uma árvore binária, as folhas são nós de grau zero e os nós internos possuem graus de no máximo 2.
PERGUNTA 8
Seja a árvore a seguir, qual alternativa mostra uma árvore obtida após a remoção de B usando o algoritmo aprendido em aula.
RESPOSTA - IMAGEM NO ANEXO
PERGUNTA 9
Dada a árvore binária a seguir, assinale a alternativa correta.
A profundidade do nó 81 é 3.
PERGUNTA 10 ERREI ESTA
Dada a árvore a seguir, qual alternativa identifica corretamente os percursos pré-ordem, pós-ordem e in-ordem, respectivamente?
A B C D E F G H; C D B G F H E A; C D B A E F G H
A B C D E F G H; C D B G H F E A; C D B A E F G H <------- INCORRETA
A B C D E F G H; C D B G H F E A; C B D A G F H E
C D B A G H F E; C D B G H F E A; A B C D E F G H <------- INCORRETA POR ELIMINAÇÃO
C D B A E F G H; C D B G H F E A; A B C D E F G H <------- INCORRETA POR ELIMINAÇÃO
Explicação: 9/10 respotas no Anexo
Sobre essa árvore, é possível afirmar que a árvore gerada não é balanceada. Nesse caso, as buscas ocorrerão com tempo proporcional ao número de nós na árvore. Alternativa E.
A Árvore Binária é uma forma de estruturar dados por sua hierarquia. Onde cada elemento é um Nó e cada primeiro elemento é chamado de Raiz. Na árvore binária, cada elemento pode ter até dois filhos, por isso binária. Um nó sem filho é chamado de folha.
A profundidade de um nó é a distância dele até a Raiz e também a distância entre a folha mais distante e a raiz é a altura da árvore. Um conjunto de nós com a mesma profundidade é denominado, nível da árvore.
A organização em Pré-ordem, Ordem e Pós-Ordem é dada pelo forma de inserção dos dados.
- Pré- Ordem: Raiz número; Raiz esquerda; Raiz Direita.
- Ordem: Raiz Esquerda; Raiz número; Raiz Direita.
- Pós- Ordem: Raiz Esquerda; Raiz Direita; Raiz Número.
Uma árvore binária de busca não balanceada é qualquer árvore binária que não mantém a sua altura pequeno mesmo depois de sucessivas inserções e exclusões arbitrárias, tendo suas buscas com tempo proporcional ao número de nós na árvore.
Veja mais sobre árvores binárias em: https://brainly.com.br/tarefa/26189180
