ATIVIDADE 4 _ DISCIPLINA PROGRAMAÇÃO E INTEGRAÇÃO DE JOGOS - CURSO JOGOS DIGITAIS

Prévia do material em texto

QUESTÃO 1
Leia o excerto a seguir:
“Uma árvore binária é um conjunto finito de elementos que está vazio ou é particionado em três subconjuntos disjuntos. O primeiro subconjunto contém um único elemento, chamado raiz da árvore. Os outros dois subconjuntos são em si mesmos árvores binárias, chamadas subárvores esquerda e direita da árvore original.”
 
TENENBAUM, A. M.; LANGSAM, Y.; AUGENSTEIN, M. J. Estruturas de Dados Usando C. ed. 1, São Paulo: Pearson Universidades, 1995, p.303. 
 
Considerando o excerto apresentado, sobre as características de árvores binárias, analise as afirmativas a seguir:
 
I. Um conjunto finito de um ou mais elementos em uma árvore pode ser chamado de nós de uma árvore.
II. Em Árvores Binárias, um nó sem filhos, ou seja, que não possua subárvores, pode ser chamado de nó folha.
III. A ​profundidade ​de uma árvore é dada pelo maior nível de um nó folha.
IV. Existem três tipos de nós: raiz, folhas e sementes.
 
Está correto o que se afirma em:
 I, II e IV, apenas. 
 RESPOSTA CORRETA: I, II e III, apenas.
Resposta correta. A alternativa está correta, uma árvore é composta por itens que são chamados de nós. No processo de inserção, precisamos buscar a melhor posição para alocar o nó na árvore. Assim, cada nó estará a uma determinada distância do nó raiz, e a maior distância (definida por um dos nós folhas) determina a profundidade da árvore.
 I e II, apenas.
 II, III e IV, apenas.
 II e III apenas
QUESTÃO 2
Leia o excerto a seguir:
"Em diversas aplicações, necessita-se de estrutura mais complexas do que as puramente sequenciais [...]. Entre essas, destacam-se as árvores, por existirem inúmeros problemas práticos que podem ser modelados através delas. Além disso, as árvores, em geral, admitem um tratamento computacional simples e eficiente. Isto não pode ser dito de estruturas mais gerais do que as árvores, como os grafos, por exemplo.”
 
SZWARCFITER, J. L.; MARKENZON, L. Estruturas de Dados e seus Algoritmos, São Paulo: LTC, 1994, p. 61.
 
Analise as afirmativas a seguir:
 
I. Podemos dizer que uma árvore com apenas um elemento possui profundidade 0 (zero).
II. Nas árvores estritamente binárias, todo nó não folha deve possuir as subárvores esquerda e direita.
III. Uma árvore binária é completa de altura d quando todas as folhas estão no mesmo nível.
IV. Árvore Ordenada é um tipo de árvore que tem estrutura organizada de forma linear.
 
Está correto o que se afirma em:
 RESPOSTA INCORRETA: II, III e IV, apenas.
Sua resposta está incorreta. A alternativa está incorreta, pois uma árvore ordenada é aquela que segue uma forma de organização (muitas vezes hierárquica) bem definida. É possível representar diversos tipos de contextos, tanto em lógicas de inteligência artificial quanto em representações de ontologias e organização de conjuntos.
 I, II e IV, apenas.
 RESPOSTA CORRETA: I, II e III, apenas. 
 I e II, apenas.
 II e III apenas.
QUESTÃO 3
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.
Fonte: Elaborada pelo autor.
Com base na estrutura de dados representada na imagem, assinale a alternativa que representa o resultado da equação obtida:
 RESPOSTA CORRETA: 9.
Resposta correta. A alternativa está correta. A varredura em intraordem verifica primeiro os nós das subárvores localizados mais à esquerda, depois a raiz de cada um e, por último, os nós das subárvores mais à direita. Nessa lógica, obtemos a equação 1 + 4 * 4 / 2 * 1 = ?, e o resultado será 9.
 11.
 20.
 10.
 8
