AOL4

Prévia do material em texto

Conteúdo do exercício
Ocultar opções de resposta 
Pergunta 1 -- /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 é:
setAresta (0,1); 
setAresta (0, new Arrays.asList (ArrayList <> (new Vertice []{new Array("B",1)}))); 
Resposta corretasetAresta (0, new ArrayList <> (Arrays.asList (new Vertice []{new Vertice ("B",1)}))); 
setAresta (0, new Vertice <> ({new Vertice ("B",1)})); 
setAresta (0, new Arrays.asList (ArrayList <> (new Vertice []{new Vertice ("B",1)}))); 
Pergunta 2 -- /1
Ocultar opções de resposta 
Ocultar opções de resposta 
Existem muitas formas de navegação dentro de um grafo. Uma das mais comuns é a matriz de adjacência, 
uma matriz que possui o mesmo número de linhas e de colunas – ou seja, quadrada – e sua quantidade de 
elementos, tanto linhas quanto colunas, é o total de vértices do grafo. Nesse sentido, toda matriz de 
adjacência sempre será bidimensional. Essa é uma das principais formas de visualização de grafos dentro 
dos algoritmos, onde estes recebem a matriz e fazem o processamento pelas ligações dos vértices.
Analise a situação a seguir:
Com base nessas informações e no conteúdo estudado, dizemos que o grafo que corresponde a essa 
matriz é:
BQ04 - Tópicos Integradores II(ADS) - Questão 4.PNG
G-F-X.
Resposta corretaF-X-G.
F-G-X.
F-X e G isolado.
X-F-G.
Pergunta 3 -- /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:
Com base nessas informações e no conteúdo estudado, podemos dizer que o comando que retorna o 
resultado da busca DFS em A é:
BQ04 - Tópicos Integradores II(ADS) - Questão 8.PNG
E-C-D
Ocultar opções de resposta 
B-C-D 
B-D-E 
Resposta corretaB-C-E 
B-E-D
Pergunta 4 -- /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 é:
matriz de incidência.
BFS ou busca por largura.
Resposta corretaDFS ou busca por profundidade.
lista de adjacência.
matriz de adjacência.
Pergunta 5 -- /1
Ocultar opções de resposta 
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:
V e III.
IV e II.
III e IV.
II e I.
Resposta corretaI e IV.
Ocultar opções de resposta 
Pergunta 6 -- /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 é:
Resposta corretapesquisar >= vetor[(int) (vetor.length / 2)].
pesquisar != vetor[(int) (vetor.length)].
pesquisar >= vetor[(int) (vetor.length)].
pesquisar == vetor[(int) (vetor.length / 2)].
pesquisar <= vetor[(int) (vetor.length)].
Ocultar opções de resposta 
Pergunta 7 -- /1
A estrutura hash possui um dos melhores desempenhos dentro de uma grande estrutura de dados, pois 
sua notação de big O(1) é uma constante. Ou seja, para N dados, temos apenas um conjunto de instruções 
a se buscar. Porém, com a grande quantidade de dados, surge o problema da colisão, quando dados 
diferentes assumem o mesmo valor de hash. Existem formas de trabalhar o hashing para que isso não 
ocorra, porém, é preciso usar uma outra estrutura de dados para poder considerar um hash repetido de 
dados distintos. Uma das estruturas possíveis é a linkedlist, que faz a alocação do dado repetido ou 
aproximado dentro de um mesmo hash.
Com base nessas informações e no conteúdo estudado, podemos dizer que a técnica utilizada para a 
colisão é:
o new LinkedList.
o linear probing.
o rerash.
o load factor.
Resposta corretao encadeamento separado.
Pergunta 8 -- /1
A pilha é uma estrutura de dados homogênea, que se comporta mais ou menos da mesma forma que uma 
pilha do mundo real, tendo seus dados organizados na estrutura LIFO (Last in First Out). Uma das 
aplicações das pilhas é no algoritmo de busca de grafos, no DFS que busca por profundidade, onde sua 
busca aplica-se em receber um vérticee retornar todos os caminhos atrelados a partir dele.
Analise a situação a seguir:
public void buscaDFS(Grafo_MA adj) { /*Grafo_MA adj é matriz de adjacência*/
Ocultar opções de resposta 
  this.resetar(adj);
  Stack<Vertice> pilha = new Stack<>();
  adj.getNo(0).setVisitado(true);
  pilha.add(adj.getNo(0));
  System.out.print(adj.getNo(0).getNome());
  while (!pilha.isEmpty()) {
    /*chamada da função getIDVizinhos com argumentos de matriz de adjacência e o índice do topo da 
pilha*/
    DECLARAÇÃO IDVIZINHO
    if (idVizinho == -1) {
       pilha.pop()
    ;} else {
    adj.getNo(idVizinho).setVisitado(true);
    pilha.push(adj.getNo(idVizinho));
    System.out.print("," + adj.getNo(idVizinho).getNome());
    }
  }
}
Com base nessas informações e no conteúdo estudado, o código que corresponde à declaração de 
idVizinho no DFS é:
int idVizinho = this.getVertices (pilha.peek ().getIndice (), pilha.peek ().getIndice ()); 
int Vizinho = this.getIDVizinhos (0, pilha.peek ().getIndice ());
Resposta corretaint idVizinho = this.getIDVizinhos (adj, pilha.peek ().getIndice ());
int idVizinho = this.getVertices (adj,pilha.peek ().getIndice ());
int idVizinho = this.getIDVizinhos (pilha.peek ().getIndice (),pilha.peek ().getIndice ());
Pergunta 9 -- /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:
Ocultar opções de resposta 
Ocultar opções de resposta 
Com base nessas informações e no conteúdo estudado, podemos dizer que o uso da fila em BFS, nesse 
caso, é:
BQ04 - Tópicos Integradores II(ADS) - Questão 11.PNG
B-C-D, F-G-H, E.
B-E-F, D-H, C-G.
Resposta corretaB-E-F, C-G, D-H.
D-H, C-G, B-E-F.
B-C-D, E, F-G-H.
Pergunta 10 -- /1
A busca sequencial é uma das formas mais simples de trabalhar a estrutura de dados. Seu algoritmo 
geralmente é um loop e não possui critérios com relação a busca em si. O que temos é somente uma 
condição para encontrar o dado dentro do algoritmo. Este formato de busca chama-se sequencial, pois 
percorre todos os elementos da estrutura de forma estática e pode ser usado em vetores e matrizes de 
forma dinâmica, percorrendo posições de memória ou retornando endereços de objetos diferentes de 
nulo.
Analise a situação a seguir:
for(int i=0;i< 5; i++)
for(int j=i+1;j< 10; j++)
if( ... )
System.out.println("Dado:"+buscar+" localizado");
Com base nessas informações e no conteúdo estudado, podemos dizer que a alternativa que corresponde 
ao comando IF acima é:
buscar = numeros[i].
buscar = numeros[j].
buscar = numeros[i][j].
buscar == numeros[j][i].
buscar == numeros[i][j].