Estrutura de Dados com Orientação a Objetos A4

Prévia do material em texto

Pergunta 1
1 em 1 pontos
	
	
	
	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 Selecionada:
	 
V, V, V, F.
	Resposta Correta:
	 
V, V, V, F.
	Comentário da resposta:
	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 2
1 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:
	 
A altura de uma árvore corresponde à altura do nó raiz.
	Resposta Correta:
	 
A altura de uma árvore corresponde à altura do nó raiz.
	Comentário da resposta:
	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 3
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 4
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 5
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 6
1 em 1 pontos
	
	
	
	“[...] 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écnicas de 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?
	
	
	
	
		Resposta Selecionada:
	 
Árvores AVL.
	Resposta Correta:
	 
Árvores AVL.
	Comentário da resposta:
	Sua resposta está correta. Árvores AVL são árvores de pesquisa binária, em que cada nó armazena valores para uma chave e para os ponteiros da subárvore esquerda e o ponteiro para a subárvore direita. No caso das árvores AVL, para encontrar a altura de uma subárvore, temos a implementação da função altura, em que usamos as mesmas declarações vistas para uma árvore binária.
	
	
	
 Pergunta 7
1 em 1 pontos
	
	
	
	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:
	
	
	
	
		Resposta Selecionada:
	 
como as árvores AVL são árvoresde equilíbrio de altura, operações como inserção e exclusão têm baixa complexidade de tempo.
	Resposta Correta:
	 
como as árvores AVL são árvores de equilíbrio de altura, operações como inserção e exclusão têm baixa complexidade de tempo.
	Comentário da resposta:
	Sua resposta está correta. As árvores AVL, por serem árvores balanceadas, primam pela eficiência nas operações de inclusão, exclusão e busca.
	
	
	
 Pergunta 8
0 em 1 pontos
	
	
	
	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 Selecionada:
	 
V, F, V, F.
	Resposta Correta:
	 
F, V, V, F.
	Comentário da resposta:
	Sua resposta está incorreta. As árvores binárias podem ser implementadas com estruturas de dados estáticas ou dinâmicas. Ao se utilizar uma estrutura estática do tipo array, os nós de cada nível são armazenados de forma contígua, ordenados da esquerda para a direita, utilizando-se vetores. Um vetor é uma estrutura de dados estática que armazena uma sequência de objetos, todos do mesmo tipo, em posições consecutivas da memória, permitindo acesso aleatório.
	
	
	
 Pergunta 9
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 10
1 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 B.
	Resposta Correta:
	 
Árvore B.
	Comentário da resposta:
	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.