Atividade 4 Arvores

Prévia do material em texto

…Pergunta 1
Resposta
Selecionada:
Resposta Correta:
Feedback
da resposta:
Durante o desenvolvimento de um sistema computacional, a equipe de desenvolvimento constatou a
necessidade de criar uma estrutura capaz de recuperar com facilidade o cadastro de itens de um estoque.
Inicialmente, a estrutura continha apenas cinco registros, que com o tempo seria expandida para mais
itens. Os itens continham um código, identificado dentro dos parênteses, e uma descrição; são eles: (12)
sapatos, (6) camisetas, (4) shorts, (7) calças e (2) meias.
Para realização de testes, cada item foi inserido, respeitando a ordem apresentada, em duas árvores
binárias de busca diferentes. Na primeira árvore, a chave utilizada para a busca seria o código de cada
item, em que os itens cujo código era menor ou igual ao da raiz eram alocados na subárvore esquerda e,
os maiores, na direita. Já para a segunda árvore, a chave da busca seria apenas a descrição de cada item
(os itens cuja descrição, em ordem alfabética, fosse antes da raiz eram alocados na subárvore esquerda).
Considerando as árvores de busca binária resultantes no processo, assinale a alternativa correta.
A primeira árvore é considerada binária, enquanto a segunda é uma árvore quase
completa de altura 2.
A primeira árvore é considerada binária, enquanto a segunda é uma árvore quase
completa de altura 2.
Resposta correta. A alternativa está correta. Ao final da inserção dos itens nas duas
estruturas, a primeira árvore resultante possui profundidade 3 e é binária, enquanto a
segunda estrutura possui profundidade 2 e pode ser considerada uma árvore balanceada.
A segunda estrutura acaba sendo mais eficiente para a operação de busca, devido à
disposição de seus elementos.
Pergunta 2
Leia o excerto a seguir:
“Um exemplo de uma situação da vida real que pode ser modelada por um gráfico é o sistema
aeroportuário. Cada aeroporto é um vértice. Se houver um voo sem escalas entre dois aeroportos, dois
vértices serão conectados por uma aresta. A aresta pode ter um peso que representa o tempo, a distância
ou o custo do voo."
WEISS, M. A. Data Structures & Problem Solving Using Java. 4 ed. London: Pearson Education. 2010,
p. 529.
Diante do contexto apresentado, foi formado o seguinte grafo, em que cada vértice é um aeroporto e as
arestas a conexão (ou voos disponíveis) entre eles.
1 em 1 pontos
1 em 1 pontos
Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0945 ... https://unifacs.blackboard.com/webapps/assessment/review/review.jsp?a...
1 of 9 10/04/2020 18:19
Resposta Selecionada:
Resposta Correta:
Feedback
da
resposta:
Fonte: Elaborada pelo autor.
Sobre o grafo apresentado, analise as afirmativas a seguir e assinale V para a(s) verdadeira(s) e F para
a(s) falsa(s).
I. ( ) A quantidade mínima de escalas para pegar um voo entre A e E é 1.
II. ( ) A quantidade mínima de escalas para pegar um voo entre E e D é 0.
III. ( ) No grafo, o nó que representa o aeroporto D possui grau de entrada 3.
IV. ( ) A classificação para esse tipo de estrutura é um grafo misto.
Assinale a alternativa que apresenta a sequência correta:
V, F, F, V.
V, F, F, V.
Resposta correta. A alternativa está correta, já que apresenta sequência adequada. O grafo
em questão é considerado um grafo misto, uma vez que possui tanto conexões não
direcionadas quanto direcionadas. Assim, é necessário verificar se existe o trajeto para os
aeroportos. No caso de uma conexão direta do Aeroporto A para o Aeroporto E, é
necessário realizar uma escala no aeroporto C. Dessa forma, o caminho mínimo conteria
uma escala para esse trajeto.
Pergunta 3
Após debater com os alunos as características de árvores, árvores binárias e árvores binárias de busca, um
professor apresentou duas árvores para que os alunos identificassem algumas características. As árvores
estão representadas nas figuras a seguir. Em seguida, o professor fez algumas afirmativas sobre as
árvores, e pediu para os alunos identificassem alguns erros que disse de forma proposital.
1 em 1 pontos
Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0945 ... https://unifacs.blackboard.com/webapps/assessment/review/review.jsp?a...
2 of 9 10/04/2020 18:19
Resposta Selecionada:
Resposta Correta:
Feedback
da
resposta:
Fonte: Elaboradas pelo autor.
Considerando o contexto apresentado, analise as afirmativas a seguir, dadas pelo professor:
I. A árvore I pode ser classificada como uma árvore estritamente binária ou uma árvore quase completa de
altura 3.
II. A árvore I é uma árvore binária cuja disposição dos elementos é semelhante à de uma lista linear.
III. A profundidade da árvore II é de 2, uma vez que o maior nível de um nó folha encontrado na árvore é 2.
IV. Se excluirmos um nó folha da árvore II, ela será do tipo quase completa de altura 1.
Está correto o que se afirma em:
II e III, apenas.
II e III, apenas.
Resposta correta. A alternativa está correta, pois a disposição da árvore I é semelhante à
de uma lista linear. Se considerarmos que a árvore tem o propósito de busca, para
aumentar a eficiência seria interessante realizar um processo de balanceamento. Além
disso, a árvore II é uma árvore completa de altura 2, pois todos os nós intermediários
possuem tanto as subárvores da esquerda quanto da direita, e todos os nós folhas possuem
nível 2.
Pergunta 4
Um professor pediu um trabalho para seus alunos, no qual eles precisariam organizar itens de um
inventário que seria utilizado em um jogo de aventura. Cada item possuía uma chave cujo valor é numérico,
e era possível descobrir qual o tipo de item (armas, escudos, poções, armaduras etc.) verificando apenas o
valor da chave. Dessa forma, o professor sugeriu aos alunos que criassem uma árvore binária com objetivo
de organizar os itens e, depois, tentassem descobrir qual o tipo de árvore resultante desse processo.
Um dos alunos, após a inserção, obteve a seguinte árvore:
1 em 1 pontos
Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0945 ... https://unifacs.blackboard.com/webapps/assessment/review/review.jsp?a...
3 of 9 10/04/2020 18:19
Resposta Selecionada:
Resposta Correta:
Feedback
da resposta:
Fonte: Elaborada pelo autor.
Assinale a alternativa que corresponda ao tipo de árvore obtida pelo aluno:
Árvore estritamente binária.
Árvore estritamente binária.
Resposta correta. A alternativa está correta. A árvore apresentada é estritamente binária,
pois, apesar de todos os nós possuírem as árvores direita e esquerda, elas estão em níveis
diferentes (no caso do elemento “12”, no nível d-2). Isso justifica também que essa árvore
não pode ser do tipo árvores quase completa de altura d, sendo o tipo árvore estritamente
binária a única opção correta possível.
Pergunta 5
As redes sociais são muito populares nos dias de hoje. Elas alteram o jeito de conectar pessoas, por meio
de amizades e interesses semelhantes. Com o crescimento desse tipo de aplicações, aumentam também a
oportunidade de algoritmos relacionados ao estudo de interações e informações fornecidas pelos usuários.
Na imagem a seguir é possível observar um grafo direcionado para estudo de envio de solicitações de
amizade, em que as pessoas são representadas pelos nós do grafo, e as arestas representam o envio do
convite de uma pessoa para outra.
1 em 1 pontos
Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0945 ... https://unifacs.blackboard.com/webapps/assessment/review/review.jsp?a...
4 of 9 10/04/2020 18:19
Resposta Selecionada:
Resposta Correta:
Feedback
da
resposta:
Fonte: Elaborada pelo autor.
Considerando o contexto apresentado, analise as afirmativas a seguir:
I. O grafo apresentado pode ser considerado um dígrafo.
II. O grau de entrada do nó “Gabriel” no grafo é 2, pois enviou duas solicitações de amizade.
III. Existe ao menos um ciclo no grafo.
IV. No grafo, a quantidade de ciclos e de laços é a mesma.
Está correto o que se afirma em:
I e IV, apenas.
I e IV, apenas.
Resposta correta. A alternativa está correta, podemos classificar um grafo como direcionado
(ou dígrafo) quando todas as ligações entre osnós são estabelecidas com ligações
direcionadas, logo, que seja possível identificar um vértice inicial e final. No caso do dígrafo
em questão, não conseguimos visualizar ciclos e laços. Os ciclos são caminhos que têm
como início e final o mesmo vértice. Os laços são ligações de um vértice com ele mesmo. A
quantidade desses dois elementos no grafo é igual a 0.
Pergunta 6
Existem maneiras diferentes de se percorrer uma árvore binária. Alguns tipos de busca utilizam a recursão
para navegar por todos os elementos. Algumas estratégias utilizam também outras estruturas de dados,
como uma fila ou pilha. Entretanto, as varreduras mais conhecidas são pré-ordem, intraordem e pós-ordem.
Considere a criação de duas árvores binárias I e II, em que a primeira é uma árvore de busca e a segunda,
apenas uma árvore binária.
1 em 1 pontos
Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0945 ... https://unifacs.blackboard.com/webapps/assessment/review/review.jsp?a...
5 of 9 10/04/2020 18:19
Resposta Selecionada:
Resposta Correta:
Feedback
da
resposta:
Fonte: Elaboradas pelo autor.
Considerando o objetivo de mostrar todos os elementos da árvore em ordem crescente, assinale a
alternativa que contenha as técnicas corretas para alcançar esse resultado:
I - intraordem e II - pós-ordem.
I - intraordem e II - pós-ordem.
Resposta correta. A alternativa está correta, pois na árvore I sabemos que a estrutura é uma
árvore binária de busca. Com essa característica, quando aplicamos a varredura em
intraordem obtemos os itens de forma ordenada, porque primeiro imprimimos o elemento
mais a subárvore esquerda (que é o elemento menor), depois a raiz e, por fim, a subárvore
direita (elemento maior). Na árvore II, como a árvore é binária, mas não é de busca, é
necessário realizar a varredura aplicando todos os algoritmos para que seja possível
descobrir qual é o elemento utilizado.
Pergunta 7
Um matemático estava estudando a criação de árvores binárias para adequação de equações. Ele
disponibilizou os elementos da equação de forma hierárquica, os números são armazenados nos nós folhas
e as operações serão armazenadas nos nós intermediários e no nó raiz. Após a criação da árvore e
inserção de seus elementos, realiza-se uma varredura em intraordem (ordem), em que uma equação é
formada. Os cálculos são realizados após a equação ter sido obtida.
0 em 1 pontos
Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0945 ... https://unifacs.blackboard.com/webapps/assessment/review/review.jsp?a...
6 of 9 10/04/2020 18:19
Resposta Selecionada:
Resposta Correta:
Feedback
da
resposta:
Fonte: Elaborada pelo autor.
Com base na estrutura de dados representada na imagem, assinale a alternativa que representa o
resultado da equação obtida:
10.
9.
Sua resposta está incorreta. A alternativa está incorreta. Precisamos lembrar sobre as
regras das técnicas de varredura em árvores. Diferentemente da pré-ordem e pós-ordem, na
intraordem as subárvores serão vistas na sequência: esquerda, raiz e direita. Além disso,
após formar a equação é necessário respeitar também a ordem dos operadores
matemáticos, em que primeiro realizamos a multiplicação e divisão e, só depois, a soma e
subtração. Obtendo a equação 1 + 4 * 4 / 2 * 1 = ? e analisando as regras dos operadores: 1
+ 16 /2 = 1 + 8 = 9.
Pergunta 8
Leia o excerto a seguir:
“Uma árvore binária é uma estrutura vazia ou um nó raiz e duas subárvores chamadas esquerda e direita,
as quais são também árvores binárias (vazias ou não). É importante observar que uma árvore binária não é
apenas uma árvore de grau máximo dois, pois há também a questão de ordem (esquerda e direita) de
subárvores [...]”
HONDA, W. Y.; PARABONI, I. ACH2023 - Algoritmos e estrutura de dados. Universidade de São Paulo.
2011. Disponível em: https://edisciplinas.usp.br/pluginfile.php/4379241/mod_resource/content/0/apostila_
AED1_completo.pdf . Acesso em: 05 jan. 2020.
A partir do apresentado, analise as asserções a seguir e a relação proposta entre elas.
I. Podemos chamar de árvores binárias de busca as árvores binárias cujos valores dos itens contidos nos
elementos das subárvores da direita sempre serão maiores e os da esquerda, menores ou iguais à
informação contida no nó raiz
Pois:
II. Assim é possível otimizar a busca por um item, de forma a direcionar quais subárvores devem ser
analisadas pelo algoritmo.
A seguir, assinale a alternativa correta:
1 em 1 pontos
Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0945 ... https://unifacs.blackboard.com/webapps/assessment/review/review.jsp?a...
7 of 9 10/04/2020 18:19
Resposta
Selecionada:
Resposta Correta:
Feedback
da
resposta:
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta
da I.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta
da I.
Resposta correta. A alternativa está correta, a asserção I é uma proposição verdadeira, pois
uma árvore de busca segue regras de inserção que utilizam os valores chaves dos nós,
mantendo a estrutura organizada. A asserção II também é verdadeira e justifica a I, pois
dessa organização é muito mais fácil e rápido recuperar uma informação contida na
estrutura, uma vez que o algoritmo é direcionado a consultar os valores de menos
elementos para alcançar o resultado.
Pergunta 9
Resposta Selecionada:
Resposta Correta:
Feedback
da
resposta:
Grafo de cena é uma técnica bastante conhecida na área de computação gráfica para modelagem de
cenários complexos. Em um jogo digital 3D, foi criado um grafo de cena para modelagem de um dormitório
de uma casa. Nesse contexto, os nós desse grafo representam objetos contidos nesse cômodo (nós folhas)
e operações geométricas aplicadas nesses objetos (nós internos). O grafo obtido está representado na
imagem a seguir.
 Fonte: Elaborada pelo autor.
