Estrutura de Dados: Árvores Binárias de Busca

Prévia do material em texto

Curso ESTRUTURA DE DADOS 
Teste ATIVIDADE 4 (A4) 
• Pergunta 1 
1 em 1 pontos 
 
Imagine que você foi contratado para implementar um aplicativo que testa os conhecimentos 
da disciplina de Estrutura de Dados no ENEM. Para isso, você modelou uma classe 
“ EstruturaDadosEnem”, que contém os seguintes atributos: uma string contendo o texto da 
pergunta, um inteiro correspondente à área do conhecimento e um vetor de cinco strings para 
armazenar as opções de resposta e dicas de estudo. Como o objetivo é, ao final, indicar para 
os alunos quais as áreas de estudo que ele tem que se dedicar mais, você decidiu que a 
estrutura de dados mais propícia seria uma árvore. 
Considerando essas informações, assinale a alternativa a seguir que contém a implementação 
de uma classe “EstruturaDadosEnem”, conforme descrito, para ser inserida em uma árvore. 
 
Resposta Selecionada: 
. 
Resposta Correta: 
. 
Feedback 
da resposta: 
Isso mesmo, sua resposta está correta! A definição de um nó de uma árvore é 
realizada pela criação de uma classe denominada “EstruturaDadosEnem”. No 
contexto apresentado, no escopo desta classe, devem ser declarados como 
atributos os dados que armazenam informações sobre ela: pergunta, área e 
opções de resposta. O atributo pergunta deve ser declarado como do tipo string, a 
área deve ser um inteiro (definido pelo tipo primitivo int) e precisa haver um vetor 
do tipo string que corresponde às opções de resposta ( String []). 
 
 
• Pergunta 2 
0 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: 
Infelizmente sua resposta está errada. Inserir um nó filho depende da criação do 
objeto e posterior inserção da referência ao nó filho e ao nó pai. Lembre-se de que 
você está criando a subárvore apresentado no esquema gráfico. Reveja o 
conteúdo e tente responder à questão novamente! 
 
• Pergunta 3 
1 em 1 pontos 
 
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. 
 
Resposta Selecionada: 
.X = 3 e Y = 14. 
Resposta Correta: 
.X = 3 e Y = 14. 
Feedback da 
resposta: 
Isso mesmo, resposta correta! Como o nó X está à esquerda do nó 6, é 
necessário que X seja menor que 6, então, o valor 3 atende. De forma similar, já 
que Y está à direita de 12, seu valor deve ser maior que isso. Assim, o valor de Y 
igual a 14 é válido. 
 
 
• Pergunta 4 
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 5 
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 6 
1 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: 
Isso mesmo, resposta correta! Como a posição correta do elemento corresponde 
à posição do nó atual, é preciso confirmar se a posição está vazia, ou seja, se não 
tem outro nó a ocupando, para que o elemento seja inserido. 
 
 
• Pergunta 7 
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 8 
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 9 
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 10 
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.