Avaliação On-Line 4 (AOL 4) - Programação e Estrutura de Dados

Prévia do material em texto

Avaliação On-Line 4 (AOL 4) - 
Questionário 
Nota final 
Enviado: 08/11/21 11:30 (BRT) 
10/10 
1. Pergunta 1 
/1 
Uma das principais aplicações de grafos em um problema de logística é achar o menor 
caminho para várias entregas. No caso, cada ponto de entrega seria um vértice e cada 
rua, avenida ou caminho, seriam as arestas. Por ser um problema recorrente em 
grafos, existem diversos algoritmos para isso. Um deles se destaca por ser um dos mais 
simples para resolver este problema. Trata-se da árvore geradora mínima ou MST 
(Minimum Spanning Tree), que percorre os vizinhos até o fim e verifica se algum deles 
possui uma conectividade com os nós do grafo. 
Com base nessas informações e no conteúdo estudado, podemos dizer que o algoritmo 
usado no MST como forma de criar uma árvore geradora mínima é: 
Ocultar opções de resposta 
1. 
DFS ou busca por profundidade. 
Resposta correta 
2. 
lista de adjacência. 
3. 
matriz de adjacência. 
4. 
matriz de incidência. 
5. 
BFS ou busca por largura. 
2. Pergunta 2 
/1 
A fila é uma estrutura de dados homogênea, que tem por objetivo organizar e alocar os 
elementos da sua estrutura na forma de LIFO (Last in First Out), fazendo com que o 
primeiro a ser inserido seja removido. Sua função nos grafos se encontra dentro da 
busca por largura, removendo o nó visitado e buscando primeiro seus vizinhos em 
nível, assim, adicionando os vizinhos até chegar nos nós finais. 
Analise a situação a seguir: 
A-B-C-D 
A-E 
A-F-G-H 
Com base nessas informações e no conteúdo estudado, podemos dizer que o uso da fila 
em BFS, nesse caso, é: 
Ocultar opções de resposta 
1. 
D-H, C-G, B-E-F. 
2. 
B-E-F, D-H, C-G. 
3. 
B-C-D, E, F-G-H. 
4. 
B-C-D, F-G-H, E. 
5. 
B-E-F, C-G, D-H. 
Resposta correta 
3. Pergunta 3 
/1 
Uma das formas de navegar no grafo é através da lista de adjacência, que possui dois 
atributos: o vértice e a lista de vizinhos. Em vez de armazenar as arestas, armazena os 
vizinhos. 
Uma das vantagens da lista de adjacência é que ela não utiliza uma matriz como base e, 
portanto, pode ter tamanho indefinido. 
Analise a situação a seguir: 
public ArrayList buscarVizinhos (Vertice noaux){returnnew ArrayList <> (arestas 
[noaux.getIndice () ]);} 
No código-fonte acima, há uma criação estática, ou seja, com quantidades fixas de 
vértices. Foi utilizado um vetor de arestas para poder alocar os vizinhos. Com base 
nessas informações e no conteúdo estudado, podemos dizer que o comando utilizado 
para buscar o vizinho de um nó é: 
Ocultar opções de resposta 
1. 
buscarVizinhos (new int [1] [1]); 
2. 
buscarVizinhos (new Vertice ("A",1)); 
Resposta correta 
3. 
buscarVizinhos (new Aresta (1)); 
4. 
buscarVizinhos (new Grafo (1)); 
5. 
buscarVizinhos (1); 
4. Pergunta 4 
/1 
As estruturas de dados homogêneas são estruturas que possuem indexação por 
profundidade, porém com apenas uma tipagem. No caso de matrizes e vetores, 
independentemente do tamanho “N” que possuam, eles sempre terão a mesma 
tipagem. 
Por isso, existem diversas aplicações para essas estruturas, sendo uma delas na forma 
computacional de manipular um grafo. Na classe grafo, temos os vértices e a matriz de 
adjacência, que deve ser populada para possuir as arestas. Porém, o grafo em si é 
iniciado ao executar o construtor, pois este define os tamanhos da matriz da classe. 
Analise a situação a seguir: 
class Grafo{private Vertice nos [];private int matriz [] []; 
public Grafo (Vertice nosaux []){...}} 
Com base nessas informações e no conteúdo estudado, podemos dizer que a linha que 
corresponde ao comando do construtor do código acima é: 
Ocultar opções de resposta 
1. 
nosaux = nosaux; matriz = new int [nosaux.length] [nosaux.length]; 
2. 
nos = nosaux; matriz = new int [nosaux.length] [nosaux.length]; 
Resposta correta 
3. 
nos = nosaux; matriz = new int [10] [10]; 
4. 
nos = nos; matriz = new int [nos.length] [nos.length]; 
5. 
noaux = nos; matriz = new int [nos.length] [nos.length]; 
5. Pergunta 5 
/1 
A busca binária, é uma busca que tem por objetivo receber uma estrutura ordenada e 
fazer uma comparação parcial do dado que é tratado com o tamanho da metade da sua 
estrutura, caso o dado seja maior que a metade da estrutura o algoritmo faz um loop 
na segunda metade da estrutura, caso seja menor faz um loop na metade da estrutura, 
esse formato elimina de um total de valores praticamente metade de comparações, 
tendo como tamanho O(n/2), pois independente de ter o dado ou não na estrutura 
somente vai percorrer uma metade. 
Agora, leia o código-fonte a seguir: 
public static boolean buscaBinaria(int[] vetor, int pesquisar) {if ( … ) {for (int pos = 0; 
pos < vetor.length; pos++) {if (pesquisar == vetor[pos]) 
{System.out.println("Localizado");return true;}}} else {for (int pos = vetor.length; pos 
> 0; pos--) {if (pesquisar == vetor[pos]) {System.out.println("Localizado");return 
true;}}}return false;} 
Considerando essas informações e o conteúdo estudado, a alternativa que 
corresponde ao comando IF do código acima é: 
Ocultar opções de resposta 
1. 
pesquisar >= vetor[(int) (vetor.length)]. 
2. 
pesquisar == vetor[(int) (vetor.length / 2)]. 
3. 
pesquisar >= vetor[(int) (vetor.length / 2)]. 
Resposta correta 
4. 
pesquisar <= vetor[(int) (vetor.length)]. 
5. 
pesquisar != vetor[(int) (vetor.length)]. 
6. Pergunta 6 
/1 
Uma ArrayList é uma estrutura da Api Collection que trabalha com alocação dinâmica, 
possui aplicação em diversas situações e regras de negócio. No caso dos grafos, sua 
aplicação pode se dar na representação da lista de adjacência. A lista de adjacência é 
um formato de representação de grafo, que recebe do grafo um nó e as ligações (ou 
vizinho) de um nó e os aloca. 
Quando se trata da alocação de vizinhos, que pode ser fixa ou variável, a lista 
encadeada ou uma estrutura dinâmica é necessária para poder alocar os vizinhos de 
um nó. 
Com base nessas informações e no conteúdo estudado, podemos dizer que o comando 
usado para adicionar os vizinhos em uma lista de adjacência é: 
Ocultar opções de resposta 
1. 
setAresta (0,1); 
2. 
setAresta (0, new Vertice <> ({new Vertice ("B",1)})); 
3. 
setAresta (0, new ArrayList <> (Arrays.asList (new Vertice []{new Vertice 
("B",1)}))); 
Resposta correta 
4. 
setAresta (0, new Arrays.asList (ArrayList <> (new Vertice []{new Vertice 
("B",1)}))); 
5. 
setAresta (0, new Arrays.asList (ArrayList <> (new Vertice []{new 
Array("B",1)}))); 
7. Pergunta 7 
/1 
A busca por profundidade no grafo é uma das principais que podem ser executadas. 
Ela necessita da matriz de adjacência para poder percorrer os vértices. A busca por 
profundidade é conhecida por percorrer até o último vizinho de um vértice por vez, ou 
seja, percorre todo o caminho até o final de um vizinho, vai para o próximo e segue até 
o fim. 
Analise a situação a seguir: 
 