Considerando o contexto apresentado, analise as afirmativas a seguir:
I. A raiz do grafo não representa uma operação geométrica e poderia ser descartada.
II. A transformação de rotação será aplicada nos objetos 1, 2 e 3.
III. A transformação de translação será aplicada em todos os objetos da cena.
IV. Se considerarmos o grafo como uma árvore, a altura dessa estrutura seria 3.
Está correto o que se afirma em:
III e IV, apenas.
III e IV, apenas.
Resposta correta. A alternativa está correta, pois em um grafo de cena podemos nos
beneficiar com uma propriedade chamada herança de estados. Nesse caso, como o nó da
translação é anterior a todos os nós dos objetos, essa transformação é aplicada em todos
1 em 1 pontos
Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0945 ... https://unifacs.blackboard.com/webapps/assessment/review/review.jsp?a...
8 of 9 10/04/2020 18:19
os nós sucessores. Além disso, o maior nível encontrado por um nó folha (ou seja, a
distância entre o nó folha até a raiz) seria de 3, o que definiria a altura da árvore.
Pergunta 10
Resposta
Selecionada:
Resposta Correta:
Feedback
da
resposta:
Leia o excerto a seguir:
“Um gráfico de cena é uma estrutura geral de dados que define a relação espacial e lógica de uma cena
gráfica para gerenciamento e renderização eficientes de dados gráficos. Geralmente, é representado como
um gráfico hierárquico, que contém um conjunto de nós gráficos, incluindo um nó raiz de nível superior, um
número de nós de grupo, cada um dos quais pode ter qualquer número de nós filhos e um conjunto de nós
folha, cada um dos quais possui zero nós filhos e que servem juntos como a camada inferior da árvore.”
(WANG, 2010, p. 8, Tradução nossa)
WANG, R.; QIAN, X. OpenScene Graph 3.0. Beginner's Guide . 1 ed. Birmingham: Packt Publishing. 2010.
A partir do apresentado, analise as asserções a seguir e a relação proposta entre elas.
I. Na herança de estados, qualquer efeito ligado às transformações de objetos que foi aplicado em nós
antecessores deve ser aplicado àquele nó.
Pois:
II. Quando um grafo possui vértices conectados por uma aresta, em que o acesso é feito de forma
ordenada, podemos chamá-los de dígrafos.
A seguir, assinale a alternativa correta:As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa
correta da I.
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa
correta da I.
Resposta correta. A alternativa está correta, a asserção I é uma proposição verdadeira, pois
a herança de estados refere-se à transmissão de transformações e efeitos aplicados em um
nó para seus sucessores. Isso permite facilitar a aplicação de um mesmo efeito para um
grupo de objetos. Já a asserção II também é verdadeira, mas não justifica a I, sendo que os
dígrafos são grafos cujo acesso de um nó para outro é feito de forma direcionada.…
1 em 1 pontos
Revisar envio do teste: ATIVIDADE 4 (A4) – GRA0945 ... https://unifacs.blackboard.com/webapps/assessment/review/review.jsp?a...
9 of 9 10/04/2020 18:19