ESTRUTURA DE DADOS COM ORIENTAÇÃO A OBJETOS Atividade A4 2022 90 correta UAM

Prévia do material em texto

1. “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.
2. 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:
3. 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.
4. 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.
5. 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?
6. As árvores AVL 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. Em uma árvore AVL, o balanceamento é definido a partir das alturas das subárvores nela existentes.
 
Considerando essas informações e conteúdo estudado sobre árvores AVL, pode-se afirmar que:
7. 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.
8. 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.
 
9. 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 à:
10. 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: