A4 ESTRUTURA DE DADOS FMU

Prévia do material em texto

• Pergunta 
0,25 em 0,25 pontos 
 
A inserção de um elemento em uma árvore binária de busca pode ser 
implementada por meio de um método recursivo. Este é aquele que tem uma 
chamada para o próprio método dentro da sua definição. Para que o algoritmo 
não execute indefinidamente, é 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. 
 
Resposta Selecionada: 
. 
Resposta Correta: 
. 
Feedback da 
resposta: 
Isso mesmo, resposta correta! Como a posição correta do elemento 
corresponde à posição do nó atual, é preciso confirmar se a 
posição está vazia, ou seja, se não tem outro nó a ocupando, para 
que o elemento seja inserido. 
 
 
• Pergunta 
0,25 em 0,25 pontos 
 
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ó filho da esquerda, este deve ter 
um valor menor que o da raiz. De forma similar, o nó filho 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. 
 
Resposta Selecionada: 
.X = 3 e Y = 14. 
Resposta Correta: 
.X = 3 e Y = 14. 
Feedback da 
resposta: 
Isso mesmo, resposta correta! Como o nó X está à esquerda do nó 
6, é necessário que X seja menor que 6, então, o valor 3 atende. De 
forma similar, já que Y está à direita de 12, seu valor deve ser 
maior que isso. Assim, o valor de Y igual a 14 é válido. 
 
 
• Pergunta 
0,25 em 0,25 pontos 
 
Uma árvore é um tipo abstrato de dado que possui um conjunto de nós ligados 
entre si por meio de referências aos nós, sendo estes conhecidos como filhos. 
Um nó pode não ter filhos, por isso, ele é chamado de “nó folha”. A referência 
que liga os nós na linguagem Java consiste no endereço de memória onde inicia 
a definição de outro objeto. 
Assim, a partir dessa definição, considere o nó “Pergunta” definido na figura a 
seguir. 
 
Fonte: Elaborada pela autora, 2019. 
Agora, assinale a alternativa que contém o trecho de código que implementa o 
método público “ehFolha()”, que retorna verdadeiro caso o nó do tipo “Pergunta” 
recebido como parâmetro seja do tipo folha. 
 
Resposta Selecionada: 
. 
Resposta Correta: 
. 
Feedback 
da 
resposta: 
Muito bem, sua resposta está correta! Um nó do tipo folha não tem 
nós filhos, sendo que isto pode ser comprovado pelo valor das 
referências dos atributos “noFilhoEsquerda” e “noFilhoDireita”. É 
necessário que os dois filhos sejam verificados: se eles estiverem 
apontando para algum objeto, então ele não é um nó folha. A 
indicação disso na linguagem Java é por meio da comparação com o 
valor null. 
 
 
• Pergunta 
0,25 em 0,25 pontos 
 
Comumente utilizadas para construir estruturas para avaliar expressões 
matemáticas, o percurso em árvores binárias por meio do método de busca de 
ordem simétrica é conhecido, também, como ordem central ou in-ordem. O 
algoritmo correspondente a esse percurso pode ser enunciado a partir de três 
passos: percorrer a subárvore da esquerda em ordem simétrica, visitar o nó raiz 
e percorrer a subárvore da direita em ordem simétrica. 
Dessa forma, considere a árvore binária de busca a seguir, construída com 
variáveis e operadores matemáticos. 
 
Fonte: Elaborada pela autora, 2019. 
Considerando a figura anterior, assinale a alternativa que contém a sequência 
dos nós visitados em ordem simétrica. 
 
Resposta Selecionada: 
.A*B/C. 
Resposta Correta: 
.A*B/C. 
Feedback 
da resposta: 
Isso mesmo, resposta correta! No percurso em ordem simétrica, o 
nó mais à esquerda (A) é o primeiro a ser visitado, depois, o nó raiz 
do nó esquerda (*) e, então, o nó à direita (B). O resultado dessa 
avaliação é o nó à esquerda. O processo continua: é visitado o nó 
raiz (/) e, por fim, o nó à direita (C). 
 
 
• Pergunta 
0,25 em 0,25 pontos 
 
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 afirmativas a 
seguir e marque V para as verdadeiras e F para as falsas. 
I. ( ) Para indicar que um nó tem filhos, é necessário criar um objeto daquele 
tipo e armazenar a referência do objeto criado. 
II. ( ) Ao criar um nó filho, é possível que este tenha outros nós filhos, desde que 
seja feita a alocação do elemento quando o nó pai for criado. 
III. ( ) Uma vez atribuído um nó filho, 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 filhos 
da esquerda e da direita são iguais a null. 
Agora, assinale a alternativa com a sequência correta. 
Resposta Selecionada: 
.V, F, F, F, V. 
Resposta Correta: 
.V, F, F, F, V. 
Feedback 
da resposta: 
Isso mesmo, sua resposta está correta! Um nó de uma árvore pode 
ter filhos, sendo que, para indicar isto, basta criarmos um novo nó e 
armazenar a referência para o objeto criado nos nós filhos da 
esquerda ou da direita. Quando não há referência para os nós filhos 
da esquerda e da direita, o nó é chamado de folha. A inexistência de 
referência é indicada pelo valor null.