Árvores Binárias de Busca

Prévia do material em texto

PERGUNTA 1
1. 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.
	
	
	.C/A*B.
	
	
	.A*C/B.
	
	
	.B/C*A.
	
	
	.C*B/A.
1 pontos  
PERGUNTA 2
1. 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 3
1. 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:
	
	
	.recebe esse nome porque os nós podem assumir os valores 0 ou 1.
	
	
	.um nó de uma árvore binária pode ter 0 ou 1 filho, no máximo.
	
	
	.um nó de uma árvore binária pode ter 0, 1 ou 2 filhos, no máximo.
	
	
	.ela tem um tamanho pré-determinado, chamado “altura”.
	
	
	.os nós têm, exatamente, 2 filhos cada, com exceção dos nós folhas.
1 pontos  
PERGUNTA 4
1. 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, V, F, F, V.
	
	
	.V, F, F, F, V.
	
	
	.V, F, V, F, V.
	
	
	.F, F, V, V, F.
	
	
	.F, V, F, V, F.
1 pontos  
PERGUNTA 5
1. Podemos dizer que uma árvore é binária quando cada um dos seus nós tem 0, 1 ou 2 filhos. Com esta característica, é possível definir uma estrutura de dados em que, além das informações armazenadas, tenhamos acesso ao filho da esquerda e da direita.
A figura a seguir representa um nó “Produto”, com a referência para os outros filhos desse “Produto”: “filhoEsquerda” e “filhoDireita”.
Fonte: Elaborada pela autora, 2019.
Temos, ainda, que um tipo especial de árvore binária é chamado de AVL. Assinale a alternativa a seguir que contém a principal característica desse tipo de árvore.
	
	
	.A árvore AVL tem apenas altura 2.
	
	
	.A árvore AVL tem apenas nós folhas.
	
	
	.A árvore AVL tem apenas o nó raiz.
	
	
	.A árvore AVL pode ter mais de 2 filhos.
	
	
	.A árvore AVL é balanceada.
1 pontos  
PERGUNTA 6
1. 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 7
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.
Abaixo 5 itens listados com letras romanas. Cada item contém o desenho de uma árvore binária em que os nós são representados por círculos e as conexões são representadas por setas. Dentro de cada círculo tem uma letra maiúscula representando o valor armazenado naquele nó. Enumerando cada item temos:
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 8
1. 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 9
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.
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 pontosPERGUNTA 10
1. 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?
	
	
	.D, B, A, C, F, E, G.
	
	
	.A, B, C, D, E, F, G.
	
	
	.A, C, B, E, F, G, D.
	
	
	.D, F, G, E, B, C, A.
	
	
	.B, A, C, D, F, E, G.