Desempenho em Questões de Árvores

Prévia do material em texto

Você acertou 0 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
D
E
A
B
C
D
E
A
B
C
D
E
A
B
C
D
E
A
B
C
D
E
1 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.
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.
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:
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 (26,29,28,27) e,
por fim, visitamos a raiz (25).
3 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.
Pode possuir até duas raízes.
As alturas das duas subárvores a partir
de cada nó são exatamente iguais.
Questão não respondida
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.
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:
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.
Questão não respondida
Opa! A alternativa correta é a letra E.
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.
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 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).
Questão não respondida
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:
Questões
Exercicio
Árvores
05/11/2024, 19:46
Página 1 de 1