QUESTÃO 4
Estudando para um concurso na área de desenvolvimento de jogos, um desenvolvedor criou um programa para estudar os conceitos básicos sobre árvores binárias de busca. Na aplicação, foram gerados 8 números randômicos entre 1 e 20, que foram inseridos nesse tipo de estrutura de dados.
 
Supondo que os números gerados foram 6, 3, 12, 1, 4, 7, 15, 8, nessa ordem, avalie as afirmativas a seguir e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s).
 
I. ( ) A sequência dos nós quando ocorre a varredura em pré-ordem é: 6-3-1-4-12-7-8-15.
II. ( ) A sequência dos nós quando ocorre a varredura em intraordem é: 3-1-4-6-8-7-15-12.
III. ( ) A sequência dos nós quando ocorre a varredura em pós-ordem é: 1-4-3-8-7-15-12-6.
IV. ( ) A classificação para esse tipo de estrutura é uma árvore completa de altura 4.
 
Assinale a alternativa que apresenta a sequência correta:
 F, V, F, V.
 V, F, F, V.
 RESPOSTA CORRETA: V, F, V, F.
Resposta correta. A alternativa está correta, já que apresenta sequência adequada. A varredura em pré-ordem consiste em apresentar primeiro a raiz e só depois os elementos da subárvore esquerda e direita. Já na varredura em pós-ordem, serão acessados primeiro os elementos da subárvore esquerda, depois da direita e só por último a raiz. Após montar a árvore de busca, precisamos acessar os nós na ordem estabelecida pelos algoritmos de varredura. Assim, as afirmativas I e III são verdadeiras.
 F, F, F, F.
 V, V, V, V
QUESTÃO 5
Um dos maiores desafios dos jogos digitais é a renderização de cenários complexos e espaçosos. Não apenas pela quantidade de objetos, mas também devido ao nível de detalhamento dos objetos inseridos no ambiente virtual, muitos cálculos de posicionamento e efeitos são necessários. Os grafos de cenas buscam diminuir a complexidade desses tipos de sistemas, fornecendo uma estrutura adequada baseada em organização hierárquica e abstração.
Diante do cenário apresentado sobre grafos de cenas, assinale a alternativa correta:
 Em um grafo de cena, cada nó pode ter apenas dois nós sucessores.
 RESPOSTA CORRETA: Conseguem representar a existência de um objeto dentro de um grupo.
Resposta correta. A alternativa está correta, pois
um dos objetivos da utilização de um grafo de cena é fornecer uma organização hierárquica. Assim, é possível agrupar os objetos de algumas maneiras, sendo umas mais eficientes do que outras. Essa característica é um fator positivo quando modelamos cenários complexos.
 Não é possível representar detalhes de objetos em um grafo de cena.
 Os nós para os efeitos de translação e rotação não podem ter sucessores.
 Os objetos devem ser sempre representados com um único elemento.
QUESTÃO 6
Leia o excerto a seguir:
"Na maioria das vezes, as operações em uma árvore de pesquisa binária são simples de visualização. Podemos executar uma operação de localização iniciando na raiz e ramificando repetidamente para a esquerda ou direita, dependendo do resultado de uma comparação."
 
WEISS, M. A. ​Data Structures & Problem Solving Using Java​. 4 ed. London: Pearson Education, 2010, p. 688.
 
Considerando o contexto apresentado, analise as afirmativas a seguir:
 
I. No método de varredura pós-ordem, iniciamos a varredura lendo a subárvore esquerda em pós-ordem, depois a subárvore direita em pós-ordem e, por último, o nó raiz.
 
II. Quando realizamos comparações com outras estruturas de dados (como pilha, fila ou lista), uma árvore binária só será mais eficiente após o balanceamento dos nós.
 
