A4 ESTRUTURA DE DADOS

Prévia do material em texto

A4 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. 
 
 
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}? 
 
 
 
 
 
 
 
 
 
 
 
 
2) 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. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3) 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. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
4) 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. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
5) 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? 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
6)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. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
7)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. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
8) Uma operação muito comum nos sistemas computacionais é a operação de 
consulta ou busca. Ela, geralmente, recebe como parâmetro o elemento que se deseja 
procurar e um elemento de partida a partir do qual devemos buscar o elemento. 
Pensando nessa funcionalidade, consideremos a definição das classes “Produto” e 
“NoProduto” a seguir. 
 
 
Fonte: Elaborada pela autora, 2019. 
Foi implementado um método de busca por um elemento a partir do valor do atributo 
de “nome” do “Produto”. Os parâmetros recebidos são o nó visitado (“noProd”) e o nó 
com os dados procurados (“noProcurado”). Observe o próximo código. 
 
 
Fonte: Elaborada pela autora, 2019. 
A respeito desse código, assinale a alternativa verdadeira sobre o método “buscar()”, 
apresentado anteriormente. 
 
 
 
 
 
 
 
 
9)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? 
 
 
 
 
 
 
 
 
 
 
 
 
 
10)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.