Atividade 3 Estrutura de Dados

Prévia do material em texto

Atividade 3
Entrega 26 de nov de 2023 em 23:59 Pontos 1 Perguntas 5
Disponível 14 de ago de 2023 em 0:00 - 26 de nov de 2023 em 23:59
Limite de tempo Nenhum Tentativas permitidas 2
Instruções
Este teste não está mais disponível, pois o curso foi concluído.
Histórico de tentativas
Tentativa Tempo Pontuação
MANTIDO Tentativa 2 9 minutos 1 de 1
MAIS RECENTE Tentativa 2 9 minutos 1 de 1
Tentativa 1 17 minutos 0,4 de 1
Pontuação desta tentativa: 1 de 1
Enviado 22 de nov de 2023 em 18:47
Esta tentativa levou 9 minutos.
Importante:
Caso você esteja realizando a atividade através do aplicativo "Canvas Student", é necessário que
você clique em "FAZER O QUESTIONÁRIO", no final da página.
0,2 / 0,2 ptsPergunta 1
Leia o texto e analise a imagem a seguir:
Árvore B
Árvore B é uma estrutura de dados baseada em árvores de pesquisa
balanceadas, semelhante a árvore rubro-negra. Essa estrutura é usada
principalmente para minimizar o tempo em operações de E/S em
dispositivos de armazenamento secundário, como discos magnéticos.
A+
A
A-
https://famonline.instructure.com/courses/31357/quizzes/158699/history?version=2
https://famonline.instructure.com/courses/31357/quizzes/158699/history?version=2
https://famonline.instructure.com/courses/31357/quizzes/158699/history?version=1
Como o acesso a memória secundária é muito mais custoso em
relação ao acesso a memória principal, é necessário reduzir a
quantidade de acessos a memória secundária. Tipicamente, acessar a
memória secundária é seis vezes mais lento do que acessar a
memória primária (memória RAM). A árvore B consegue minimizar
esse problema armazenando nos seus nós uma quantidade de blocos
da memória secundária na memória principal e mantendo uma altura
de O(log n) onde n é o número de nós da árvore.
Unidade de disco
Uma unidade de disco é tipicamente composta por várias lâminas
chamadas de trilhas que giram em torno de um eixo. A gravação das
lâminas é feita pela extremidade de um braço que gira em torno de um
eixo pivô. O tempo de acesso a um disco não é constante, pois
depende da localização do braço em relação à trilha desejada.
A quantidade de dados que uma árvore B requisita da memória
secundária pode não caber na memória principal, assim o algoritmo
que busca as páginas do disco copia as páginas para a memória
principal conforme necessário. Se for feita uma referência a uma
página que não está na memória principal, uma busca será feita no
disco pela página requerida e esta será inserida na árvore. As páginas
que não estão em uso são retiradas da memória principal e gravadas
novamente em disco.
Fonte: MOURA, C. Árvore B: O que é e para que serve? Medium, 22
set. 2020. Disponível em:
A+
A
A-
https://medium.com/@ccmoura/%C3%A1rvore-b-o-que-%C3%A9-
e-para-que-serve-71c949484527
(https://medium.com/@ccmoura/%C3%A1rvore-b-o-que-%C3%A9-e-para-
que-serve-71c949484527) . Acesso em: 13 out. 2022.
Considerando as reflexões apresentadas, assinale a opção correta.
 
Uma árvore B permite armazenar grande número de chaves em um
único nó, mantendo a altura da árvore.
 
Nas outras árvores de busca auto balanceadas, supõe-se que alguns
elementos estejam na memória principal.
 
Os dispositivos de armazenamento secundário são mais rápidos e
possuem maior capacidade.
 
A necessidade de árvores B surgiu com o aumento da necessidade de
menos tempo para acessar a mídia de armazenamento.
Correto!Correto!
A alternativa está correta, pois a necessidade de árvores B surgiu 
com o aumento da necessidade de menos tempo para acessar a 
mídia de armazenamento físico, como podemos observar em um 
disco rígido.
 
