A4 EDOO ESTRUTURA DE DADOS COM ORIENTAÇÃO A OBJETOS

Prévia do material em texto

 Pergunta 1 
1 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: 
F, V, 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 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 
 
 
“[...] 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 4 
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 5 
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 6 
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. 
 
 
 Pergunta 7 
1em 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 8 
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 9 
1 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, III e IV. 
Resposta Correta: 
I, III e IV. 
Comentário 
da resposta: 
Sua resposta está correta. Para inserir um novo elemento em 
uma árvore B, basta localizar o nó folha X, onde o novo 
elemento deve ser inserido. Se o nó X estiver cheio, será 
necessário realizar uma subdivisão de nós, que consiste em 
passar o elemento mediano de X para seu pai e subdividir X em 
dois novos nós com t-1 elementos e depois inserir a nova chave. 
 
 
 
 Pergunta 10 
1 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 de pesquisa binária. 
 
Resposta Correta: 
Árvore de pesquisa binária. 
 
Comentário 
da resposta: 
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.