Atividade 4 - Estrutura de dados

Prévia do material em texto

Usuário JOHNNY WILLIAM LOURENCO PECEGO 
Curso GRA0246 ESTRUTURA DE DADOS GR0940211 - 
202110.ead-14724.01 
Teste ATIVIDADE 4 (A4) 
Iniciado 29/05/21 15:45 
Enviado 29/05/21 16:25 
Status Completada 
Resultado da 
tentativa 
10 em 10 pontos 
Tempo decorrido 40 minutos 
Resultados exibidos Respostas enviadas, Respostas corretas, Comentários 
• Pergunta 1 
1 em 1 pontos 
 
 Uma estrutura de dados do tipo árvore é formada por uma série de 
elementos ou nós que são ligados entre si por meio de arestas. O processo 
de construção de uma árvore começa pela definição do nó raiz e pela 
inserção dos nós filhos das subárvores da esquerda e da direita. 
Considere, por exemplo, o nó formado pelo nome das áreas da Ciência da 
Computação, que são derivadas da disciplina de Estrutura de Dados: 
Laboratório de Programação I e Análise de Algoritmos. 
 
 
 
Fonte: Elaborada pela autora, 2019. 
Agora, considere o trecho de código a seguir. Veja que ele representa a 
criação de uma árvore binária, cuja informação é armazenada em uma 
classe “NoDisciplina”, em um atributo do tipo string. 
 
 
 
Fonte: Elaborada pela autora, 2019. 
Sendo assim, assinale a alternativa a seguir que realiza a inserção dos 
filhos da esquerda e da direita, conforme apresentado no esquema da 
subárvore. 
Resposta Selecionada: 
. 
Resposta Correta: 
 
Comentário 
da resposta: 
Muito bem, sua resposta está de acordo! Para os nós filhos 
da esquerda e da direita, o primeiro passo é criar o objeto 
do tipo “NoDisciplina”, preencher o nome da disciplina por 
meio da chamada do método “setInformacao” — já que os 
atributos são privados — e, por fim, adicionar a referência 
do nó filho ao nó raiz. 
 
 
• Pergunta 2 
1 em 1 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. 
Comentário 
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 3 
1 em 1 pontos 
 
 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 definição anterior e nossos estudos sobre o assunto, 
considerando a figura retratada, qual é a sequência dos nós visitados em 
pré-ordem? 
Resposta Selecionada: 
.D, B, A, C, F, E, G. 
Resposta Correta: 
.D, B, A, C, F, E, G. 
Comentário 
da resposta: 
Isso mesmo, resposta correta! No percurso em pré-ordem, 
o nó raiz é o primeiro a ser visitado. Em seguida, é visitada 
a subárvore da esquerda. Iniciando pela raiz (B), vamos, 
na sequência, visitar o elemento mais à esquerda (A) e, 
depois, o nó à direita (C). O resultado dessa avaliação é o 
nó à esquerda. O processo continua: é visitado o nó raiz (/) 
e, por fim, o nó à direita (C). O mesmo é feito para a 
subárvore da direita: primeiro é visitada a raiz (F), depois o 
nó da esquerda (E) e, por último, o nó mais à direita (G). 
 
 
• Pergunta 4 
1 em 1 pontos 
 
 O processo de inserção de um nó em uma árvore binária de busca viabiliza 
que o processo de busca por um elemento tenha melhor performance 
que uma busca sequencial, se os dados forem dispostos em uma estrutura 
mais simples, como um vetor. Por performance, podemos entender como o 
tempo para se encontrar o elemento e o número de comparações que 
precisam ser feitas, a fim de se achar o item procurado. 
Com base nessas informações e em nossos estudos sobre o assunto, 
analise os esquemas de árvores apresentados a seguir. 
Abaixo 5 itens listados com letras romanas. Cada item contém o desenho 
de uma árvore binária em que os nós são representados por círculos e as 
conexões são representadas por setas. Dentro de cada círculo tem uma 
 
letra maiúscula representando o valor armazenado naquele nó. 
Enumerando cada item temos: 
 
I. 
II. 
III. 
IV. 
Agora, assinale a alternativa que contém apenas as representações com 
árvores binárias de busca. 
Resposta Selecionada: 
.I e IV, apenas. 
Resposta Correta: 
.I e IV, apenas. 
Comentário 
da resposta: 
Isso mesmo, resposta correta! As árvores binárias de 
busca devem seguir a regra que o nó filho da esquerda 
deve sempre ser menor que o nó raiz; enquanto o nó raiz 
deve ser menor que o nó filho da direita. Tal regra precisa 
ser aceita em todas as subárvores da esquerda e da 
direita. 
 
 
• Pergunta 5 
1 em 1 pontos 
 
 A árvore é um tipo abstrato de dados em que cada um dos elementos que 
