Estrutura de Dados - Atv 04

Prévia do material em texto

• Pergunta 1 
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;”: 
 
( ) A árvore crescerá indefinidamente. 
( X ) O programa não compilará. 
( ) A árvore será transformada em uma lista circular. 
( ) O método retornará somente false. 
( ) Será levantada uma exceção quando o programa for executado. 
 
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 2 
Um método de busca que pode ser aplicado em uma árvore binária de busca 
é denominado pós-ordem. Este algoritmo pode ser enunciado a partir de três 
passos: percorrer a subárvore da esquerda em pós-ordem, percorrer a subárvore 
da direita em pós-ordem e visitar o nó raiz. 
Considere, então, a seguinte árvore binária de busca construída com valores 
numéricos. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Fonte: Elaborada pela autora, 2019. 
 
 
De acordo com a definição anterior, com base na figura retratada, qual é a 
sequência dos nós visitados em pós-ordem? 
 
 
( ) 1, 2, 3, 4, 5, 6, 7. 
( ) 4, 2, 5, 6, 3, 7, 1. 
( ) 4, 2, 1, 9, 8, 6, 5. 
( X ) 1, 4, 2, 6, 9, 8, 5. 
( ) 1, 2, 4, 5, 6, 8, 9. 
 
Resposta correta, parabéns! 
No percurso em pós-ordem, inicialmente, visitamos o nó da esquerda, que é uma 
subárvore com raiz (2). Como o algoritmo é recursivo, visitamos primeiro o nó 
mais à esquerda (1). Depois disso, o nó da direita é visitado (4) e, por fim, a raiz 
da subárvore da esquerda (2). Após visitar a subárvore da esquerda, vamos para 
a subárvore da direita. Primeiro é visitado o elemento mais à esquerda dessa 
subárvore (6), depois o elemento à direita (9) e, por último, a raiz da subárvore 
da direita (8). Somente ao final é visitada a raiz (5) da árvore. 
 
• Pergunta 3 
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? 
 
( ) A, C, B, E, F, G, D. 
( ) A, B, C, D, E, F, G. 
( X ) D, B, A, C, F, E, G. 
( ) D, F, G, E, B, C, A. 
( ) B, A, C, D, F, E, G. 
 
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 
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. 
 
( ) Produto[] noProd = new Produto();. 
( ) Produto noProd = new NoProduto();. 
( ) Produto noProd = new Produto();. 
( ) NoProduto noProd = new Produto[10];. 
( X ) NoProduto noProd = new NoProduto();. 
 
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 5 
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. 
 
 
( ) 
 
( ) 
 
( X ) 
 
( ) 
 
( X ) 
 
 
Infelizmente sua resposta está errada. 
Inserir um nó filho depende da criação do objeto e posterior inserção da 
referência ao nó filho e ao nó pai. Lembre-se de que você está criando a 
subárvore apresentado no esquema gráfico. Reveja o conteúdo e tente 
responder à questão novamente! 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
• Pergunta 6 
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. 
 
 
I. 
 
 
 
 
 
 
 
 
 
 
 
 
 
II. 
 
 
 
 
 
 
 
 
 
 
 
 
 
III. 
 
 
 
 
 
 
 
 
 
IV. 
 
 
 
 
 
 
 
 
 
 
 
 
Agora, assinale a alternativa que contém apenas as representações com 
árvores binárias de busca. 
 
( X ) I e IV, apenas. 
( ) II, III e IV, apenas. 
( ) III e IV, apenas. 
( ) II e III, apenas. 
( ) I e III, apenas. 
 
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 7 
Um tipo abstrato de dados, por definição, deve ter uma forma de armazenar 
a informação e um conjunto de operações que podem ser aplicadas sobre os 
dados armazenados. Na linguagem Java, um método fica declarado dentro da 
classe que define o tipo do objeto. Para se definir um método, deve ser informado 
um modificador de acesso, um tipo de retorno,o nome do método e o conjunto 
de parâmetros. 
Assim, considerando essas informações e nossos estudos, assinale a 
alternativa a seguir com a declaração de um método público na linguagem Java, 
o qual recebe um objeto do tipo “Pergunta” e retorna um vetor 
de strings corresponde às opções de resposta. 
 
( X ) public String[] metodo(Pergunta p){}. 
( ) public Pergunta metodo(String[]){}. 
( ) public metodo String(Pergunta){}. 
( ) public metodo Pessoa(String[] s){}. 
( ) public Pergunta metodo (String s){}. 
 
Sua resposta está correta, parabéns! 
Um método público indica sua definição com a palavra-chave “PUBLIC”, seguida 
do tipo de retorno, o nome do método e a lista de parâmetros. Além disso, entre 
abre e fecha parênteses, devem ser definidos os parâmetros. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
• Pergunta 8 
Imagine que você foi contratado para implementar um aplicativo que testa os 
conhecimentos da disciplina de Estrutura de Dados no ENEM. Para isso, você 
modelou uma classe “ EstruturaDadosEnem”, que contém os seguintes 
atributos: uma string contendo o texto da pergunta, um inteiro correspondente à 
área do conhecimento e um vetor de cinco strings para armazenar as opções de 
resposta e dicas de estudo. Como o objetivo é, ao final, indicar para os alunos 
quais as áreas de estudo que ele tem que se dedicar mais, você decidiu que a 
estrutura de dados mais propícia seria uma árvore. 
Considerando essas informações, assinale a alternativa a seguir que contém 
a implementação de uma classe “EstruturaDadosEnem”, conforme descrito, para 
ser inserida em uma árvore. 
 
( ) 
 
( ) 
 
( X ) 
 
( ) 
 
( ) 
 
Isso mesmo, sua resposta está correta! 
A definição de um nó de uma árvore é realizada pela criação de uma classe denominada 
“EstruturaDadosEnem”. No contexto apresentado, no escopo desta classe, devem ser 
declarados como atributos os dados que armazenam informações sobre ela: pergunta, 
área e opções de resposta. O atributo pergunta deve ser declarado como do tipo string, 
a área deve ser um inteiro (definido pelo tipo primitivo int) e precisa haver um vetor do 
tipo string que corresponde às opções de resposta ( String []). 
 
• Pergunta 9 
Por definiçã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. 
 
 
( ) 
 
( ) 
 
( X ) 
( ) 
 
( ) 
 
Isso mesmo, sua resposta está de acordo! 
Na árvore em questão, a subárvore da esquerda tem profundidade superior que 
a subárvore da direita em duas unidades, o que viola a característica base de 
uma árvore AVL. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
• Pergunta 10 
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: 
 
( ) 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 filho, no máximo. 
( ) os nós têm, exatamente, 2 filhos cada, com exceção dos nós folhas. 
( ) ela tem um tamanho pré-determinado, chamado “altura”. 
( X ) um nó de uma árvore binária pode ter 0, 1 ou 2 filhos, no máximo. 
 
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.