III. No método de varredura pré-ordem: iniciamos a varredura pelo nó raiz; depois, a subárvore esquerda; e, por último, a subárvore direita, ambas em pré-ordem;
 
IV. A varredura em pré-ordem não é eficiente em árvores pequenas, com poucos nós e ramificações.
 
Está correto o que se afirma em:
 II e IV, apenas.
 RESPOSTA CORRETA: I e III, apenas.
Resposta correta. A alternativa está correta, a varredura em pré-ordem é iniciada pela raiz, na qual podemos consultar ou imprimir o(s) valor(es) contido(s) no item e, depois, exploramos a subárvore esquerda e direita, consecutivamente. Já na varredura em pós-ordem, iniciamos primeiro pelassubárvores esquerda e direita e só então pelo nó raiz. Esses métodos não produzem vantagens entre si. É necessário analisar o contexto aplicado para decidir qual o melhor método a ser utilizado, conforme as necessidades.
 I, II e III, apenas.
 II, III e IV, apenas.
 I, II e IV apenas.
QUESTÃO 7
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.
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:
 I e IV, apenas.
 II, III e IV, apenas.
 I, II e IV, apenas. 
 RESPOSTA CORRETA: 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.
 I, II e III.
QUESTÃO 8
Ao estudar sobre criptografia, um aluno experimentou criar uma sequência numérica e organizar cada um dos seus dígitos em uma árvore binária de busca. Assim, foi criada uma estrutura que permitisse a recuperação da informação, em que cada nó iria representar um dígito da mensagem criptografada. Para saber qual a senha correta, seria necessário descobrir qual forma de varredura foi estabelecida para ler essa estrutura.
Fonte: Elaborada pelo autor.
 
Sabendo que a forma de varredura escolhida pelo aluno foi intraordem e a árvore binária utilizada está representada na figura, assinale a alternativa que corresponda à senha utilizada pelo aluno:
 5-3-2-9-7-7-6.
 RESPOSTA CORRETA: 2-3-5-6-7-7-9.
Resposta correta. A alternativa está correta. A varredura em intraordem é dada visitando primeiro a subárvore à esquerda, depois o nó raiz e, em seguida, a subárvore mais à direita. Assim, nessa sequência, quando iniciamos os algoritmos, o nó com maior profundidade localizado mais à esquerda é o elemento 2. Isso já elimina três alternativas. Como a raiz é o segundo elemento a ser verificado, e a raiz do elemento 2 é o elemento 3, encontramos a resposta correta. Seguindo a sequência da lógica, obtemos a senha completa, que é 2-3-5-6-7-7-9.
 3-2-5-6-9-7-7.
 3-2-5-6-7-7-9.
 2-5-3-6-7-9-7
QUESTÃO 9
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:
 II e III, apenas.
 I, II e III, apenas.
 II, III e IV, apenas.
 RESPOSTA CORRETA: 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 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.
 I, II e IV apenas.
QUESTÃO 10
Uma árvore binária de busca foi criada com apenas três elementos, inseridos nesta ordem: 20, 16 e 24. Após a inserção, foi realizada uma varredura em pré-ordem na árvore. Suponha que durante a varredura cada nó acessado fosse incluído em uma estrutura de dados do tipo pilha.
Assinale a alternativa que corresponda à ordem correta dos elementos retirados da pilha:
 RESPOSTA CORRETA: 24 - 16 - 20.
Resposta correta. A alternativa está correta, pois o resultado da busca em pré-ordem é 20, 16 e 24. Quando inserimos esses elementos na pilha, nessa ordem, o topo possui a referência do 24 (último elemento inserido), depois a referência do 16 e, por fim, do 20. No momento de retirar a pilha, iremos retirar primeiro o elemento 24, depois o 16 e, por fim, o 20, sendo essa a alternativa correta.
 20 - 16 - 24.
 16 - 20 - 24.
 16 - 24 - 20.
 24 – 20 - 16