Uma árvore B pode armazenar diversas chaves em vários nós e pode
ter vários nós filhos.
0,2 / 0,2 ptsPergunta 2
Observe a imagem e leia o texto a seguir:
A+
A
A-
https://medium.com/@ccmoura/%C3%A1rvore-b-o-que-%C3%A9-e-para-que-serve-71c949484527
https://medium.com/@ccmoura/%C3%A1rvore-b-o-que-%C3%A9-e-para-que-serve-71c949484527
https://medium.com/@ccmoura/%C3%A1rvore-b-o-que-%C3%A9-e-para-que-serve-71c949484527
https://medium.com/@ccmoura/%C3%A1rvore-b-o-que-%C3%A9-e-para-que-serve-71c949484527
https://medium.com/@ccmoura/%C3%A1rvore-b-o-que-%C3%A9-e-para-que-serve-71c949484527
https://medium.com/@ccmoura/%C3%A1rvore-b-o-que-%C3%A9-e-para-que-serve-71c949484527
Grafo de um autômato finito não determinístico generalizado (AFNG)
Os grafos estão presentes em muito do que diz respeito à ciência da
computação. Eles são uma abstração perfeitamente computável para
boa parte das relações da realidade e da imaginação humana.
Conceitualmente, um grafo é composto por um conjunto discreto de
elementos que representam a existência de algo material ou
imaginário. Estes elementos se relacionam; há uma regra, ou um
conjunto de regras, definindo estas relações pela lógica. Em outras
palavras, os elementos do conjunto discreto em questão são
interconectados por relações de um padrão de incidência bem definido,
e estas relações fazem parte do grafo — elas são expressas por
arestas, enquanto os elementos interconectados são expressos por
vértices.
Você pode inquirir por esclarecimento: a propósito, o que exatamente
significa isso? Qual é a aplicação prática disso tudo? Para que estas
dúvidas se façam sanadas, é conveniente que antes se conheça
alguns formalismos sobre os grafos. A concepção deste universo de
ideias com vértices e arestas é papel de uma teoria matemática
prenunciada por Leonhard Euler em 1736, em seu artigo sobre o
problema das 7 pontes de Königsberg. É a chamada teoria dos grafos.
Basicamente, a teoria dos grafos trata de relações entre elementos de
conjuntos discretos. Ela é amplamente empregada em algoritmos para
abstrair objetos do mundo real ou imaginário que são inter-
relacionados de alguma forma.
A+
A
A-
Fonte: CHAGAS, F. Grafos e algoritmos. Medium, 13 abr. 2020.
Disponível em: https://medium.com/programadores-ajudando-
programadores/os-grafos-e-os-algoritmos-697c1fd4a416
(https://medium.com/programadores-ajudando-programadores/os-grafos-
e-os-algoritmos-697c1fd4a416) . Acesso em: 27 set. 2022.
Considerando as informações, avalie as afirmações abaixo:
I. Os nós são um dos blocos de construção de uma estrutura de dados,
eles criam uma rede completa em qualquer grafo.
II. As arestas basicamente conectam os nós em uma estrutura de
dados de grafo.
III. Um caminho ou path em um grafo é um conjunto finito ou infinito de
arestas que une a um conjunto de vértices.
IV. Em uma estrutura de dados não linear, os elementos são
organizados linearmente ou sequencialmente.
É correto o que se afirma em:
 I, II e IV, apenas. 
 III e IV, apenas. 
 II e IV, apenas. 
 I, II e III, apenas. Correto!Correto!
A+
A
A-
https://medium.com/programadores-ajudando-programadores/os-grafos-e-os-algoritmos-697c1fd4a416
https://medium.com/programadores-ajudando-programadores/os-grafos-e-os-algoritmos-697c1fd4a416
https://medium.com/programadores-ajudando-programadores/os-grafos-e-os-algoritmos-697c1fd4a416
https://medium.com/programadores-ajudando-programadores/os-grafos-e-os-algoritmos-697c1fd4a416
https://medium.com/programadores-ajudando-programadores/os-grafos-e-os-algoritmos-697c1fd4a416
https://medium.com/programadores-ajudando-programadores/os-grafos-e-os-algoritmos-697c1fd4a416
A alternativa está correta, pois apenas as afirmações I, II e III
estão corretas.
A afirmação I está correta, pois os nós criam uma rede completa
em qualquer grafo. Eles são um dos blocos de construção de uma
estrutura de dados de grafo. Eles conectam as arestas e criam a
rede principal de um grafo. Eles também são chamados de
vértices.
A afirmação II está correta, pois as arestas basicamente conectam
os nós em uma estrutura de dados de grafo. Eles representam os
relacionamentos entre vários nós em um grafo. As arestas
também são chamadas de caminho em um grafo.
A afirmação III está correta, pois um caminho ou path em um grafo
é um conjunto finito ou infinito de arestas que une a um conjunto
de vértices. Ele pode se conectar a 2 ou mais nós.Além disso, se
o caminho conecta todos os nós de uma estrutura de dados de
grafo, então é um grafo conectado, caso contrário é chamado de
grafo desconectado.
A afirmação IV está incorreta, pois em uma estrutura de dados
não linear, os elementos não são organizados linearmente ou
sequencialmente. Como a estrutura de dados não linear não
envolve um único nível, um usuário não pode percorrer todos os
seus elementos de uma vez.
 I e III, apenas. 
