MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dentre as alternativas abaixo, assinale a INCORRETA.

A) A classe de problemas NP pode ser definida como o conjunto de problemas de decisão que podem ser solucionados em tempo polinomial em uma Máquina de Turing não determinística.

B) Um problema c em NP também está em NPC se e somente se todos os outros problemas em NP podem ser transformados em p em tempo polinomial.

C) A classe de problemas P engloba todos os problemas de decisão que podem ser resolvidos por um algoritmo de tempo polinomial.

D) A classe de problemas NPC é um subconjunto dos problemas de decisão em NP de tal modo que todo problema em NP pode-se reduzir, com uma redução de tempo polinomial, a um dos problemas NPC.

E) N.D.A.

Ideia original de: Tiago Pedroso da Cruz de Andrade

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Uma empresa tem sua fábrica (onde os produtos são produzidos) localizada na cidade S e seu centro de distribuição (onde os produtos são armazenados para serem distribuídos) localizado na cidade T. Segundo o grafo abaixo, que mostra as rodovias que conectam as diversas cidades (vértices) e o número máximo de caminhões que podem trafegar por cada rodovia (arestas e seus pesos), qual é o número máximo de caminhões que a empresa pode enviar para o seu centro de distribuição?

A) 13

B) 22

C) 12

D) 11

E) N.D.A.

Ideia original de: Tiago Pedroso da Cruz de Andrade

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dado o grafo dirigido G = (V, E), a função de pesos das areas w e os algoritmos abaixo:

Assinale a alternativa que contém o valor d correto de cada um dos vértices do grafo G, após a execução do algoritmo DIJKSTRA-MODIFIED(G, w, z).

DIJKSTRA-MODIFIED(G, w, s)
  INITIALIZE-SINGLE-SOURCE-MODIFIED(G, s)
  Q = G.V
  while Q != ∅
    u = EXTRACT-MAX(Q)
    for each vertex v ∈ G.adj[u]
      RELAX-MODIFIED(u, v, w)

INITIALIZE-SINGLE-SOURCE-MODIFIED(G, s)
  for each vertex v ∈ G.V
    v.d = -∞
  s.d = 0

RELAX-MODIFIED(u, v, w)
  if v.d < u.d + w(u, v)
    v.d = u.d + w(u, v)

A) s.d = 3, t.d = 6, y.d = 8, x.d = 7, z.d = 0

B) s.d = 3, t.d = 6, y.d = 8, x.d = 12, z.d = 0

C) s.d = 3, t.d = 9, y.d = 11, x.d = 15, z.d = 14

D) s.d = 3, t.d = 9, y.d = 11, x.d = 12, z.d = 17

E) N.D.A.

Ideia original de: Tiago Pedroso da Cruz de Andrade

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Sobre os grafos, seus algoritmos e seus tipos de representações, podemos afirmar:

I - O custo total de execução tanto do BFS quanto do DFS independe do tipo de representação (lista ou matriz) do grafo.
II - O DFS é usado, entre outras coisas, para ordenação topológica e para achar as componentes fortemente conectadas.
III - O custo total do BFS e do DFS é theta(V + E) somente quando o grafo é representado por uma lista de adjacências.
IV - Um grafo pode ser representado ou por uma lista de adjacência ou por uma matriz de adjacência dependendo de qual otimização é necessária.

Dentre as afirmações acima, qual ou quais NÃO são verdadeiras:

A) I, somente

B) I, II e IV, somente

C) III, somente

D) I e III, somente

E) N.D.A.

Ideia original de: Tiago Pedroso da Cruz de Andrade

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dada a árvore de busca binária abaixo, assinale a alternativa que contém a sequência dos elementos do caminho 'postorder'.

A) 02, 07, 11, 27, 33, 38, 41, 62, 67, 81, 82, 84, 92

B) 82, 92, 84, 62, 67, 81, 33, 38, 02, 11, 07, 27, 41

C) 41, 27, 81, 07, 38, 67, 84, 02, 11, 33, 62, 82, 92

D) 02, 11, 07, 33, 38, 27, 62, 67, 82, 92, 84, 81, 41

E) N.D.A.

Ideia original de: Tiago Pedroso da Cruz de Andrade

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Através da análise do algoritmo da função LCS-LENGTH abaixo, podemos afirmar que o tempo de execução e o espaço auxiliar requerido por este algoritimo são, respectivamente:

LCS-LENGTH(X,Y)
 m = X.length
 n = Y.length
 let c[0 ... MIN(m,n)] be a new table
 for i = 0 to MIN(m,n)
  c[i] = 0
 for i = 1 to MAX(m,n)
  previous = c[0]
  for j = 1 to MIN(m,n)
   if Xi == Yj
    c[j] = previous + 1
   else if c[j] >= c[j - 1]
    previous = c[j]
   else
    previous = c[j]
    c[j] = c[j - 1]
 return c[MIN(m,n)]

A) theta(m + n) e theta(m * n)

B) theta(m + n) e theta(MIN(m,n))

C) theta(m * n) e theta(m + n)

D) theta(m * n) e theta(MIN(m,n))

E) N.D.A.

Ideia original de: Tiago Pedroso da Cruz de Andrade

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dado um vetor de n elementos inteiros, qual é a quantidade máxima de comparações necessárias para se encontrar, simultaneamente, tanto o elemento de menor valor quanto o elemento de maior valor?

A) n - 1

B) n lg n

C) 2n - 2

D) ⌊3n/2⌋

E) N.D.A.

Ideia original de: Tiago Pedroso da Cruz de Andrade

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Com relação ao QUICK SORT, qual das afirmações abaixo está INCORRETA?

A) Ele é local e não estável.

B) O pior caso ocorre quando o menor item do vetor é selecionado como pivo.

C) Ele possui complexidade O(n^2) para o pior caso.

D) O melhor caso ocorre quando a partição produz dois subproblemas com a mesma quantidade de elementos.

E) N.D.A.

Ideia original de:  Tiago Pedroso da Cruz de Andrade

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dada a recorrência T(n) = 2T(n/2) + n lg n, qual é o seu limite assintótico?

A) n lg n

B) n

C) n^2

D) n lg^2 n

E) N.D.A.

Ideia original de:  Tiago Pedroso da Cruz de Andrade

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dadas as recorrências abaixo, qual NÃO pode ser resolvida pelo método Mestre?

A) T(n) = 9T(n/3) + n

B) T(n) = T(2n/3) + 1

C) T(n) = 3T(n/4) + n lg n

D) T(n) = 2T(n/2) + n lg n

E) N.D.A.

Ideia original de:  Tiago Pedroso da Cruz de Andrade