detém a informação armazenada é denominado “nó”. Os nós são ligados 
entre si por meio de arestas. Quando isto ocorre, dizemos que o nó possui 
filhos e estes, por sua vez, podem ter outros filhos ou não. Quando o nó 
não tem nós filhos, ele é denominado “nó folha”. Além disso, dependendo 
do escopo do sistema, temos que criar um tipo específico para armazenar 
determinada informação. 
Assim, com base em nossos estudos, qual é a palavra-chave que deve ser 
utilizada para iniciar um tipo abstrato de dados que corresponde a um nó 
da árvore na linguagem Java? 
 
Resposta Selecionada: 
. Class. 
Resposta Correta: 
.Class. 
 
Comentário 
da resposta: 
Isso mesmo, sua resposta está correta! Em um nó de uma 
árvore, além da informação a ser armazenada, são 
declaradas as referências para os nós filhos por meio de 
atributos. Para definir esse conjunto de informações em um 
único elemento, deve-se criar uma classe Java. Para isso, 
precisamos iniciar sua definição com a palavra-chave 
“ class”, seguida do nome da classe. 
 
• Pergunta 6 
1 em 1 pontos 
 
 Podemos dizer que uma árvore é binária quando cada um dos seus nós 
tem 0, 1 ou 2 filhos. Com esta característica, é possível definir uma 
estrutura de dados em que, além das informações armazenadas, tenhamos 
acesso ao filho da esquerda e da direita. 
A figura a seguir representa um nó “Produto”, com a referência para os 
outros filhos desse “Produto”: “filhoEsquerda” e “filhoDireita”. 
 
Fonte: Elaborada pela autora, 2019. 
Temos, ainda, que um tipo especial de árvore binária é chamado de AVL. 
Assinale a alternativa a seguir que contém a principal característica desse 
tipo de árvore. 
 
Resposta Selecionada: 
.A árvore AVL é balanceada. 
Resposta Correta: 
.A árvore AVL é balanceada. 
Comentário da 
resposta: 
Sua resposta está de acordo, parabéns! A árvore AVL é 
dita balanceada, ou seja, a distância entre o nó raiz e os 
nós folhas de qualquer subárvore se difere de, no 
máximo, uma unidade. 
 
 
• Pergunta 7 
1 em 1 pontos 
 
 A declaração de uma classe para armazenar a informação de um nó na 
árvore foi realizada na classe “Produto”, conforme vemos na figura na 
sequência. 
 
 
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 definiçã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. 
Resposta Selecionada: 
.NoProduto noProd = new NoProduto();. 
Resposta Correta: 
.NoProduto noProd = new NoProduto();. 
Comentário 
da resposta: 
Isso mesmo, sua resposta está correta! Foi solicitada a 
criação de um objeto do tipo “NoProduto”. Assim, nesse 
caso, o tipo “NoProduto” deve ser utilizado dos dois lados 
da igualdade. Temos, então, “NoProduto noProd = new 
NoProduto();”. 
 
 
• Pergunta 8 
1 em 1 pontos 
 
 Em estruturas de dados, de forma geral, tão importante quanto o 
armazenamento dos dados, é necessário definir 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 verifica se a árvore está vazia. 
Veja com atenção a definiçã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;”. 
Resposta Selecionada: 
.O programa não compilará. 
Resposta Correta: 
.O programa não compilará. 
Comentário 
da resposta: 
Muito bem, sua resposta está correta! O método “ehVazia” 
tem sempre que retornar um valor booleano para todos os 
possíveis fluxos de execução do programa. Como há uma 
cláusula if, é necessário indicar um retorno booleano se o 
programa não entrar nas condições exigidas. Assim, se for 
retirado comando “return true”, o programa não compilará. 
 
 
• Pergunta 9 
1 em 1 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. 
Comentário 
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. 
 
 
• Pergunta 10 
1 em 1 pontos 
 
 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 
afirmar que: 
 
Resposta 
Selecionada: 
 
.um nó de uma árvore binária pode ter 0, 1 ou 2 
filhos, no máximo. 
Resposta Correta: 
.um nó de uma árvore binária pode ter 0, 1 ou 2 
filhos, no máximo. 
Comentário 
da resposta: 
Sua resposta está exata, muito bem! A árvore é dita 
binária quando todos os nós da árvore têm 0, 1 ou 2 filhos, 
no máximo. Por este motivo, podemos modelar um nó de 
uma árvore binária com uma referência para o nó filho da 
esquerda e outra para o da direita. 
 
 
Sábado, 29 de Maio de 2021 16h25min59s BRT