Atividade 4 Estrutura de Dados

Prévia do material em texto

 Pergunta 1 
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. 
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. 
Feedback 
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 2 
1 em 1 pontos 
 
Uma operação muito comum nos sistemas computacionais é a operação de 
consulta ou busca. Ela, geralmente, recebe como parâmetro o elemento que 
se deseja procurar e um elemento de partida a partir do qual devemos 
buscar o elemento. Pensando nessa funcionalidade, consideremos a 
definição das classes “Produto” e “NoProduto” a seguir. 
 
Fonte: Elaborada pela autora, 2019. 
Foi implementado um método de busca por um elemento a partir do valor do 
atributo de “nome” do “Produto”. Os parâmetros recebidos são o nó visitado 
(“noProd”) e o nó com os dados procurados (“noProcurado”). Observe o 
próximo código. 
 
Fonte: Elaborada pela autora, 2019. 
A respeito desse código, assinale a alternativa verdadeira sobre o método 
“buscar()”, apresentado anteriormente. 
 
Resposta 
Selecionada: 
 
.O conteúdo do atributo “nome” não está sendo comparado 
corretamente. 
Resposta Correta: 
.O conteúdo do atributo “nome” não está sendo comparado 
corretamente. 
Feedback 
da resposta: 
Isso mesmo, sua resposta está correta! Os atributos do 
tipo string devem ser comparados com o uso dos métodos 
“equals” ou “equalsIgnoreCase”. O uso do operador “==” serve, 
no caso, para comparar as referências para os objetos, não o 
conteúdo das strings. 
 
 
 Pergunta 3 
1 em 1 pontos 
 
Sabemos que uma árvore binária de busca deve ser construída de forma 
que a seguinte regra seja preservada: o nó filho da esquerda de um nó raiz 
deve ser menor que o nó raiz por determinada chave; e o nó filho da direita 
deve ser sempre maior que o nó raiz. A relação de maior ou menor pode ser 
atribuída pelo valor da informação no nó ou por meio da definição de um 
atributo-chave do nó, o qual será utilizado como comparativo. 
Dessa forma, considere a árvore binária de busca na sequência. 
 
Fonte: Elaborada pela autora, 2019. 
Com base na figura anterior, qual é o nome do método de percurso em 
árvore que geraria a seguinte sequência de caracteres como saída: {A, B, C, 
D, E, F, G}? 
 
Resposta Selecionada: 
.Ordem simétrica. 
Resposta Correta: 
.Ordem simétrica. 
Feedback 
da resposta: 
Isso mesmo, resposta correta! No percurso em ordem simétrica, 
três passos são seguidos para percorrer uma árvore binária: 
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, os nós serão visitados de acordo com a ordem 
solicitada: {A, B, C, D, E, F, G}. 
 
 
 Pergunta 4 
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. 
Feedback 
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 5 
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á. 
Feedback 
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 6 
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: 
. 
Feedback 
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 7 
0 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: 
Infelizmente sua resposta está incorreta. A condição deparada, 
no caso, deve interromper o processo de busca pelo local de 
inserção do elemento. Procure estudar esse algoritmo, selecione 
um exemplo de árvore binária de busca e o execute passo a 
passo para entender seu funcionamento. Releia nosso material 
de estudos a respeito do assunto e tente responder novamente! 
 
 
 Pergunta 8 
1 em 1 pontos 
 
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? 
 
Resposta Selecionada: 
.1, 4, 2, 6, 9, 8, 5. 
Resposta Correta: 
.1, 4, 2, 6, 9, 8, 5. 
Feedback 
da resposta: 
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 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: 
. 
Feedback da 
resposta: 
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 
 
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. 
Feedback 
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.