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) A árvore gerada não é balanceada. Entretanto, as buscas, inserções e remoções podem ser feitas de forma eficiente em O(log n).
C) A árvore gerada não será binária de busca, dado que existe um padrão na inserção dos nós.
D) No pior caso, a remoção de um nó demandará O(log n), sendo n o número de 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
Explicação: EA LETRA[C]
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
TIREI 10/10