Árvores de Busca

Prévia do material em texto

16/04/2024, 12:22 wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/
https://wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/ 1/15
Você acertou 10 de 10 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
1 Marcar para revisãopara revisar antes de finalizar
Ano: 2015 Banca: MP�RS Órgão: MP�RS Prova:
Técnico em informática � Sistemas
Imagine que temos números de 1 a 100 em uma
árvore de pesquisa binária �ABP�. Agora
queremos procurar o número 50. Assinale a
alternativa que apresenta a possível sequência
de elementos da árvore consultada.
42 � 60 � 20 � 48 � 50.
40 � 10 � 45 � 30 � 50.
40 � 60 � 45 � 48 � 50.
40 � 15 � 45 � 30 � 50.
42 � 60 � 20 � 30 � 50.
Questão 1 de 10
Corretas �10�
Em branco �0�
1 2 3 4 5
6 7 8 9 10
Exercicio Árvores Sair
16/04/2024, 12:22 wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/
https://wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/ 2/15
Resposta correta
Parabéns, você selecionou a
alternativa correta. Confira o
gabarito comentado!
Gabarito Comentado
A sequência correta para encontrar o
número 50 em uma árvore de pesquisa
binária �ABP� é 40 � 60 � 45 � 48 � 50. Em
uma ABP, cada nó tem um valor. Se o valor
que estamos procurando é menor que o
valor do nó, seguimos para a esquerda. Se
o valor que estamos procurando é maior,
seguimos para a direita. Neste caso,
começamos com 40 (menor que 50�,
depois vamos para 60 (maior que 50�,
depois para 45 (menor que 50�, depois
para 48 (menor que 50� e finalmente
chegamos a 50.
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:
16/04/2024, 12:22 wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/
https://wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/ 3/15
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 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�.
3 Marcar para revisão
16/04/2024, 12:22 wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/
https://wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/ 4/15
A
B
C
D
E
Ano: 2012 Banca: IDECAN Órgão: BANESTES
Prova: Analista de Tecnologia da Informação �
Desenvolvimento de Sistemas
Árvore de pesquisa é uma estrutura de dados
eficiente para armazenar informação, sendo
particularmente adequada quando existe a
necessidade de considerar todos ou alguma
combinação de registros. Assinale uma
combinação correta desses registros.
Acesso direto e sequencial eficientes,
facilidade de inserção e retirada de
registro, boa taxa de utilização de
memória, utilização de memória
primária e secundária.
Utilização de algoritmos de ordenação
eficientes.
Utilização de estruturas de dados
como lista, pilha e fila.
Não é necessário indexar os registros.
As operações de inserir, retirar e
pesquisar são definidas.
Resposta correta
Parabéns, você selecionou a
alternativa correta. Confira o
gabarito comentado!
Gabarito Comentado
A alternativa correta é a letra A. A árvore de
pesquisa é uma estrutura de dados que
permite um acesso direto e sequencial
eficientes, além de facilitar a inserção e
16/04/2024, 12:22 wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/
https://wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/ 5/15
A
B
C
retirada de registros. Ela também apresenta
uma boa taxa de utilização de memória,
podendo utilizar tanto a memória primária
quanto a secundária. As demais
alternativas não descrevem corretamente
as características e funcionalidades de uma
árvore de pesquisa.
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.
16/04/2024, 12:22 wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/
https://wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/ 6/15
D
E
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.
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
Escola de Formação Complementar do Exército
� EsFCEx Prova: CFO � Informática � 2019
Árvores binárias podem ser usadas para
representar expressões aritméticas. Como um
exemplo de expressão, podemos ter: a * b + f
sen - h * j com os elementos enumerados "Em-
16/04/2024, 12:22 wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/
https://wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/ 7/15
A
B
C
D
E
ordem". Nesse caso, a árvore binária terá como
raiz:
O átomo a
O átomo j
O átomo +
O átomo sen
O átomo *
Resposta correta
Parabéns, você selecionou a
alternativa correta. Confira o
gabarito comentado!
Gabarito Comentado
Na representação de expressões
aritméticas por meio de árvores binárias, a
raiz da árvore é o operador principal da
expressão. No caso da expressão dada, o
operador principal é o sinal de adição (+),
que é o responsável por unir as duas partes
da expressão. Portanto, o átomo + é a raiz
da árvore binária que representa a
expressão aritmética apresentada.
6 Marcar para revisão
16/04/2024, 12:22 wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/
https://wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/ 8/15
A
B
C
D
E
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 correta
Parabéns, você selecionou a
alternativa correta. Confira ogabarito comentado!
Gabarito Comentado
16/04/2024, 12:22 wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/
https://wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/ 9/15
A
B
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.
7 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.
16/04/2024, 12:22 wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/
https://wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/ 10/15
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.
8 Marcar para revisão
Seja o seguinte código em Python cujo principal
objetivo é implementar uma árvore binária.
16/04/2024, 12:22 wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/
https://wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/ 11/15
A
B
C
D
E
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 correta
Parabéns, você selecionou a
alternativa correta. Confira o
gabarito comentado!
16/04/2024, 12:22 wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/
https://wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/ 12/15
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:
9 Marcar para revisão
As rotações são operações fundamentais para
ajuste da propriedade AVL. Analise as
afirmativas abaixo.
I � A inserção de uma nova chave em uma
árvore AVL pode desregular diversos nós no
caminho da raiz até a folha onde a nova chave
foi inserida. Só é necessário aplicar uma
rotação no nó mais profundo desregulado.
Porque
II � A aplicação da rotação resulta em uma
subárvore com a mesma altura da subárvore
original, isto é, antes da inserção da nova
chave.
Marque a alternativa correta.
16/04/2024, 12:22 wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/
https://wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/ 13/15
A
B
C
D
E
As duas afirmativas estão corretas e a
segunda não justifica a primeira.
As duas afirmativas estão corretas e a
segunda justifica a primeira.
As duas afirmativas são falsas.
A primeira afirmativa é verdadeira e a
segunda afirmativa é falsa.
A primeira afirmativa é falsa e a
segunda afirmativa é verdadeira.
Resposta correta
Parabéns, você selecionou a
alternativa correta. Confira o
gabarito comentado!
Gabarito Comentado
As operações de rotação em uma árvore
AVL são fundamentais para manter o
equilíbrio da árvore. Quando uma nova
chave é inserida, pode ocorrer um
desequilíbrio em vários nós no caminho da
raiz até a folha onde a nova chave foi
inserida. No entanto, é suficiente aplicar
uma rotação no nó mais profundo que está
desequilibrado para corrigir a situação
(afirmativa I�. A rotação resulta em uma
subárvore com a mesma altura da
subárvore original antes da inserção da
nova chave (afirmativa II�. Portanto, a
segunda afirmativa justifica a primeira, pois
explica o motivo pelo qual apenas uma
rotação é necessária para corrigir o
16/04/2024, 12:22 wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/
https://wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/ 14/15
A
B
C
D
E
desequilíbrio causado pela inserção de uma
nova chave.
10 Marcar para revisão
Ano: 2020 Banca: Instituto AOCP Órgão:
Prefeitura de Nova Hamburgo � RS Prova:
Analista de Desenvolvimento � Analista de
Sistemas
Analise a seguinte árvore binária e assinale a
alternativa correta.
"A" é filho de todos.
"B" e "C" são caules da árvore.
"B" tem grau de saída 3 e ¿C¿ grau 2.
TA é a subárvore enraizada em "A",
portanto toda a árvore.
Com exceção do nó "A", que é raiz, os
demais nós são conhecido como
folhas
16/04/2024, 12:22 wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/
https://wyden.saladeavaliacoes.com.br/exercicio/661e9656139d33d91491cf45/gabarito/ 15/15
Resposta correta
Parabéns, você selecionou a
alternativa correta. Confira o
gabarito comentado!
Gabarito Comentado
Resposta correta: TA é a subárvore
enraizada em "A", portanto toda a árvore.