ESTRUTURA DE DADOS ATIVIDADES 4

Prévia do material em texto

ATIVIDADE 4
	
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:
	
	
	Feedback da resposta:
	Não é isso, sua resposta está equivocada. As árvores AVL podem ter subárvores da esquerda e da direita com a mesma altura ou, até mesmo, com uma unidade de diferença. Lembre-se de que a altura da árvore é contada a partir do nó raiz. Cada filho diretamente ligado à esquerda de um nó raiz na subárvore está na mesma altura que o outro filho da direita. Releia o conteúdo sobre o assunto e tente responder outra vez!
Pergunta 2
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ó 
· Pergunta 3
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.
	
	
	
· Pergunta 4
0 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 Pergunta metodo(String[]){}.
	Resposta Correta:
	 
.public String[] metodo(Pergunta p){}.
	Feedback da resposta:
	Não é isso, sua resposta está incorreta. Os métodos em um tipo abstrato de dados no modelo árvore opera sobre os elementos armazenados em sua definição. O tipo de retorno deve ser a segunda informação e, neste caso, é um vetor de elementos string. O parâmetro precisa ser sempre informado entre o abre e fecha parênteses. A construção correta da assinatura do método viabilizará o acesso às informações do nó da árvore. Releia nosso material de estudos e tente responder novamente à questão!
	
	
	
· Pergunta 5
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 6
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).
Pergunta 7
1 em 1 pontos
	
	
	
	Para a definição de um nó em uma árvore, precisamos, inicialmente, encapsular a informação armazenada em um novo tipo de dado, ou seja, em uma nova classe Java. Isto é possível por meio da declaração dos atributos na classe, que nada mais são do que variáveis presentes em todos os objetos de determinado tipo.
Os atributos são variáveis, posições na memória do computador que podem armazenar dados, formadas por quatro elementos: nome, tipo, tamanho e valor. Na linguagem Java, é possível, ainda, definir um modificador de visibilidade se a variável for um atributo da classe, sendo os valores permitidos public, private, protected
ou default.
A figura a seguir, por exemplo, traz a declaração de uma classe “Pergunta”, com três atributos: texto da pergunta, alternativas e dicas sobre como responder. Observe.
	
	
	
	
	
	
	
	
	
	Fonte: Elaborada pela autora, 2019.
Sendo assim, assinale a alternativa a seguir que contém a inicialização correta do atributo “opcoesResposta” com cinco opções em um objeto do tipo “Pergunta” na linguagem Java.
		Resposta Selecionada:
	 
.String[] opcoesPergunta = {“A”, “B”, “C”, “D”, “E”};.
	Resposta Correta:
	 
.String[] opcoesPergunta = {“A”, “B”, “C”, “D”, “E”};.
	Feedback da resposta:
	Muitobem, sua resposta está correta! Um vetor de elementos do tipo string pode ser inicializado informando o tipo string dos dois lados da igualdade e indicando o número de elementos no lado direito da igualdade, ou pode ser inicializado com os valores diretamente do lado direito. No caso em questão, temos que “String[] opcoesPergunta = {“A”, “B”, “C”, “D”, “E”};”.
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
	
	
	
	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();.
	Feedback 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 10
0 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 método retornará somente false.
	Resposta Correta:
	 
.O programa não compilará.
	Feedback da resposta:
	Não é isso, sua resposta está errada. Lembre-se de que um método precisa sempre retornar o valor definido como retorno se ele for diferente de void. Reveja o conteúdo a respeito do assunto e responda novamente à questão!