Estrutura de Dados: Árvore Binária

Prévia do material em texto

21/06/2020 Fazer teste: ATIVIDADE 4 (A4) – GRA0246 ESTRUTURA DE ...
https://anhembi.blackboard.com/webapps/late-Course_Landing_Page_Course_100-BBLEARN/Controller 1/6
ç
Descrição
Instruções
Várias tentativas Não permitido. Este teste só pode ser feito uma vez.
Forçar conclusão Este teste pode ser salvo e retomado posteriormente.
PERGUNTA 1
O termo “árvore”, da vida real, pode ser associado ao tipo de estrutura de dados em certos
aspectos. Ambos têm um elemento raiz de onde saem todos os galhos ou as conexões
para os nós da árvore. Estes, por sua vez, podem ser entendidos como partes da árvore
que podem se desmembrar em mais partes, formando o que chamamos de “subárvores”
de uma árvore. 
Dessa forma, em relação ao tipo de árvore denominada binária, podemos a�rmar que:
.recebe esse nome porque os nós podem assumir os valores 0 ou 1.
.um nó de uma árvore binária pode ter 0 ou 1 �lho, no máximo.
.um nó de uma árvore binária pode ter 0, 1 ou 2 �lhos, no máximo.
.ela tem um tamanho pré-determinado, chamado “altura”.
.os nós têm, exatamente, 2 �lhos cada, com exceção dos nós folhas.
1 pontos   Salva
PERGUNTA 2
Em estruturas de dados, de forma geral, tão importante quanto o armazenamento dos
dados, é necessário de�nir um conjunto mínimo de métodos que operam sobre eles. No
caso de uma árvore binária, um método utilitário muito comum é aquele que veri�ca se a
árvore está vazia. 
Veja com atenção a de�nição do método “ehVazia” a seguir, que recebe como parâmetro o
nó raiz da árvore. 
 
Fonte: Elaborada pela autora, 2019. 
Considerando a implementação anterior, assinale a alternativa que relata corretamente o
que acontece com o programa se for removido o comando “return true;”.
.O método retornará somente false.
.A árvore crescerá inde�nidamente.
.Será levantada uma exceção quando o programa for executado.
.O programa não compilará.
.A árvore será transformada em uma lista circular.
1 pontos   Salva
PERGUNTA 3
A inserção de um elemento em uma árvore binária de busca pode ser implementada por
1 pontos   Salva
 Estado de Conclusão da Pergunta:
Clique em Enviar para enviar. Clique em Salvar todas as respostas para salvar todas as respostas.
Salvar todas as re
Not-Casa
Realce
21/06/2020 Fazer teste: ATIVIDADE 4 (A4) – GRA0246 ESTRUTURA DE ...
https://anhembi.blackboard.com/webapps/late-Course_Landing_Page_Course_100-BBLEARN/Controller 2/6
 se ção de u e e e to e u a á o e b á a de busca pode se p e e tada po
meio de um método recursivo. Este é aquele que tem uma chamada para o próprio
método dentro da sua de�nição. Para que o algoritmo não execute inde�nidamente, é
necessário que seja inserida uma condição de parada. 
Veja o trecho de código a seguir para inserção de um nó em uma árvore binária de busca. 
 
Fonte: Elaborada pela autora, 2019. 
Com base no código anterior, assinale a alternativa que contém o comando que deve ser
inserido como cláusula condicional do comando if (em destaque no código), para que o
algoritmo tenha uma condição de parada.
.
.
.
.
.
PERGUNTA 4
Ao inserir um nó em uma árvore binária de busca, é necessário que a característica
fundamental do tipo de estrutura seja preservada. Assim, para qualquer subárvore que
for considerado o nó �lho da esquerda, este deve ter um valor menor que o da raiz. De
forma similar, o nó �lho da direita tem que ter um valor acima. 
A árvore de valores numéricos a seguir foi construída para que seja uma árvore binária de
busca. Observe-a com atenção. 
 
