MO417 - Questão para a prova oral

Número:

Enunciado: Assinale a alternativa que contém todos os problemas NP-Completos da lista de problemas abaixo:

I - Ciclo Hamiltoniano.

II - Mochila Binária.

III - Problema da Satisfabilidade de Circuitos.

IV - Problema do Grupo Exclusivo.

(a) I, II e III.

(b) I, II e IV.
(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 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

MO417 - Questão para a prova oral

Número:

Enunciado: Considerando a árvore de pesquisa binária, assinale a alternativa que contém as afirmativas corretas:

I - A propriedade de árvore de pesquisa binária é irrelevante para o correto funcionamento da consulta em uma árvore de pesquisa binária.

II - A propriedade de árvore de pesquisa binária permite imprimir todas as chaves em sequência ordenada.

III - O custo de uma consulta em uma árvore de pesquisa binária é sempre O(lg n).

IV - O tempo de execução do método SEARCH-TREE é Ω(lg n).

V - O método SEARCH-TREE poderia ser implementado de forma iterativa para diminuir o gasto de memória do algoritmo.

(a) I, II e IV.

(b) II, III e V.

(c) I, II 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: Marque a opção que corresponde à ordem correta das etapas do desenvolvimento de um algoritmo de programação dinâmica.

(a) Construir uma solução ótima a partir de informações calculadas; Definir recursivamente o valor de uma solução ótima; Caracterizar a estrutura de uma solução ótima; Construir uma solução ótima a partir de informações calculadas;

(b) Calcular o valor de uma solução ótima em um processo de baixo para cima (bottom-up); Construir uma solução ótima a partir de informações calculadas; Definir recursivamente o valor de uma solução ótima; Caracterizar a estrutura de uma solução ótima;

(c) Caracterizar a estrutura de uma solução ótima; Definir recursivamente o valor de uma solução ótima;     Calcular o valor de uma solução ótima em um processo de baixo para cima (bottom-up); Construir uma solução ótima a partir de informações calculadas.
(d) Caracterizar a estrutura de uma solução ótima; Definir recursivamente o valor de uma solução ótima; Construir uma solução ótima a partir de informações calculadas; Calcular o valor de uma solução ótima em um processo de baixo para cima (bottom-up);

(e) N.D.A 

Idéia original de: Kim Pontes Braga

MO417 - Questão para a prova oral

Número:

Enunciado: Analise as proposições sobre o algoritmo RANDOMIZED-SELECT e assinale a alternativa que possuir somente proposições corretas.

I - Por ser um algoritmo aleatório, não há entrada específica que represente um cenário de pior caso.
II - No pior caso, o RANDOMIZED-SELECT tem tempo de execução O(n), pois é um algoritmo linear.
III - O algoritmo é linear porque faz suposições sobre a entrada.
IV - Resolve o problema de seleção sem ordenação.

    (a) I, II e IV.

    (b) I, II e III.

    (c) I, III e IV.

    (d) II, III e IV.

    (e) N.D.A

Idéia original de: Kim Pontes Braga

MO417 - Questão para a prova oral

Número:

Enunciado: Marque a alternativa INCORRETA sobre o Counting sort:

    (a) É um algoritmo estável.

    (b) Não é um algoritmo que realiza comparações entre os números a ordenar.

    (c) Ordena os valores in place.

    (d) Seu tempo de execução é O(n).

    (e) NDA

Idéia original de: Kim Pontes Braga