0,2 / 0,2 ptsPergunta 3
Leia o texto e analise as imagens a seguir:
Grafo simétrico é um grafo orientado no qual, sempre que houver um
arco (i,j), haverá um arco (j,i). Trata-se da situação que discutimos em
2.1: um grafo simétrico equivale a um grafo não orientado.
Grafo completo é um grafo, orientado ou não, que possui ao menos
uma ligação entre cada par de vértices. Isso implicaria na existência de
ligações do tipo (i,i), associadas à diagonal principal da matriz de
adjacência, ou seja, os laços. Neste texto, como adiantamos não
iremos considerar laços, embora eles tenham significado em algumas
A+
A
A-
aplicações de gratos já citadas. Como já visto, um grafo completo é o
universo de referência para definição de grafo complementar.
O caso não orientado é mais importante, especialmente quando se
trata de um grafo completo que seja subgrafo induzido de outro grafo.
Neste caso, ele se chama uma clique do outro grafo. (Uma dique é
como uma panelinha, que já vimos também no exemplo do
sociograma). Veja os vértices brancos no exemplo abaixo. No caso não
orientado, para um 1-grafo, ao menos uma ligação quer dizer
exatamente uma.
Fonte: BOAVENTURA NETTO, Paulo Oswaldo; JURKIEWICZ, Samuel.
Grafos: Introdução e prática. São Paulo: Blucher, 2009. Adaptado.
Refletindo sobre grafos especiais, avalie as seguintes asserções e a
relação proposta entre elas.
I. Um grafo que tem vértices e arestas é um grafo nulo, pois cada
vértice está conectado a todos os outros vértices.
PORQUE
II. O grafo G é um grafo regular se todos os seus vértices têm o
mesmo grau. Um exemplo de gráfico regular é o Null Graph Nn.
A respeito dessas asserções, assinale a opção correta:
A+
A
A-
 
As asserções I e II são proposições verdadeiras, e a II é uma
justificativa da I.
 As asserções I e II são proposições falsas. 
 
A asserção I é uma proposição falsa, e a II é uma proposição
verdadeira.
Correto!Correto!
A alternativa está correta, pois a asserção I é uma proposição
falsa, e a II é uma proposição verdadeira.
A asserção I é falsa, pois um grafo que só tem vértices e não tem
arestas é um grafo nulo, é representado pelo símbolo Nn onde n é
o número de vértices. É em um grafo completo, que cada vértice
está ligado a todos os outros vértices, o que significa que em Kn
cada vértice está ligado a n-1 vértices, o que significa também que
existem n-1 arestas ligadas a cada vértice.
A asserção II é verdadeira, pois o grafo G é um grafo regular se
todos os seus vértices têm o mesmo grau. Por exemplo, se o grau
de um vértice em G é r, então o grafo G é dito regular de grau r,
um exemplo de grafo regular é o grafo Nulo Nn. Todos esses
grafos são regulares em grau zero.
 
As asserções I e II são proposições verdadeiras, mas a II não é uma
justificativa da I.
 
A asserção I é uma proposição verdadeira, e a II é uma proposição
falsa.
0,2 / 0,2 ptsPergunta 4
Leia o texto e analise a imagem a seguir:
A+
A
A-
As árvores são estruturas de dados baseadas em listas encadeadas
que possuem um nó superior também chamado de raiz que aponta
para outros nós, chamados de nós filhos, que podem ser pais de
outros nós.
Uma árvore de busca binária tem as seguintes propriedades:
todos os elementos na subárvore esquerda de um determinado nó
n são menores que n;
todos os elementos na subárvore direita de um determinado nó n
são maiores ou iguais a n.
Segue na Figura 1 uma ilustração de um exemplo de árvore binária.
No exemplo acima tem-se uma árvore binária onde a raiz é o elemento
8, o filho da esquerda do elemento 8 é o elemento 3, o filho da direita é
o elemento número 10. Nota-se que todos os elementos da árvore
binária possuem no máximo dois filhos, sendo o da esquerda sempre
menor e o da direita sempre maior que o elemento pai.
Fonte: DEVMEDIA. Trabalhando com árvores binárias em Java.
Disponível em: https://www.devmedia.com.br/trabalhando-com-
arvores-binarias-em-java/25749
(https://www.devmedia.com.br/trabalhando-com-arvores-binarias-em-
java/25749) . Acesso em: 27 set. 2022.
A+
A
A-
https://www.devmedia.com.br/trabalhando-com-arvores-binarias-em-java/25749
https://www.devmedia.com.br/trabalhando-com-arvores-binarias-em-java/25749
https://www.devmedia.com.br/trabalhando-com-arvores-binarias-em-java/25749
https://www.devmedia.com.br/trabalhando-com-arvores-binarias-em-java/25749
https://www.devmedia.com.br/trabalhando-com-arvores-binarias-em-java/25749
https://www.devmedia.com.br/trabalhando-com-arvores-binarias-em-java/25749
Considerando o conceito de árvore binária, qual é a alternativa que
relaciona os tipos e definições de árvores corretamente?
 
