Estrutura de Dados - Atividade 4

Prévia do material em texto

• Pergunta 1 
1 em 1 pontos 
 
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. 
 
Resposta Selecionada: 
.public String[] metodo(Pergunta p){}. 
Resposta Correta: 
.public String[] metodo(Pergunta p){}. 
Feedback 
da resposta: 
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 2 
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á. 
Feedba
ck da 
respost
a: 
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 3 
1 em 1 pontos 
 
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. 
 
Resposta Selecionada: 
. 
 
 
 
 
Resposta Correta: 
.
 
Feedback 
da 
resposta: 
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 4 
1 em 1 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 5 
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. 
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. 
 
 
• Pergunta 6 
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. 
Feedba
ck da 
respost
a: 
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 7 
1 em 1 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émo 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: 
. 
Feedba
ck da 
respost
a: 
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 8 
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: 
. 
Feedba
ck da 
respost
a: 
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 9 
1 em 1 pontos 
 
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. 
 
Resposta Selecionada: 
. 
Resposta Correta: 
. 
Feedba
ck da 
respost
a: 
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 
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. 
Feedback 
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).