EDCOO-ATV4

Prévia do material em texto

• Pergunta 1 
0 em 1 pontos 
 
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? 
 
Resposta Selecionada: 
Árvore binária. 
Resposta Correta: 
Árvore B. 
Comentário 
da resposta: 
Sua resposta está incorreta. Para entender o uso deste tipo 
de árvores, devemos pensar em uma grande quantidade de 
dados que não cabem na memória principal. Quando o 
número de chaves é alto, os dados são lidos do disco na 
forma de blocos. O tempo de acesso ao disco é muito alto em 
comparação com o tempo de acesso à memória principal. A 
ideia principal de usar este tipo de árvore é reduzir o número 
de acessos ao disco. 
 
 
• Pergunta 2 
1 em 1 pontos 
 
“As operações básicas em uma árvore binária (de busca) têm tempo 
proporcional à sua altura. Como a altura da árvore dependerá da quantidade 
N de chaves e de sua ordem de inserção na árvore, o tempo de resposta das 
operações básicas dependerá da quantidade e da distribuição das chaves 
pelas subárvores (subárvores com diferentes alturas)”. 
Fonte: BIANCHI, F.; FREITAS, R.; JUNIOR, D. Estrutura de dados e técnicas de 
programação. Rio de Janeiro: Elsevier, 2014, p.273. 
 
 
Considerando essas informações e o conteúdo estudado sobre a eficiência 
na busca em árvore binária, analise as afirmativas a seguir e assinale V para 
a(s) verdadeira(s) e F para a(s) falsa(s). 
 
I. Uma árvore balanceada tem para cada nó da árvore as alturas das 
subárvores esquerda e direita, diferindo, no máximo, em uma unidade. 
II. Se uma árvore possuir essa propriedade, sua altura será minimizada e, 
assim, as buscas serão mais rápidas. 
III. No pior caso, teríamos as inserções das chaves de modo que a altura da 
árvore fosse N-1, ou seja, um tempo de execução das operações básicas 
O(N). 
IV. As árvores binárias, por definição, são balanceadas, pois implementam, 
naturalmente, o fator de equilíbrio. 
 
Agora, assinale a alternativa que apresenta a sequência correta. 
Resposta Selecionada: 
V, V, V, F. 
Resposta Correta: 
V, V, V, F. 
Comentário 
da resposta: 
Sua resposta está correta. As árvores de busca binária são 
estruturas hierárquicas que guardam os dados de forma 
ordenada, e caso a árvore esteja balanceada, a quantidade 
de comparações até localizar o valor procurado é limitada 
superiormente pela altura da árvore. 
 
 
• Pergunta 3 
1 em 1 pontos 
 
Á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. 
Resposta Selecionada: 
I, III e IV. 
Resposta Correta: 
I, III e IV. 
Comentário 
da resposta: 
Sua resposta está correta. As árvores B são árvores N-ária 
balanceadas e estão sujeitas às mesmas definições e 
conceitos das árvores N-árias, de modo que não estão 
restritas a ter nós-filhos com o máximo de grau 2. Devem 
atender a determinadas condições, para garantir seu 
balanceamento, como ter todos os nós folhas no mesmo nível 
da árvore, ter limites inferiores e superiores para os números 
de chaves em cada nó, entre outros. 
 
 
• Pergunta 4 
1 em 1 pontos 
 
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. 
Resposta 
Selecionada: 
 
A figura a representa uma árvore binária quase completa e a 
figura b uma árvore binária quase não completa. 
Resposta 
Correta: 
 
A figura a representa uma árvore binária quase completa e a 
figura b uma árvore binária quase não completa. 
Comentário 
da resposta: 
Sua resposta está correta. A árvore a é uma árvore quase 
completa, mas a árvore b não é uma árvore binária quase 
completa, porque, para todo nó Bn que possuir um descendente 
direito no nível N (nível máximo da árvore), todo descendente 
esquerdo de Bn deverá ser nó folha no nível N. 
 
 
• Pergunta 5 
1 em 1 pontos 
 
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. 
 
Resposta Selecionada: 
V, V, V, F. 
Resposta Correta: 
V, V, V, F. 
Comentário 
da resposta: 
Sua resposta está correta. As árvores B são utilizadas em 
aplicações em que a quantidade de dados é muito grande 
para que as chaves possam ser armazenadas somente em 
memória, sendo necessário o uso de memória secundária. 
Esse tipo de estrutura de dados tem no máximo dois filhos e 
todas as folhas estão no mesmo nível. 
 
 
• Pergunta 6 
1 em 1 pontos 
 
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. 
Resposta Selecionada: 
F, V, V, V. 
Resposta Correta: 
F, V, V, V. 
Comentário 
da resposta: 
Sua resposta está correta. As árvores n-árias são compostas 
por uma série de características, como ter uma estrutura 
vazia e os elementos dentro de um nó estarem sempre 
ordenados por meio de suas respectivas chaves. 
 
 
• Pergunta 7 
0 em 1 pontos 
 
