MO417 - Questão para a prova oral

Número:

Enunciado: Sobre os algoritmos de Floyd-Warshall e Johnson, assinale a alternativa que contém as afirmativas verdadeiras:

I - O algoritmo de Floyd-Warshall tem complexidade O(n³).

II - O Algoritmo de Johnson usa os algoritmos de Dijkstra e Bellman-Ford como sub-rotinas baseado na existência de arestas de peso negativo.

III - Se o Algoritmo de Johnson usar o algoritmo de Dijkstra sua complexidade é O(V² lg V + VE).

IV - O algoritmo de Floyd-Warshall tem desempenho superior ao de Johnson em grafos esparsos.

V - O algoritmo de Johnson usa lista de adjacências ao invés de matriz de adjacências.

(a) I, II e IV.

(b) I, II e V.
(c) II, III e V.

(d) II, IV e V.

(e) N.D.A

Idéia original de: Kim Pontes Braga

MO417 - Questão para a prova oral

Número:

Enunciado: Sobre os algoritmos de grafos, assinale a alternativa que contém os itens corretos:

I - O algoritmo de Prim tem desempenho equivalente ao algoritmo de Kruskal quando o grafo é esparso.

II - O Algoritmo de Bellman-Ford tem desempenho superior ao algoritmo de Dijkstra em grafos orientados com pesos negativos.

III - A ordenação topológica de um grafo utiliza a busca em profundidade para encontrar o tempo de término de cada vértice, e dessa forma organizar os vértices de forma que eles fiquem ordenados decrescentemente pelo tempo de término. O algoritmo só funciona em grafos acíclicos não-orientados.

IV - Durante a execução do algoritmo de busca em profundidade, encontrar uma aresta de retorno indica que o grafo não é acíclico.

V - A melhor estrutura de dados para o algoritmo de Prim são as Heaps de Fibonacci, fazendo a complexidade do algoritmo ser O(E + V lg V).

(a) I, II e IV.

(b) II, III e V.

(c) I, IV e V.
(d) II, IV e V. 

(e) N.D.A 

Idéia original de: Kim Pontes Braga