Fonte: Elaborada pela autora, 2019. 
Agora, assinale a alternativa que contém os valores numéricos para X e Y, mantendo a
árvore representada como uma árvore binária de busca.
.X = 9 e Y = 10.
.X = 3 e Y = 14.
.X = 14 e Y = 3.
.X = 10 e Y = 9.
.X = 1 e Y = 11.
1 pontos   Salva
 Estado de Conclusão da Pergunta:
Clique em Enviar para enviar. Clique em Salvar todas as respostas para salvar todas as respostas.
Salvar todas as re
Not-Casa
Nota
X = 3 e Y = 14.
21/06/2020 Fazer teste: ATIVIDADE 4 (A4) – GRA0246 ESTRUTURA DE ...
https://anhembi.blackboard.com/webapps/late-Course_Landing_Page_Course_100-BBLEARN/Controller 3/6
PERGUNTA 5
Por de�nição, uma árvore binária é denominada AVL quando, para qualquer nó, as alturas
de suas duas subárvores (esquerda e direita) sejam diferentes em módulo de até uma
unidade. Na literatura relacionada, essa propriedade é comumente dita como sendo de
balanceamento da árvore, já que, no processo de busca, o tempo gasto para avaliar as
árvores da esquerda e direita é bem similar. 
Sendo assim, com base em nossos estudos sobre o assunto, assinale a alternativa a seguir
que contém um exemplo de árvore binária, mas que não é do tipo árvore AVL.
.
. 
.
.
1 pontos   Salva
 Estado de Conclusão da Pergunta:
Clique em Enviar para enviar. Clique em Salvar todas as respostas para salvar todas as respostas.
Salvar todas as re
21/06/2020 Fazer teste: ATIVIDADE 4 (A4) – GRA0246 ESTRUTURA DE ...
https://anhembi.blackboard.com/webapps/late-Course_Landing_Page_Course_100-BBLEARN/Controller 4/6
.
PERGUNTA 6
Para a de�nição de um nó em uma árvore, precisamos, inicialmente, encapsular a
informação armazenada em um novo tipo de dado, ou seja, em uma nova classe Java. Isto
é possível por meio da declaração dos atributos na classe, que nada mais são do que
variáveis presentes em todos os objetos de determinado tipo. 
Os atributos são variáveis, posições na memória do computador que podem armazenar
dados, formadas por quatro elementos: nome, tipo, tamanho e valor. Na linguagem Java, é
possível, ainda, de�nir um modi�cador de visibilidade se a variável for um atributo da
classe, sendo os valores permitidos public, private, protected 
ou default. 
A �gura a seguir, por exemplo, traz a declaração de uma classe “Pergunta”, com três
atributos: texto da pergunta, alternativas e dicas sobre como responder. Observe. 
 
Fonte: Elaborada pela autora, 2019. 
Sendo assim, assinale a alternativa a seguir que contém a inicialização correta do atributo
“opcoesResposta” com cinco opções em um objeto do tipo “Pergunta” na linguagem Java.
.int[] opcoesResposta = new opcoesResposta[5];.
.Pergunta opcoesResposta = new Pergunta();.
.String[] opcoesPergunta = new String[];.
.String[] opcoesPergunta = {“A”, “B”, “C”, “D”, “E”};.
.String[5] opcoesPergunta = new String[];.
1 pontos   Salva
PERGUNTA 7
A declaração de uma classe para armazenar a informação de um nó na árvore foi realizada
na classe “Produto”, conforme vemos na �gura na sequência. 
 
1 pontos   Salva
 Estado de Conclusão da Pergunta:
