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
MAIS RECENTE Tentativa 1 27.529 minutos 0,4 de 1
Pontuação desta tentativa: 0,4 de 1
Enviado 20 de nov de 2023 em 17:11
Esta tentativa levou 27.529 minutos.

Pergunta 1
0,2 / 0,2 pts
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.
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 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
A+
A
A-
10/06/2024, 14:58 Atividade 3: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158699?module_item_id=878101 1/10
https://famonline.instructure.com/courses/31357/quizzes/158699/history?version=1
 A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
 As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.
Correto!
 A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
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-
10/06/2024, 14:58 Atividade 3: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158699?module_item_id=878101 2/10
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 falsas.
 As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.

Pergunta 2
0,2 / 0,2 pts
Observe a imagem e leia o texto a seguir:
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.
A+
A
A-
10/06/2024, 14:58 Atividade 3: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158699?module_item_id=878101 3/10
 I e III, apenas.
Correto!
 I, II e III, apenas.
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
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.
 
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:
A+
A
A-
10/06/2024, 14:58 Atividade 3: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158699?module_item_id=878101 4/10
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
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, poisem 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, II e IV, apenas.
 II e IV, apenas.
 III e IV, apenas.

Pergunta 3
0 / 0,2 pts
Leia o texto e analise a imagem a seguir:
 
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.
A+
A
A-
10/06/2024, 14:58 Atividade 3: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158699?module_item_id=878101 5/10
Resposta correta
 
Uma árvore binária cheia, é um tipo especial de árvore binária na qual cada nó pai/nó interno tem dois ou nenhum
filho.
 
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 perfeita é a árvore que tem um único filho à esquerda ou à direita.
Você respondeu
 
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.
 
Considerando o conceito de árvore binária, qual é a alternativa que relaciona os tipos e definições de
árvores corretamente?
A+
A
A-
10/06/2024, 14:58 Atividade 3: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158699?module_item_id=878101 6/10
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
 
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.
A alternativa está incorreta, pois uma árvore binária balanceada ou Balanced Binary Tree é 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 distorcida que é uma árvore patológica/degenerada na qual a árvore é
dominada pelos nós esquerdos ou pelos nós direitos. Assim, existem dois tipos de árvore binária
assimétrica: árvore binária assimétrica à esquerda e árvore binária assimétrica à direita.
Desse modo, a alternativa correta é aquela que diz que 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.
 
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.

Pergunta 4
0 / 0,2 pts
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.
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
A+
A
A-
10/06/2024, 14:58 Atividade 3: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158699?module_item_id=878101 7/10
 Os dispositivos de armazenamento secundário são mais rápidos e possuem maior capacidade.
 Uma árvore B permite armazenar grande número de chaves em um único nó, mantendo a altura da árvore.
Resposta correta
 
A necessidade de árvores B surgiu com o aumento da necessidade de menos tempo para acessar a mídia de
armazenamento.
Você respondeu
 Uma árvore B pode armazenar diversas chaves em vários nós e pode ter vários nós filhos.
 
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:
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.
A+
A
A-
10/06/2024, 14:58 Atividade 3: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158699?module_item_id=878101 8/10
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
A alternativa está incorreta, pois uma árvore B pode armazenar muitas chaves em um único nó e
pode ter vários nós filhos. Isso diminui significativamente a altura, permitindo acessos mais rápidos
ao disco.
A resposta correta é “A necessidade de árvores B surgiu com o aumento da necessidade de menos
tempo para acessar a mídia de armazenamento”.
 Nas outras árvores de busca auto balanceadas, supõe-se que alguns elementos estejam na memória principal.

Pergunta 5
0 / 0,2 pts
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 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.
 
A+
A
A-
10/06/2024, 14:58 Atividade 3: Estrutura deDados
https://famonline.instructure.com/courses/31357/quizzes/158699?module_item_id=878101 9/10
 I e II, apenas.
Você respondeu
 I, apenas.
A alternativa está incorreta, 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 primeiro
deslocados para a direita e depois para a esquerda.
 II, apenas.
Resposta correta
 I e III, apenas.
 II e III, apenas.
Pontuação do teste: 0,4 de 1
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-
10/06/2024, 14:58 Atividade 3: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158699?module_item_id=878101 10/10