Teste sobre Grafo e busca em largura e em profundidade

Pergunta 1: Os materiais de estudo fornecem detalhes sobre duas representações computacionais de grafos específicas?

A. Sim

B. Não

Explicação: Embora os materiais de estudo mencionem a necessidade de representar grafos eficientemente na memória de um computador e a existência de 'duas representações', eles não chegam a detalhar ou descrever quais são essas representações ou como elas funcionam. O texto é interrompido antes que qualquer representação específica seja apresentada.

Pergunta 2: De acordo com o material de estudo, qual é a principal característica que distingue um grafo direcionado de um grafo não direcionado?

A. A existência de pesos associados a cada aresta.

B. A natureza dos vértices que compõem o grafo.

C. A importância da ordem dos vértices em um par que representa uma aresta.

D. O número total de vértices e arestas presentes no grafo.

Explicação: O material de estudo afirma explicitamente: 'Se a ordem dos vértices em um par não importa, a aresta é não direcionada; se a ordem importa, a aresta é direcionada.' Portanto, a principal diferença reside na importância da ordem dos vértices nas arestas. A existência de pesos diferencia grafos ponderados de não ponderados, não direcionados de direcionados. A natureza dos vértices e o número total de vértices e arestas não são os fatores distintivos entre grafos direcionados e não direcionados.

Pergunta 3: Encontrar todos os vizinhos de um vértice em uma matriz de adjacência leva tempo constante O(1).

A. Sim

B. Não

Explicação: De acordo com os materiais de estudo, encontrar todos os vizinhos de um vértice em uma matriz de adjacência requer percorrer uma linha inteira da matriz, levando O(V) tempo, e não O(1).

Pergunta 4: Verificar a existência de uma aresta entre dois vértices utilizando uma lista de adjacência é uma operação de tempo constante O(1).

A. Sim

B. Não

Explicação: De acordo com os materiais de estudo, a desvantagem da lista de adjacência é que 'Verificar a existência de uma aresta entre dois vértices pode levar O(grau do vértice) tempo, no pior caso O(V)', não sendo, portanto, uma operação de tempo constante O(1).

Pergunta 5: De acordo com os materiais de estudo fornecidos, qual afirmação está correta sobre a eficiência de espaço de memória entre a Matriz de Adjacência e a Lista de Adjacência, especialmente para grafos esparsos?

A. A Matriz de Adjacência consome O(V + E) de espaço de memória, sendo sempre mais eficiente que a Lista de Adjacência.

B. A Lista de Adjacência consome O(V²) de espaço de memória, o que é ineficiente para grafos esparsos.

C. A Lista de Adjacência é mais eficiente em espaço de memória para grafos esparsos, pois consome O(V + E), enquanto a Matriz de Adjacência consome O(V²).

D. Ambas as representações consomem a mesma quantidade de espaço de memória, independentemente do tipo de grafo.

Explicação: Os materiais de estudo afirmam que a Matriz de Adjacência consome O(V²) de espaço de memória, o que pode ser ineficiente para grafos esparsos. Em contraste, a Lista de Adjacência consome O(V + E) de espaço de memória, o que é mais eficiente para grafos esparsos. Portanto, a Lista de Adjacência é mais eficiente em espaço para grafos esparsos.