Clique em Enviar para enviar. Clique em Salvar todas as respostas para salvar todas as respostas.
Salvar todas as re
Not-Casa
Realce
21/06/2020 Fazer teste: ATIVIDADE 4 (A4) – GRA0246 ESTRUTURA DE ...
https://anhembi.blackboard.com/webapps/late-Course_Landing_Page_Course_100-BBLEARN/Controller 5/6
Fonte: Elaborada pela autora, 2019. 
As informações, nesse caso, são o nome do produto e um código numérico. A partir dessa
de�nição, dentro da classe “NoProduto”, foi declarado um objeto que contém as
informações e outras duas referências para outros elementos: para as subárvores da
esquerda e da direita. 
Sendo assim, assinale a alternativa que contém a linha de código para declarar um nó de
uma árvore de produtos de um uma loja de departamentos.
.Produto noProd = new Produto();.
.NoProduto noProd = new Produto[10];.
.Produto noProd = new NoProduto();.
.NoProduto noProd = new NoProduto();.
.Produto[] noProd = new Produto();.
PERGUNTA 8
Podemos dizer que uma árvore é binária quando cada um dos seus nós tem 0, 1 ou 2
�lhos. Com esta característica, é possível de�nir uma estrutura de dados em que, além
das informações armazenadas, tenhamos acesso ao �lho da esquerda e da direita. 
A �gura a seguir representa um nó “Produto”, com a referência para os outros �lhos desse
“Produto”: “�lhoEsquerda” e “�lhoDireita”. 
 
Fonte: Elaborada pela autora, 2019. 
Temos, ainda, que um tipo especial de árvore binária é chamado de AVL. Assinale a
alternativa a seguirque contém a principal característica desse tipo de árvore.
.A árvore AVL tem apenas altura 2.
.A árvore AVL tem apenas nós folhas.
.A árvore AVL tem apenas o nó raiz.
.A árvore AVL pode ter mais de 2 �lhos.
.A árvore AVL é balanceada.
1 pontos   Salva
PERGUNTA 9
O tipos abstratos de dados no modelo árvore tem como principal característica o fato de
que os elementos que a constitui, denominados “nós”, são ligados entre si por estruturas
de encadeamento. Este é possível graças ao mecanismo de referência da linguagem Java. 
Sobre esse processo, com base em nossos estudos, analise as a�rmativas a seguir e
marque V para as verdadeiras e F para as falsas. 
I. (   ) Para indicar que um nó tem �lhos, é necessário criar um objeto daquele tipo e
armazenar a referência do objeto criado. 
II. (   ) Ao criar um nó �lho, é possível que este tenha outros nós �lhos, desde que seja feita
a alocação do elemento quando o nó pai for criado. 
III. (   ) Uma vez atribuído um nó �lho, não é possível alterar ou remover o elemento, já que
a estrutura tem que ser mantida. 
IV. (   ) Uma árvore é dita binária quando os valores armazenados em cada um dos nós são
sequências de 0’s e 1’s. 
V. (   ) O chamado “nó folha” é aquele em que as referências para os nós �lhos da esquerda
e da direita são iguais a null. 
Agora, assinale a alternativa com a sequência correta.
.V, V, F, F, V.
1 pontos   Salva
 Estado de Conclusão da Pergunta:
Clique em Enviar para enviar. Clique em Salvar todas as respostas para salvar todas as respostas.
Salvar todas as re
Not-Casa
Nota
V, F, F, F, V.
21/06/2020 Fazer teste: ATIVIDADE 4 (A4) – GRA0246 ESTRUTURA DE ...
https://anhembi.blackboard.com/webapps/late-Course_Landing_Page_Course_100-BBLEARN/Controller 6/6
.V, F, F, F, V.
.V, F, V, F, V.
.F, F, V, V, F.
.F, V, F, V, F.
PERGUNTA 10
As árvores binárias de busca podem ser percorridas por meio do método de busca
denominado pré-ordem. Este algoritmo pode ser enunciado a partir de três passos: visitar
o nó raiz, percorrer a subárvore da esquerda em pré-ordem e percorrer a subárvore da
direita em pré-ordem. 
Assim, considere a seguinte árvore binária de busca construída com letras do alfabeto. 
 
Fonte: Elaborada pela autora, 2019. 
De acordo com a de�nição anterior e nossos estudos sobre o assunto, considerando a
�gura retratada, qual é a sequência dos nós visitados em pré-ordem?
.D, B, A, C, F, E, G.
.A, B, C, D, E, F, G.
.A, C, B, E, F, G, D.
.D, F, G, E, B, C, A.
.B, A, C, D, F, E, G.
1 pontos   Salva
 Estado de Conclusão da Pergunta:
Clique em Enviar para enviar. Clique em Salvar todas as respostas para salvar todas as respostas.
Salvar todas as re