Árvores exercicio

Prévia do material em texto

Você acertou 3 de 5 questões
Verifique o seu desempenho e continue treinando! Você pode refazer o exercício quantas
vezes quiser.
Verificar Desempenho
A
B
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.
C
D
E
As alturas das duas subárvores a partir de cada nó diferem no máximo em duas
unidades.
Pode possuir até duas raízes.
As alturas das duas subárvores a partir de cada nó são exatamente iguais.
Resposta correta
Parabéns, você selecionou a alternativa correta. 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
A
B
C
D
E
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
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:
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
A
B
C
D
E
á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.
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.
4 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:
Questão 3 de 5
Corretas �3�
Incorretas �2�
Em branco �0�
1 2 3 4 5
Exercicio Árvores Sair
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.
A
B
C
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.
5 Marcar para revisão
Seja a seguinte árvore binária de busca abaixo, marque a sequência correta do percurso
em pós-ordem:
23,24,25,26,27,29,28
25,24,27,23,26,29,30
25,24,23,27,26,28,29
D
E
23,24,26,29,28,27,25
23,24,29,26,28,25,27
Resposta correta
Parabéns, você selecionou a alternativa correta. 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 �26,29,28,27) e, por fim, visitamos a raiz �25�.