Questão semana 29/04 - 1ª questão

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Você está jogando um jogo online chamado DotA. Percebendo que pode converter o mapa do jogo em um grafo com os vértices representando as posições no mapa e as arestas os caminhos até eles, você quer usar o algoritmo que acabou de aprender para navegar neste grafo.Considere o seguinte mapa do jogo convertido em um grafo:

                                                     

Suponha que você queira encontrar um caminho saindo do vértice 0 (zero) a fim de chegar no vértice 1 (um) passando por todas as posições no mapa ( vértices ). Anote a ordem em que os vértices são inseridos na fila de vértices ao executar o algoritmo de BFS para encontrar este caminho:

(a) 0-2-5-7-6-3-4-1

(b) 0-2-6-7-5-4-3-1

(c) 0-5-2-4-7-3-6-1

(d) 0-5-2-7-4-3-6-1

(e) NDA

Ideia original de: Lucas Miguel de Carvalho

Questão semana 29/04 - 2ª questão

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dado as afirmações abaixo sobre algoritmos em grafos (considerando um grafo por G(V,E), onde V é o número de vértices e E o número de arestas )

I. A árvore BFS de um grafo é única.
II. A análise agregada do algoritmo BFS resulta em uma complexidade Θ(V+E).
III. Uma ordenação topológica não pode ser resolvida por DFS.
IV. Trabalhar com matrizes de adjacência é mais vantajoso do que com listas de prioridade.
V. A multiplicação da matriz de adjacência por ela mesma fornece o grafo complementar (GT(V,E)) do original, sendo G(V,E) direcionado.

A alternativa que representa as afirmações incorretas é:

a) I, II, III, IV, V
b) I, II , III, V
c) I, III , IV
d) I, II, IV
e) NDA.



Ideia original de: Lucas Miguel de Carvalho

Pergunta das aulas 16/04 e 18/04

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Após transformar um heap máximo em uma árvore binária, observou-se que ela possuía no máximo k elementos. Então a altura da árvore binária é:

a) lg(k+1) - 1
b) lgk
c) lgk +1
d) lg(k-1) + 1
e) NDA

Ideia original de: Lucas Miguel de Carvalho

Questão das aulas do dia 01/04 e 03/04 - 1ª questão

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: A principal diferença entre Programação Dinâmica e algoritmos de Divisão e Conquista é:

a) A Divisão e Conquista é mais eficiente quando todos os subproblemas são dependentes.
b) As soluções parcias em Programação Dinâmica são armazenadas e em Divisão e Conquista não.
c) A Programação Dinâmica é mais eficiente quando os subproblemas são independentes.
d) A Programação Dinâmica é mais adequada quando há sobreposições de subproblemas.
e) NDA

Ideia original de: Lucas Miguel de Carvalho

Questão das aulas do dia 01/04 e 03/04 - 2ª questão

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: Vamos considerar o problema de encontrar a Cadeia Comum mais Longa (LCS) , definindo  como LCS(A,B) a Cadeia Comum mais Longa entre as strings A e B.

Por exemplo, se considerarmos A={ALFABETO} e B={HABITAT} e os subproblemas A'={ALFA} e B'={HABI}, então podemos afirmar que:

a) LCS(A',B') + LCS(A-A',B-B') = LCS(A,B)
b) LCS(A',B') + LCS(A-A',B-B') ≠ LCS(A,B)
c) Não existe Cadeia Comum mais Longa entre os subproblemas A' e B'.
d) Só existe uma Cadeia Comum mais Longa entre A e B, ou seja, LCS(A,B) é única.
e) NDA.

Ideia original de: Lucas Miguel de Carvalho