Atividade 4 (A4) - ESTRUTURA DE DADOS - (ANHEMBI MORUMBI UAM) CURTA SE LHE AJUDOU! ;D

Prévia do material em texto

Atividade 4 - ESTRUTURA DE DADOS
1. 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.
.Pós-ordem.
.Pré-ordem.
.Ordem simétrica.
.Busca sequencial.
.Busca aleatória.
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}.
2. 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.
· .V, F, V, F, V.
· .F, V, F, V, F.
· .F, F, V, V, F.
· .V, V, F, F, V.
· .V, F, F, F, V
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.
3. 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. I V. 
Agora, assinale a alternativa que contém apenas as representações com árvores binárias de busca.
· .I e IV, apenas.
· .II, III e IV, apenas.
· .II e III, apenas.
· .III e IV, 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. 
4. 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.
· .String[] opcoesPergunta = {“A”, “B”, “C”, “D”, “E”};.
· .int[] opcoesResposta = new opcoesResposta[5];.
· .Pergunta opcoesResposta = new Pergunta();.
· .String[5] opcoesPergunta = new String[];.
· .String[] opcoesPergunta = new String[];.
Muito bem, 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”};”.
5. Ao inserir um nó em uma árvore binária de busca, é necessário que a característica fundamental do tipo de estrutura seja preservada. Assim, para qualquer subárvore que for considerado o nó filho da esquerda, este deve ter um valor menor que o da raiz. De forma similar, o nó filho da direita tem que ter um valor acima.
A árvore de valores numéricos a seguir foi construída para que seja uma árvore binária de busca. Observe-a com atenção.
Fonte: Elaborada pela autora, 2019.
Agora, assinale a alternativa que contém os valores numéricos para X e Y, mantendo a árvore representada como uma árvore binária de busca.
.X = 10 e Y = 9.
· .X = 1 e Y = 11.
· .X = 9 e Y = 10.
· .X = 14 e Y = 3.
· .X = 3 e Y = 14.
6. 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ém o 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.
· 
· 
· 
· 
· 
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.
7. 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.
· .A*B/C.
· .A*C/B.
· .C*B/A.
· .C/A*B.
· .B/C*A.
8. 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, podemter 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?
· .TAD.
· . Object.
· . Class.
· . Typedef.
· . Type.
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.
9. 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, B, C, D, E, F, G.
· .D, B, A, C, F, E, G.
· .A, C, B, E, F, G, D.
· .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).
10. 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.
· 
· 
· 
· 
· 
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.