Árvores Binárias de Busca e Métodos em Java

Prévia do material em texto

PERGUNTA 1
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.
	
	
	.I e III, apenas.
	
	
	.I e IV, apenas.
	
	
	.III e IV, apenas.
	
	
	.II, III e IV, apenas.
	
	
	.II e III, apenas.
1 pontos   
PERGUNTA 2
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.
	
	
	.int[] opcoesResposta = new opcoesResposta[5];.
	
	
	.Pergunta opcoesResposta = new Pergunta();.
	
	
	.String[] opcoesPergunta = new String[];.
	
	
	.String[] opcoesPergunta = {“A”, “B”, “C”, “D”, “E”};.
	
	
	.String[5] opcoesPergunta = new String[];.
1 pontos   
PERGUNTA 3
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.
	
	
	. 
	
	
	. 
	
	
	. 
	
	
	. 
	
	
	. 
1 pontos   
PERGUNTA 4
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.
	
	
	.public metodo String(Pergunta){}.
	
	
	.public metodo Pessoa(String[] s){}.
	
	
	.public Pergunta metodo (String s){}.
	
	
	.public String[] metodo(Pergunta p){}.
	
	
	.public Pergunta metodo(String[]){}.
1 pontos   
PERGUNTA 5
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.
	
	
	. 
	
	
	. 
	
	
	. 
	
	
	. 
	
	
	. 
1 pontos   
PERGUNTA 6
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 = 9 e Y = 10.
	
	
	.X = 3 e Y = 14.
	
	
	.X = 14 e Y = 3.
	
	
	.X = 10 e Y = 9.
	
	
	.X = 1 e Y = 11.
1 pontos   
PERGUNTA 7
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.
	
	
	. 
	
	
	. 
	
	
	. 
	
	
	. 
	
	
	. 
1 pontos   
PERGUNTA 8
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}?
	
	
	.Pré-ordem.
	
	
	.Pós-ordem.
	
	
	.Ordem simétrica.
	
	
	.Busca sequencial.
	
	
	.Busca aleatória.
1 pontos   
PERGUNTA 9
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;”.
	
	
	.O método retornará somente false.
	
	
	.A árvore crescerá indefinidamente.
	
	
	.Será levantada uma exceção quando o programa for executado.
	
	
	.O programa não compilará.
	
	
	.A árvore será transformada em uma lista circular.
1 pontos   
PERGUNTA 10
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ídacom 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.
	
	
	.1, 2, 4, 5, 6, 8, 9.
	
	
	.4, 2, 1, 9, 8, 6, 5.
	
	
	.1, 4, 2, 6, 9, 8, 5.
1 pontos