MO417- QUESTÃO PARA A PROVA ORAL

Número:  

Enunciado: Qual das seguintes alternativas não representa um problema NP-Completo?

a) Encontrar o caminho mais longo entre dois vértices de um grafo orientado
b) Encontrar um ciclo Hamiltoniano num grafo com |V| vértices e |V| arestas
c) O problema de caixeiro viajante com presença de arestas de peso negativo, sem ciclos negativos 
d)Um circuito no problema SAT que também use portas XOR (retorna 1 se X1 e X2 forem diferentes)
e) NDA

 Ideia original de: Sheila Katherine Venero Ferro

MO417- QUESTÃO PARA A PROVA ORAL

Número: Enunciado: Assinale a afirmação incorreta sobre o Fluxo máximo:

a) É possível ter uma rede com varias origens e vários sorvedores

b) Num fluxo em rede antiparalelo G=(V,E) se a aresta (u,v) ∈ E então a aresta (v,u) ∉ E

c) Se f é um fluxo máximo então sua rede residual tem pelo menos um caminho aumentante
d) O Algoritmo básico de Ford-Fulkerson tem um tempo de execução total de O(E │f*│),      onde f* é o fluxo máximo

e) NDA

Ideia original de: Sheila Katherine Venero Ferro

MO417- QUESTÃO PARA A PROVA ORAL
Número: 
Enunciado: 

Tem-se que conectar um conjunto de computadores entre eles com cabo de rede, só se pode conectar um computador diretamente com outro sem usar nenhum outro dispositivo, no seguinte grafo estão representados os computadores como vértices e as distancias mínimas em metros que um cabo pode recorrer entre cada dois computadores, como arestas. Indique qual seria o custo mínimo en reais para conecta-los, tomando em conta que cada metro de cabo custa 1.5 reais.

a) 84.0
b) 55.0
c) 82.5
d) 61.5
e) NDA

Ideia original de: Sheila Katherine Venero Ferro

MO417- QUESTÃO PARA A PROVA ORAL
Número: 
Enunciado: 

Tomando em conta a seguinte versão do algoritmo de busca em largura:

 

BFS(G,s)

1   for each vertex u∈G.V\{s}

2         u.color = WHITE

3         u.d = ∞

4         u.π = NIL

5   s.color=GRAY

6   s.d=0

7   s.π=NIL

8   Q=∅

9   ENQUEUE(Q, s)

10 while Q̸=∅

11       u = DEQUEUE(Q)

12       for each v ∈ G.Adj[u]

13             if v.color == WHITE

14                   v.color = GRAY

15                   v.d = u.d + 1

16                   v.π = u

17                   ENQUEUE(Q, v)

18       u.color = BLACK

Faça a execução do algoritmo BFS com o grafo representado pela seguinte matriz de adjacência e iniciando a partir do vértice "a":

	a	b	c	d	e	f
a	0	1	0	1	1	0
b	1	0	1	0	0	0
c	0	1	0	1	0	0
d	1	0	1	0	1	1
e	1	0	0	1	0	0
f	0	0	0	1	0	0

Indique quais são os predecessores π de cada vértice.

a) a.π=NIL, b.π=a, c.π=d, d.π=f, e.π=a, f.π=d

b) a.π=NIL, b.π=c, c.π=b, d.π=f, e.π=a, f.π=a

c) a.π=NIL, b.π=a, c.π=d, d.π=a, e.π=a, f.π=a

d) a.π=NIL, b.π=a, c.π=b, d.π=a, e.π=a, f.π=d

e) NDA

Ideia original de: Sheila Katherine Venero Ferro

MO417- QUESTÃO PARA A PROVA ORAL
Número: 
Enunciado: 

Sejam os conjuntos:

A={26, 30,50}

B={18,20,24}

C={13,10,6}

Se você insere os elementos desses conjuntos numa árvore de busca binaria no seguinte ordem: os elementos dos conjuntos A,C e B, é correto afirmar que:

a) A árvore resultante é balanceado

b)A altura da subárvore esquerda da raiz é maior da que a subárvore direita

c) A visita em pós-ordem dos nós é 6,10,18,20,24,13,50,30,26

d) A altura máxima da árvore é 4

e) NDA

Ideia original de: Sheila Katherine Venero Ferro

MO417- QUESTÃO PARA A PROVA ORAL
Número: 
Enunciado: 

Temos o conjunto A=X ∪ Y ∪ Z, onde |X|=|Y| =|Z|, e ∀ x ∈ X ∧ ∀ y ∈ Y, x>y; também ∀ y ∈ Y ∧ ∀ z ∈ Z, y>z. Se insertamos os elementos de A num árvore de busca binaria, primeiro insertando os elementos de X, logo os elementos de Z e finalmente os elementos de Y; é correto afirmar que a altura da subárvore da esquerda da raiz sempre tem maior altura que a subárvore da direita da raiz quando:

a) |A|<40

b) |A|≤24

c) em qualquer caso

d) |X|>4

e) NDA

Ideia original de: Sheila Katherine Venero Ferro

MO417- QUESTÃO PARA A PROVA ORAL
Número: 
Enunciado: Para o algoritmo: 

Fibb(n) 

1   if n <=1

2     return 1

3   else 

4     x=1

5     y=1

6     for i=2 to n

7       aux=x+y

8       y=x

9       x= aux

10   return aux    

Assinale qual é a afirmação falsa segundo o Algoritmo Fibb:

a) O algoritmo reduz um problema recursivo de O(2^n) para O(n)
b) O algoritmo requer o espaço O(n) para computar
c) O algoritmo não utiliza o método da divisão-e-conquista
d) O algoritmo consegue seu melhor caso no Θ(1)

e) NDA

Ideia original de: Sheila Katherine Venero Ferro

MO417- QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: É correto afirmar que:

a) O pior caso do Algoritmo Randomized-Select é o(n²)

b) O problema de seleção pode ser feito em complexidade o(n)

c) O número mínimo de comparações necessárias para determinar simultaneamente o   mínimo e o máximo de um conjunto são n

d) O Randomized-Select tem no melhor caso a complexidade de O(n) quando o particionamento é balanceado

e) NDA

Ideia original de: Sheila Katherine Venero Ferro

MO417- QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Sobre os algoritmos de ordenação vistos, é falso afirmar que:

a) Heapsort trabalha melhor com a memoria do que Merge Sort
b) Quicksort é eficiente com a memoria e é estável
c) Radix sort é um dos algoritmos de ordenação mais antigos
d) Bucket sort é um algoritmo de ordenação para números entre 0 ≤ x < 1
e) NDA



Ideia original de: Sheila Katherine Venero Ferro

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Para as seguintes recorrências, indique quais se aplicam ao Caso 3 do Teorema Mestre:

I.   1/2 T(n/2) + n²

II.   64 T(n/4) + n!

III.  3T(n/3) + n^1/2

IV. T(n/2) + 2ⁿ

a) Somente I

b) Somente II,III

c) Somente I, II, IV

d) Todas 

e) NDA

Ideia original de: Sheila Katherine Venero Ferro

MO417- QUESTÃO PARA A PROVA ORAL

Número:
  Quais das afirmações são corretas?  

I.    o(g(n))  ⊂ O(g(n))
II.   Ω(g(n)) ⊂ O(g(n))
III.  Ω(g(n)) ⊂ Θ(g(n))
IV. ω(g(n)) ⊂ Ω(g(n))

a)   Apenas II e IV são corretas
b)   Apenas IV e III são corretas
c)   Apenas I e III são corretas
d)   Apenas I e IV são corretas
e)   NDA

Ideia original de: Sheila Katherine Venero Ferro

Blog criado para a disciplina de Complexidade de Algoritmos -2013 UNICAMP