Atividade 04 - 10 de 10

Prévia do material em texto

Em computação, a árvore é um modelo abstrato de uma estrutura hierárquica, que 
consiste em nós com uma relação pai-filho. É semelhante a uma lista encadeada, mas 
em vez de cada nó simplesmente apontar para o próximo nó de forma linear, cada nó 
aponta para um número de nós. Neste tipo de estrutura, a ordem dos elementos não é 
importante. 
 
Considerando essas informações e o conteúdo estudado sobre árvores B, analise as 
afirmativas a seguir e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s). 
 
I. É um tipo de árvore binária que tem aplicação em expressões aritméticas e em 
árvores de decisão. 
II. Cada nó interno tem no máximo dois filhos, e os filhos de um nó formam um par 
ordenado. 
III. É um tipo de árvore binária caracterizada como um conjunto finito vazio (ou não) de 
nós. 
IV. A árvore B cresce e diminui de elementos para baixo, a partir de suas folhas, 
diferente das árvores de busca binária que crescem e diminuem a partir da raiz. 
 
Agora, assinale a alternativa que apresenta a sequência correta. 
 
 
 
Trata-se de uma árvore binária especial (sem valores de nó duplicados) e que tem a 
característica de que os valores em qualquer subárvore esquerda são menores que o 
valor no nó-pai dessa subárvore, e os valores em qualquer subárvore direita são 
maiores que o valor no nó pai dessa subárvore. 
 
Considerando essas informações e conteúdo estudado sobre árvores binárias, o 
elemento-base se refere à: 
 
 
 
Dependendo da distribuição dos seus nós, uma árvore binária pode ser classificada em: 
árvore estritamente binária, árvore binária completa e árvore binária quase completa. A 
seguir são apresentadas árvores binárias: 
 
 
Fonte: BIANCHI, F.; FREITAS, R.; JUNIOR, D. Estrutura de dados e técnicas de 
programação. Rio de Janeiro: Elsevier, 2014, p.261 
 
Considerando essas informações e o conteúdo estudado sobre a classificação das 
árvores binárias existentes, assinale a alternativa que identifica corretamente o tipo de 
arvore binária apresentada. 
 
 
 
Criadas por Bayes e McCreight em 1972, as árvores binárias são utilizadas em algumas 
aplicações em que a quantidade de dados é muito grande para que as chaves possam ser 
armazenadas somente em memória, obrigando a utilização de memória secundária, o 
que aumenta o tempo de acesso a um só nó de dados. Tais árvores podem ser 
implementadas de forma estática e dinâmica. 
 
Em relação à implementação de árvores binárias, analise as afirmativas a seguir e 
assinale V para a(s) verdadeira(s) e F para a(s) falsa(s). 
 
I. A implementação sequencial usa uma estrutura estática tipo array. 
II. Na implementação estática, os nós de cada nível são armazenados de forma contígua. 
III. A implementação encadeada de árvore binária usa uma estrutura dinâmica com 
vetores. 
IV. A implementação dinâmica usa uma estrutura dinâmica com apontadores. 
 
Agora, assinale a alternativa que apresenta a sequência correta. 
 
 
 
A árvore binária é uma estrutura de dados em que cada nó pode ter no máximo 2 
filhos. O nó presente no nível mais alto é chamado de nó raiz e um nó com 0 filhos é 
chamado de nó folha. Existem várias aplicações para as árvores binárias. 
 
 
Fonte: BIANCHI, Francisco; FREITAS, Ricardo; JUNIOR, Dilermando. Estrutura de 
dados e técnicas de programação. Rio de Janeiro: Elsevier, 2014.p.260. 
 
Considerando essas informações e conteúdo estudado sobre a estrutura de árvore 
binária, analise as afirmativas a seguir. 
 
I. Sua representação gráfica está correta. 
II. O grau da árvore apresentada é 3. 
III. A altura do nó B1 é 3. 
IV. A altura da árvore é 4. 
 
Está correto o que se afirma em: 
 
 
 
Este tipo de árvore é utilizado quando se tem necessidade de manipular uma quantidade 
maior de dados, principalmente aqueles que se encontram em armazenamento 
secundário. Neste tipo de estrutura, todas as folhas estão no mesmo nível e todas as 
chaves de um nó são classificadas em ordem crescente.Esse tipo de árvore cresce e 
diminui a partir da raiz, característica que a diferencia da árvore de pesquisa binária, que 
cresce e diminui para baixo. Além disso, a raiz pode conter no mínimo 1 chave e todos 
os nós (incluindo a raiz) podem conter no máximo t - 1 chaves. 
 