Bianchi et al (2014) afirma que “a manipulação de uma árvore B é possível 
por meio de diferentes operações. [...] A árvore B é uma árvore N-ária com a 
restrição de ser balanceada”. Dessa forma, as operações de percurso e de 
busca por determinado elemento (chave) são idênticas às das á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.328. 
 
Considerando essas informações e conteúdo estudado sobre a operação 
de inclusão em Árvore B, pode-se afirmar que são etapas para a inclusão de 
elementos: 
 
I. As chaves são inseridas nos nós folha. 
 
II. No caso de precisar verificar o valor do nó raiz e se este valor for nulo, 
deve-se alocar um nó na raiz; se o valor do nó raiz for maior que o elemento 
buscado, incluir à esquerda, se não, incluir à direita. 
III. Se o nó ficar cheio, divida a folha em duas partes e suba a chave central 
para o nó pai. 
III. Se o nó pai ficar cheio, repita o processo. No pior caso, repita até a raiz. 
IV. Se necessário, o nó raiz deverá ser divido e a chave central será 
transformada em nova raiz. 
Está correto apenas o que se afirma em: 
Resposta Selecionada: 
I, II e IV. 
Resposta Correta: 
I, III e IV. 
Comentário 
da resposta: 
Sua resposta está incorreta. Dependendo do tipo de 
operação realizada com as árvores binárias de busca, existe 
a necessidade de comparação dos elementos com os nós 
existentes. Por ser ordenada, dependendo da condição, os 
valores são adicionados à subárvore esquerda ou direita, 
sendo executada quando os dados são carregados na RAM, 
ao contrário da árvore B, que é executada quando os dados 
são carregados no disco. 
 
 
 
• Pergunta 8 
0 em 1 pontos 
 
Trata-se de uma árvore binária armazenando chaves (ou itens) em seus nós 
internos, o que satisfaz a seguinte propriedade: seja u, v e w três nós, em que 
u é nó esquerdo de v e w é seu nó direito. Temos key(u) <= key(v)<= key(w), 
ou seja, neste tipo de estrutura baseada em nós, todos os nós da subárvore 
esquerda possuem um valor numérico inferior ao nó raiz e todos os nós da 
subárvore direita possuem um valor superior ao nó raiz. 
 
Considerando essas informações e conteúdo estudado, pode-se afirmar que 
o tipo de árvore que atende a esta definição é: 
 
Resposta Selecionada: 
Árvore B. 
Resposta Correta: 
Árvore de pesquisa binária. 
 
Comentário 
da resposta: 
Sua resposta está incorreta. Árvores são estruturas em que 
os dados são dispostos de forma hierárquica. Nelas, os 
dados são armazenados em nós. Existe um nó principal, 
conhecido como raiz, a partir do qual surgem as ramificações, 
conhecidas como subárvores. Existem tipos específicos de 
árvores que são utilizados quando se precisa armazenar 
dados contra os quais outros dados são frequentemente 
verificados, sendo uma estrutura dinâmica e que pode sofrer 
alterações (inserções e remoções de nós) após ter sido 
criada. 
 
• Pergunta 9 
1 em 1 pontos 
 
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 à: 
 
Resposta Selecionada: 
Árvore de pesquisa binária. 
Resposta Correta: 
Árvore de pesquisa binária. 
Comentário 
da resposta: 
Sua resposta está correta. Árvores de pesquisa binária são 
um tipo de árvore binária, cujos elementos não se repetem e 
são dispostos de forma ordenada, de forma que todos nós da 
subárvore à esquerda contêm valores menores que o valor 
do nó raiz, e a subárvore da direita contém apenas valores 
maiores. 
 
 
• Pergunta 10 
0 em 1 pontos 
 
Uma árvore é uma estrutura de dados bidimensional, não linear, que possui 
propriedades especiais e admite muitas operações de conjuntos dinâmicos, 
como consulta, inserção, remoção, entre outros, sendo diferente de listas e 
pilhas, pois a árvore é uma estrutura de dados hierárquica e não linear, 
definida recursivamente. O nó raiz é o principal elemento da árvore. 
 
 
Considerando essas informações e conteúdo estudado sobre conceitos das 
árvores, assinale a alternativa correta em relação ao nó raiz. 
 
Resposta 
Selecionada: 
 
Os nós de uma árvore são descendentes indiretos do 
nó raiz. 
Resposta Correta: 
A altura de uma árvore corresponde à altura do nó raiz. 
Comentário 
da resposta: 
Sua resposta está incorreta. Árvores são estruturas em que 
os dados são armazenados em nós. Nelas, o nó raiz é o 
primeiro nó ou nó-pai, tendo um ou mais campos com links 
para outros nós. É o nó mais alto da estrutura da 
árvore. Cada nó pode ter um número arbitrário de filhos. Os 
nós sem filhos são chamados de folhas ou nós externos. Os 
nós, que não são folhas, são chamados de nós internos. Os 
nós internos têm pelo menos um filho. 
 
 
Quinta-feira, 27 de Maio de 2021 14h55min28s BRT