Uma árvore binária balanceada é uma árvore patológica/degenerada na
qual a árvore binária é dominada pelos nós esquerdos ou pelos nós
direitos.
 
Uma árvore binária degenerada/patológica é um tipo de árvore em que
cada nó interno tem exatamente dois nós filhos e todos os nós folha
estão no mesmo nível.
 
Uma árvore binária distorcida é um tipo de árvore binária na qual a
diferença entre a altura da subárvore esquerda e direita para cada nó é
0 ou 1.
 
Uma árvore binária perfeita é a árvore que tem um único filho à
esquerda ou à direita.
 
Uma árvore binária cheia, é um tipo especial de árvore binária na qual
cada nó pai/nó interno tem dois ou nenhum filho.
Correto!Correto!
A alternativa está correta, pois uma árvore binária cheia, ou Full 
Binary Tree, é um tipo especial de árvore binária na qual cada nó 
pai/nó interno tem dois ou nenhum filho. Também é conhecida 
como uma árvore binária adequada ou proper binary tree.
0,2 / 0,2 ptsPergunta 5
Leia o texto e analise a imagem a seguir:
A árvore AVL, criada em 1962 por Adelson-Velsky e Landis, é uma
árvore binária balanceada, ou seja, é uma árvore que obedece a todas
A+
A
A-
as propriedades da árvore binária e em que cada nó apresenta
diferença de altura entre as subárvores direita e esquerda de 1, 0 ou
-1, como ilustra a figura abaixo.
Se a diferença de altura entre as subárvores de um nó é maior que 1
ou menor que -1, a árvore está desbalanceada e haverá uma rotação.
Fonte: ASCENCIO, A. F. G.; ARAÚJO, G. S. Estrutura de Dados:
algoritmos, análise da complexidade e implementações em Java e
C/C++. São Paulo: Contentus, 2010.
Considerando as informações, analise as afirmações a seguir.
I. O fator de equilíbrio de um nó em uma árvore AVL é a diferença entre
a altura da subárvore esquerda e a da subárvore direita desse nó.
II. Um nó é sempre adicionado como um nó folha, pois depois de
excluir um nó, os fatores de equilíbrio dos nós são alterados.
III. Na rotação esquerda-direita, os arranjos são primeiramente
deslocados para a esquerda e depois para a direita.
É correto o que se afirma em:
A+
A
A-
 II e III, apenas. 
 I e III, apenas. Correto!Correto!
A alternativa está correta, pois apenas as afirmações I e III estão
corretas.
A afirmação I está correta, pois o fator de equilíbrio de um nó em
uma árvore AVL é a diferença entre a altura da subárvore
esquerda e a da subárvore direita desse nó. Fator de Equilíbrio é:
Altura da Subárvore Esquerda - Altura da Subárvore Direita ou
Altura da Subárvore Direita - Altura da Subárvore Esquerda.
A afirmação II está incorreta, pois um nó é sempre excluído como
um nó folha. Depois de excluir um nó, os fatores de equilíbrio dos
nós são alterados. Para reequilibrar o fator de equilíbrio, são
realizadas rotações adequadas.
A afirmação III está correta, pois na rotação esquerda-direita, os
arranjos são primeiro deslocados para a esquerda e depois para a
direita. Na rotação direita-esquerda, os arranjos são primeirodeslocados para a direita e depois para a esquerda.
 I e II, apenas. 
 I, apenas. 
 II, apenas. 
Pontuação do teste: 1 de 1
A+
A
A-