Considerando essas informações e conteúdo estudado sobre árvores balanceadas, 
responda: de qual estrutura de dados estamos falando? 
 
 
 
A árvore de pesquisa binária é uma árvore binária ordenada. Todos os elementos na 
subárvore esquerda são menores que a raiz, enquanto os elementos presentes na 
subárvore direita são maiores ou iguais ao elemento do nó raiz. 
 
Considerando essas informações e conteúdo estudado sobre as vantagens de se 
utilizar árvores de pesquisa binárias, analise as afirmativas a seguir e assinale V para 
a(s) verdadeira(s) e F para a(s) falsa(s). 
 
I. A pesquisa é mais eficiente, uma vez que se obtém, em cada etapa, uma dica sobre 
qual subárvore contém o elemento desejado. 
II. No processo de pesquisa, ela remove metade da subárvore em cada etapa, se 
comparada a arrays e listas encadeadas. 
III. Acelera as operações de inserção e exclusão em comparação com o array e a lista 
encadeada. 
IV. Como faz o balanceamento automático de seus elementos, consegue ser mais 
rápida que as demais árvores binárias. 
 
Agora, assinale a alternativa que apresenta a sequência correta. 
 
 
 
Árvores B são árvores de pesquisa, ordenada, balanceadas e projetadas para 
funcionar bem em discos magnéticos ou outros dispositivos de armazenamento 
secundário. É indicada para quando se precisa armazenar um número muito grande 
de dados e não se pode fazê-lo na memória primária. 
Existem algumas propriedades específicas para que uma árvore seja considerada uma 
árvore B. 
Assim, considerando essas informações e o conteúdo estudado, analise as afirmativas 
a seguir: 
 
I. Neste tipo de estrutura, assegura-se que todas as folhas estejam no mesmo nível. 
II. Seus nós têm uma chave e sua raiz deve ter dois filhos não vazios. 
III. Quando os dados são grandes demais para caber na memória, o número de 
acessos a disco se torna importante. 
IV. A altura da árvore deve ser o mais baixo possível para aumentar a performance da 
busca. 
 
Agora, assinale a alternativa que apresenta a sequência correta. 
 
 
 
Bianchi et al (2014) afirmam que “[...] assim como ocorre com as árvores AVL em 
relação às árvores binárias, as árvores B (que são árvores N-ária balanceadas) estão 
sujeitas às mesmas definições e conceitos vistos para as árvores N-árias”. 
Fonte: BIANCHI, F.; FREITAS, R.; JUNIOR, D. Estrutura de dados e técnicas de 
programação. Rio de Janeiro: Elsevier, 2014, p.324 
 
Considerando essas informações e conteúdo estudado sobre Árvores N-árias, analise as 
afirmativas a seguir e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s). 
 
I. A diferença de alturas das subárvores esquerda e direita de qualquer nó é menor ou 
igual a um. 
II. A relação entre o número de nós-filhos que uma árvore suporta é o número de chaves 
dentro do nó. 
III. A diferença se refere à distribuição dos elementos pela árvore, que é feita 
respeitando determinadas condições que garantem seu balanceamento. 
IV. Os elementos dentro de um nó estão sempre ordenados por meio de suas respectivas 
chaves. 
 
Agora, assinale a alternativa que apresenta a sequência correta. 
 
 
 
“[...] são árvores binárias em que a distribuição dos elementos é feita respeitando 
determinadas condições, que vão garantir o balanceamento dessa árvore. [...] O 
balanceamento é definido a partir das alturas das subárvores nela existentes. Nesse 
tipo de árvore, a diferença entre as alturas das subárvores esquerda e direita de 
qualquer nó é de no máximo 1, ou seja, se a altura da subárvore esquerda é N, então, 
a altura da subárvore direita será igual a N, N-1 ou N+1.” Trata-se de uma árvore 
binária de busca balanceada. 
Fonte: BIANCHI, F.; FREITAS, R.; JUNIOR, D. Estrutura de dados e técnicasde 
programação. Rio de Janeiro: Elsevier, 2014.p.317 
 
Considerando essas informações e conteúdo estudado sobre árvores binárias 
balanceadas, responda: a que tipo de estrutura específica o texto se refere?