MO417 - Questão para a prova oral

Número:

Enunciado: Conhecemos que o problema de decisão do CLIQUE é NP-Completo. Analise as sentenças a seguir e identifique a alternativa correta.

I) O problema de decisão do CLIQUE em grafos bipartidos é NP-Completo
II) O problema de decisão do CLIQUE em grafos planares é de classe P
III) O problema de decisão do CLIQUE em grafos densos não é NP-Completo

a) Apenas I está correta
b) Apenas II está correta
c) Apenas III está correta
d) Todas estão corretas
e) NDA


Ideia original de: John Edgar Vargas Muñoz

MO417 - Questão para a prova oral

Número:

Enunciado: Dado a seguinte rede em fluxo G na figura abaixo com origen s e sorvedor t :

Assinale a alternativa correta:

a) Existe um único fluxo máximo
b) O fluxo máximo em G é 12
c) O fluxo máximo em G é 9
d) O fluxo máximo em G é 15
e) NDA



Ideia original de: John Edgar Vargas Muñoz

MO417 - Questão para a prova oral

Número:

Enunciado: O seguinte grafo mostra o tempo em minutos para viajar entre 8 cidades.

Assinale a alternativa correta:

a) A aresta (E,F) pertence ao caminho que tem o tempo mínimo para viajar de A a H
b) A aresta (B,D) pertence ao caminho que tem o tempo mínimo para viajar de A a H
c) O tempo mínimo para viajar de A a H é 38
d) O tempo mínimo para viajar de A a F é 25
e) NDA


Ideia original de: John Edgar Vargas Muñoz

MO417 - Questão para a prova oral

Número:

Enunciado: Qual é a alternativa incorreta sobre os algoritmos Breadth First Search(BFS) e Depth First Search(DFS)?


a) Se pode utilizar DFS para mostrar os vértices de uma arvore em pós-ordem
b) DFS(v) produz uma arvore com raiz no vértice v
c) O tempo de execução de BFS é O(V+E), onde V é o número de vertices e E o número de arestas do grafo
d) DFS requer uma fila para manter uma lista dos vértices descobertos mas ainda não visitados
e) NDA



Ideia original de: John Edgar Vargas Muñoz

MO417 - Questão para a prova oral

Número:

Enunciado: O seguinte algoritmo insere o nó z numa árvore T.

TREE-INSERT(T,z)
1   y = NIL
2   x = T.root
3   while x <> NIL
4   y  = x
5 if z.key < x.key
6 x = x.left
7  else x = x.right
8   z.p = y
9   if y == NIL
10 T.root = z // tree T was empty
11 elseif z.key < y.key
12     y.left = z
13 else y.right = z

Depois de inserir os seguintes elementos (nessa ordem): 4, 6, 1, 2, 5, 9, 7 numa árvore vazia T. Qual não é uma folha de T?

a) 2
b) 5
c) 7
d) 9
e) NDA

Ideia original de: John Edgar Vargas Muñoz

MO417 - Questão para a prova oral

Número:

Enunciado: Um palindromo é qualquer sequência que é exatamente o mesmo que sua reversão, por exemplo ARA ou RACECAR. Qual é o ordem do tempo de execução de um algoritmo que utiliza programação dinámica que retorna o comprimento da maior subsequência palíndroma de uma sequência de n elementos.

a) O(n³)
b) Θ(n³)
c) O(n²)
d) O(n)
e) NDA



Ideia original de: John Edgar Vargas Muñoz

MO417 - Questão para a prova oral

Número:

Enunciado: Dado o seguinte algoritmo para fazer a busca do i-ésimo menor elemento:

RANDOMIZED-SELECT(A, p, r, i)
1  if p == r
2       return A[p]
3       q = RANDOMIZED-PARTITION(A, p, r)
4  k = q - p + 1
5  if i == k  // the pivot value is the answer
6       return A[q]
7  elseif i < k
8       return RANDOMIZED-SELECT(A, p, q - 1, i)
9  else return RANDOMIZED-SELECT(A, q + 1, r, i - k)

Se T(n) representa o tempo de execução do algoritmo RANDOMIZED-SELECT e S(n) representa o tempo de execução do algoritmo RANDOMIZED-SELECT trocando a linha 3 por uma partiçao que não seja aleatória, qual das seguintes afirmações é correta:

A) No pior caso T(n) = Θ(n) e  S(n) = Θ(n)
B) No pior caso T(n) = Θ(n²) e  S(n) = Θ(n²)
C) No caso médio T(n) = O(n) e  S(n) = O(n)
D) No caso médio T(n) = Θ(n²) e  S(n) = Θ(n²)
E) NDA

Ideia original de: John Edgar Vargas Muñoz