AOL4 - PROGRAMAÇÃO E ESTRUTURA DE DADOS

Prévia do material em texto

AOL 4 – PROGRAMAÇÃO E ESTRUTURA DE DADOS
1. Pergunta 1
/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 é:
B-C-E 
Resposta correta
2. Pergunta 2
/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 é:
DFS ou busca por profundidade.
Resposta correta
3. Pergunta 3
/1
A pesquisa de dados é um tópico da estrutura de dados que envolve o estudo dos algoritmos para sequências numéricas, seja ordenada ou desordenada, em ordem crescente ou decrescente.
Neste aspecto surge, dentro da pesquisa de dados, uma ferramenta chamada análise assintótica, que recebe um algoritmo e, pelas próprias instruções, nos fornece uma fórmula matemática para analisar graficamente o comportamento deste algoritmo, em seu pior caso, no computador.
Com base nessas informações e no conteúdo estudado, podemos dizer que o melhor algoritmo em pesquisa de dados, de acordo com sua fórmula, é:
O(1).
Resposta correta
4. Pergunta 4
/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ó é:
buscarVizinhos (new Vertice ("A",1)); 
Resposta correta
5. Pergunta 5
/1
As arestas são a principal forma de manipular e modelar o grafo e, dependendo da aresta, até de classificá-lo como um todo. É um modelo que foca mais nas ligações do que nos dados em si.
Em resumo, a aresta é a ligação dos vértices ou nós que, em conjunto, formam um caminho e uma estrutura organizada sem topologia ou ordem de dados.
Sobre o formato A -> B, B <- C, e D - A, pode-se afirmar que:
A, B e C são orientadas, enquanto D com A não são orientadas.
Resposta correta
6. Pergunta 6
/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 é:
int hashcode = valor % tamanho;
Resposta correta
7. Pergunta 7
/1
Os vértices ou “nós” são os componentes de um grafo que designam o sentido de uma aresta. Se um grafo não possui vértices, ele não possui arestas. Os vértices, na programação, são classes que não se referenciam, porém possuem algumas propriedades que designam rótulo, focando em alguns algoritmos, no índice ou Ids. Em programação orientada a objetos, temos o encapsulamento que, como o nome diz, encapsula essas propriedades em métodos getters e setters, para cada propriedade, que em classe se torna um atributo. 
Analise a situação a seguir:
class Vertice {private static int indice;private static String nome;boolean static visitado=false;}
Com base nessas informações e no conteúdo estudado, podemos dizer que o encapsulamento do atributo índice corresponde a:
public void setIndice (int aux) {...} public int getIndice () {...} 
Resposta correta
8. Pergunta 8
/1
As tabelas hash podem ser desenvolvidas à mão, porém, no Java existe a chamada API Collection, que auxilia na aplicação desta estrutura sem necessariamente precisar criar do zero, através da interface SET<T> com a instanciação da classe HashSet<T> ().
Embora esteja usando a interface SET, os comandos para inserir, editar, pesquisar e remover possuem, basicamente, a mesma sintaxe para quase todas as coleções.
Analise a situação a seguir:
import java.util.HashSet;
import java.util.Set;
public class Prj_Hash {public static void main(String args[]){Set<Integer> hasht=new HashSet<Integer>();     hasht.add(100);     System.out.println("remover:"+hasht.remove(100));System.out.println("contains:"+ hasht.contains(100));}   }
Assim, considerando as informações apresentadas e os conteúdos estudados, analise as operações a seguir e associe-as às suas respectivas características:
1) add
2) remove
3) contains
4) iterator
5) isEmpty
I. ( ) Remove elementos da estrutura
II. ( ) Retorna um objeto navegável através de um padrão de projeto
III. ( ) Retorna se contém elementos na estrutura ou não
IV. ( ) Busca elementos na estrutura
V. ( ) Insere elementos na estrutura
Agora, assinale a alternativa que apresenta a sequência correta:
2, 4, 5, 3, 1.
Resposta correta
9. Pergunta 9
/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, new ArrayList <> (Arrays.asList (new Vertice []{new Vertice ("B",1)}))); 
Resposta correta
10. Pergunta 10
/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++) {            ...    }  }
A funçã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 é:
adj.getNo(i).setVisitado(false); 
Resposta correta