Árvores Binárias de Busca

Prévia do material em texto

Você acertou 1 de 5 questões
Verifique o seu desempenho e continue
treinando! Você pode refazer o exercício
quantas vezes quiser.
Verificar Desempenho
A
B
C
1 Marcar para revisão
Ano: 2015 Banca: NUCEPE Órgão: SEFAZ � PI
Prova: Analista - Sistemas Pleno
Árvore AVL é uma árvore de busca
autobalanceada. Isso significa que:
As alturas das duas subárvores a
partir de cada nó diferem no máximo
em uma unidade.
Cada nó da árvore possui até três
descendentes.
As alturas das duas subárvores a
partir de cada nó diferem no máximo
em duas unidades.
Questão 1 de 5
Corretas �1�
Incorretas �4�
Em branco �0�
1 2 3 4 5
Exercicio Árvores Sair
03/08/2024, 11:58 estacio.saladeavaliacoes.com.br/exercicio/66ae459909dccd4f7ccc0b51/gabarito/
https://estacio.saladeavaliacoes.com.br/exercicio/66ae459909dccd4f7ccc0b51/gabarito/ 1/9
D
E
Pode possuir até duas raízes.
As alturas das duas subárvores a
partir de cada nó são exatamente
iguais.
Resposta incorreta
Opa! A alternativa correta é a letra
A. Confira o gabarito comentado!
Gabarito Comentado
A alternativa correta é a letra A. A árvore
AVL, nomeada em homenagem aos seus
inventores Adelson-Velskii e Landis, é uma
árvore de busca binária onde a diferença
de alturas de subárvores de qualquer nó é
garantida para ser no máximo uma
unidade. Se em qualquer momento elas
diferirem em mais de uma unidade,
rebalanceamento é feito para restaurar
essa propriedade. As outras alternativas
são incorretas pois não descrevem
corretamente as características de uma
árvore AVL.
2 Marcar para revisão
Seja a seguinte árvore binária de busca abaixo,
marque a sequência correta do percurso em
pós-ordem:
03/08/2024, 11:58 estacio.saladeavaliacoes.com.br/exercicio/66ae459909dccd4f7ccc0b51/gabarito/
https://estacio.saladeavaliacoes.com.br/exercicio/66ae459909dccd4f7ccc0b51/gabarito/ 2/9
A
B
C
D
E
23,24,25,26,27,29,28
25,24,27,23,26,29,30
25,24,23,27,26,28,29
23,24,26,29,28,27,25
23,24,29,26,28,25,27
Resposta incorreta
Opa! A alternativa correta é a letra
D. Confira o gabarito comentado!
Gabarito Comentado
O percurso em pós-ordem de uma árvore
binária é definido pela seguinte sequência
de ações: primeiro, percorre-se
recursivamente o lado esquerdo da raiz
considerada; em seguida, percorre-se
recursivamente o lado direito; e,
finalmente, visita-se a raiz. Nesse caso, a
sequência correta é a alternativa D�
23,24,26,29,28,27,25. Isso porque,
seguindo a regra de pós-ordem, primeiro
percorremos a subárvore esquerda
�23,24�, depois a subárvore direita
03/08/2024, 11:58 estacio.saladeavaliacoes.com.br/exercicio/66ae459909dccd4f7ccc0b51/gabarito/
https://estacio.saladeavaliacoes.com.br/exercicio/66ae459909dccd4f7ccc0b51/gabarito/ 3/9
A
B
C
�26,29,28,27) e, por fim, visitamos a raiz
�25�.
3 Marcar para revisão
As árvores binárias de busca são
especializações das árvores binárias que
permitem uma melhor organização dos
algoritmos de busca. Sobre a inserção de uma
nova chave em uma árvore binária de busca é
correto afirmar que:
Toda nova chave é inserida
obrigatoriamente na raiz.
Para determinar a posição da nova
chave é necessário calcular o
percurso em ordem simétrica da
árvore obtida. Com este percurso,
verifica-se se a sequência está
ordenada em ordem crescente. Caso
esteja, a posição da nova chave está
correta.
A complexidade da inserção é sempre
O(n), independentemente da altura da
árvore.
03/08/2024, 11:58 estacio.saladeavaliacoes.com.br/exercicio/66ae459909dccd4f7ccc0b51/gabarito/
https://estacio.saladeavaliacoes.com.br/exercicio/66ae459909dccd4f7ccc0b51/gabarito/ 4/9
D
E
Todas as chaves são inseridas em
folhas, a posição da folha é
determinada pela busca.
O algoritmo de inserção em árvores
binárias de busca é estático, isto é, é
necessário recalcular toda árvore para
inserir uma nova chave.
Resposta incorreta
Opa! A alternativa correta é a letra
D. Confira o gabarito comentado!
Gabarito Comentado
A alternativa correta é a D. Em uma árvore
binária de busca, todas as chaves são
inseridas em folhas. A posição da folha é
determinada pela busca. Isso ocorre
porque a árvore binária de busca é
projetada para otimizar a busca de dados.
Portanto, quando uma nova chave é
inserida, ela é colocada em uma posição
que facilita a busca futura. A chave não é
inserida na raiz (como afirmado na
alternativa A) nem requer o recálculo de
toda a árvore (como afirmado na
alternativa E�. Além disso, a complexidade
da inserção não é sempre O(n), como
afirmado na alternativa C. A complexidade
pode variar dependendo da altura da
árvore. Por fim, a posição da nova chave
não é determinada pelo percurso em
ordem simétrica da árvore, como afirmado
na alternativa B.
03/08/2024, 11:58 estacio.saladeavaliacoes.com.br/exercicio/66ae459909dccd4f7ccc0b51/gabarito/
https://estacio.saladeavaliacoes.com.br/exercicio/66ae459909dccd4f7ccc0b51/gabarito/ 5/9
A
B
C
D
E
4 Marcar para revisão
Seja o seguinte código em Python cujo principal
objetivo é implementar uma árvore binária.
Marque a alternativa correta quanto a execução
do código:
A árvore criada no código acima é
uma árvore binária de busca com
todas as folhas no último nível.
A árvore criada no código acima não é
binária de busca.
A árvore criada no código é binária de
busca com altura 6, isto é, com 6
níveis distintos.
Não é possível inferir a topologia da
árvore com base no código.
A classe NotArvore implementa regras
que garantem que os nós inseridos
respeitam a ordem de inserção dos
nós (maiores a direita e menores a
esquerda).
Resposta incorreta
03/08/2024, 11:58 estacio.saladeavaliacoes.com.br/exercicio/66ae459909dccd4f7ccc0b51/gabarito/
https://estacio.saladeavaliacoes.com.br/exercicio/66ae459909dccd4f7ccc0b51/gabarito/ 6/9
Opa! A alternativa correta é a letra
A. Confira o gabarito comentado!
Gabarito Comentado
Apesar de que a função NoArvore não tem
regras quanto à inserção dos nós, a forma
(e a ordem) de como os nós foram
inseridos �55�35�75�65�85�25�45) formam
uma árvore binária de busca.
Resultado:
5 Marcar para revisão
Seja a seguinte árvore, marque a opção correta
que indica o porquê a árvore abaixo não é uma
árvore binária de busca:
03/08/2024, 11:58 estacio.saladeavaliacoes.com.br/exercicio/66ae459909dccd4f7ccc0b51/gabarito/
https://estacio.saladeavaliacoes.com.br/exercicio/66ae459909dccd4f7ccc0b51/gabarito/ 7/9
A
B
C
D
E
Não é uma árvore binária de busca
pois está desbalanceada.
Não é uma árvore binária de busca
pois o nó 35 deveria estar inserido à
direita do nó 20.
Não é uma árvore binária de busca
pois essa árvore deve estar
perfeitamente balanceada.
Não é uma árvore binária de busca
pois esta árvore deve estar com os
níveis de suas folhas todas igualmente
perfeitas.
Não é uma árvore binária de busca
pois o nó 22 deveria estar inserido à
direita do nó 20.
Resposta correta
Parabéns, você selecionou a
alternativa correta. Confira o
gabarito comentado!
Gabarito Comentado
Uma árvore binária de busca são árvores
que obedecem às seguintes propriedades:
Dado um nó qualquer da árvore binária,
todos os nós à esquerda dele são
menores ou iguais a ele.
Dado um nó qualquer da árvore binária,
todos os nós à direita dele são maiores
ou iguais a ele.
03/08/2024, 11:58 estacio.saladeavaliacoes.com.br/exercicio/66ae459909dccd4f7ccc0b51/gabarito/
https://estacio.saladeavaliacoes.com.br/exercicio/66ae459909dccd4f7ccc0b51/gabarito/ 8/9
Observe que a sub-árvore 20�22 não
respeita a regra básica, portanto, o nó 22
deveria estar a direita do nó 20.
03/08/2024, 11:58 estacio.saladeavaliacoes.com.br/exercicio/66ae459909dccd4f7ccc0b51/gabarito/
https://estacio.saladeavaliacoes.com.br/exercicio/66ae459909dccd4f7ccc0b51/gabarito/ 9/9