ESTRUT DADOS QUEST 08 UNID 4_v1.PNG 
Com base nessas informações e no conteúdo estudado, podemos dizer que o comando 
que retorna o resultado da busca DFS em A é: 
Ocultar opções de resposta 
1. 
B-E-D 
2. 
E-C-D 
3. 
B-C-D 
4. 
B-C-E 
Resposta correta 
5. 
B-D-E 
8. Pergunta 8 
/1 
A busca por largura BFS (Breadth-First Search), é um algoritmo de busca em grafos 
que retorna os níveis dos vizinhos deste o primeiro até o último vértice. Primeiro, ele 
mostra os vizinhos do nó, depois os vizinhos dos vizinhos e assim até chegar no final. 
Este formato de busca é ideal para mostrar os níveis de um nó, pois, diferente do DFS, 
ele mostra todo o caminho de um vizinho até chegar no próximo. Esses dois principais 
algoritmos de busca como DFS e BFS precisam que a propriedade “visitado” dos nós ou 
vértices estejam false, pois isso significa que este nó não foi percorrido e, portanto, 
poderá ser contabilizado. 
Analise a situação a seguir: 
 public void resetar (Grafo_MA adj) { for (int i = 0; i < adj.size (); i++) { ... } } 
Afunção resetar recebe uma matriz de adjacência e transforma em false a propriedade 
visitado de todos os vértices, através do comando adj.getNo (i), que visita o nó do 
índice i. Com base nessas informações e no conteúdo estudado, pode-se afirmar que a 
linha que corresponde à ação de setar como false no código acima é: 
Ocultar opções de resposta 
1. 
adj.getNo(new Vertice("A",i)).setVisitado(false); 
2. 
adj.getNo(i).setVisitado(false); 
Resposta correta 
3. 
adj.getNo(0).setVisitado(false); 
4. 
adj.getNo(i).setVisitado(true); 
5. 
adj.getNo(i.getIndice()).setVisitado(false); 
9. Pergunta 9 
/1 
O hash é uma estrutura de dados que se fundamenta no conceito de hashing, que, 
resumindo, trata-se de uma série de cálculos de dados juntamente com a quantidade 
de espaços disponíveis em memória. Esta técnica é muito utilizada em criptografia de 
textos, números, dados em geral e até bits. As principais formas de criptografia provêm 
de uma variação do hashing que carrega não somente o dado, mas a quantidade de bits 
e constantes (variáveis estáticas), para poder criptografar um dado de forma única. 
Analise a situação a seguir: 
public static int getHashCode(int valor, int tamanho){ ---------------- return 
hashcode; } 
Com base nessas informações e no conteúdo estudado, podemos dizer que o cálculo do 
hashing do código acima é: 
Ocultar opções de resposta 
1. 
int hashcode = Math.random() * (valor / tamanho) * 10; 
2. 
int hashcode = Math.pow(valor,tamanho); 
3. 
int hash = valor % tamanho; 
4. 
int hashcode = valor + tamanho / tamanho; 
5. 
int hashcode = valor % tamanho; 
Resposta correta 
10. Pergunta 10 
/1 
O HashMap é uma estrutura hash diferenciada, pois nela você é obrigado a setar o 
valor junto com sua posição de memória, no entanto ao instanciar um hashmap, deve-
se passar via parâtro da declaração a tipagem do índice e a tipagem do valor, no caso 
do exemplo abaixo, o índice é integer e o dado também, podendo assumir diversos 
tipos inclusive um objeto tanto como índice como quanto valor. 
Por conta da particularidade da inserção do índice junto com o valor a add, no 
hashmap não é usado e sim o put(indice,valor) para poder alocar, e o uso do constains 
é diferenciado pois pode-se buscar tanto por chave usando a containsKey quanto por 
valor containsValue.Por este motivo o hashmap é democrático pois você pode criar as 
posições que desejar e assim trazer mais agilidade ao programa caso necessite 
Analise a situação a seguir: 
import java.util.HashMap; 
import java.util.Map; 
public class Prj_HashMap {public static void main(String 
args[]){Map<Integer,Integer> mapa=new HashMap<Integer,Integer>(); 
mapa.put(1, 100); 
mapa.put(2, 200); 
System.out.println("remover:"+mapa.remove(2)); 
System.out.println("contains por chave:"+ mapa.get(1)); 
System.out.println("contains por chave:"+ mapa.containsKey(1)); 
System.out.println("contains por valor:"+ mapa.containsValue(100)); 
for(Integer aux: mapa.keySet() ){System.out.println(aux + "-" + aux.hashCode() + "-"+ 
mapa.get(aux) );} } } 
Com base nessas informações e no conteúdo estudado, analise as afirmativas a seguir e 
identifique qual dela(s) corresponde(m) ao padrão iterator na navegação da estrutura 
Mapa. 
I. Integer aux: mapa.keySet() 
II. new HashMap<Integer,Integer>();. 
III. mapa. 
IV. mapa.get(aux). 
V. mapa.getClass(). 
Está correto apenas o que se afirma em: 
Ocultar opções de resposta 
1. 
II e I. 
2. 
IV e II. 
3. 
I e IV. 
Resposta correta 
4. 
III e IV. 
5. 
V e III.