Atividade A3 ESTRUTURA DE DADOS COM ORIENTAÇÃO A OBJETOS

Prévia do material em texto

Se foi útil para você deixe um joinha 
Pergunta 1)
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:
A altura de uma árvore corresponde à altura do nó raiz.
Sua resposta está correta. Um nó raiz, por não ter ancestrais, tem seu nível sempre igual a zero e é responsável por definir a altura de uma árvore. Todos os nós que são inseridos depois dele são seus descendentes diretos ou indiretos.
Pergunta 2)
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.
Resposta:
F, V, V, F.
Sua resposta está correta. Uma árvore binária pode ser implementada com alocação estática com utilização de vetores ou com alocação dinâmica, com a utilização de listas encadeadas.
Pergunta 3)
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:
Árvore de pesquisa binária.
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 4)
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:
Capturar_20211112090134.JPG
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:
A figura a representa uma árvore binária quase completa e a figura b uma árvore binária quase não completa.
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)
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.
Resposta:
V, V, V, F.
Sua resposta está correta. As árvores de pesquisa binária se diferenciam das árvores binárias, por serem ordenadas. Diferente das árvores AVL onde a distribuição dos elementos é feita respeitando determinadas condições que garantem o balanceamento, esse tipo de árvore não é balanceado.
Pergunta 6)
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:
Árvore B.
Sua resposta está correta. As árvores B favorecem o armazenamento de maior volume de dados, sem um impacto significativo no número de acessos aos nós, quando se deseja localizar algum elemento (chave). Isso decorre do fato de o armazenamento de vários elementos ser feito em um mesmo nó, e também por ser balanceado de modo que todos os nós folha estejam em um mesmo nível.
Pergunta 7)
“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:
V, V, V, F.
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 8)
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:
F, V, V, V.
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 9)
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:
Árvore de pesquisa binária.
Sua resposta está correta. Uma árvore de pesquisa binária é uma estrutura de dados que nos permite manter rapidamente uma lista ordenada de números. É chamada de árvore binária porque cada nó da árvore tem no máximo dois filhos, sendo que 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.
Pergunta 10)
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.
a_20211112090134.JPG
 
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:
Resposta:
I, III e IV.
Sua resposta está correta. A figura representa corretamente uma árvore binária, pois os nós estão restritos a dois filhos no máximo. O grau da árvore é dado pelo nó que tem mais filhos, portanto, o grau da árvore é 4. A altura de um nó Bi é igual à maior distância entre Bi e um nó folha que seja seu descendente; e a altura de uma árvore corresponde à altura do nó raiz.