luc

MO417-QUESTÃO PARA A PROVA ORAL -1ª QUESTÃO

Número:

Enunciado: Quais das arestas devem ser removidas do grafo abaixo para que seja possível obter uma ordenação topológica?

a) 9 e 3

b) 8 e 5

c) 1 e 10

d) 9 e 1

e) NDA

Ideia original de: Lucas Oliveira Batista

pau

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-

Enunciado: Dado um grafo simples e não-orientado G = (V, E), cujo número de componentes conexos é 1, o algoritmo abaixo retorna um grafo caminho G_p = (V_p, E_p), tal que V_p = V. Considere que o algoritmo usa a representação por lista de adjacência; que a expressão G.V[i] retorna o i-ésimo vértice em V; que a expressão G.Adj[v][i] retorna o i-ésimo vértice da lista de adjacência do vértice v; que o grau mínimo dos vértices de G é 2.

1 toPathGraph(G)

2     Let G_p be a new Graph

3     for each v Є G.V

4         v.color = WHITE

5     G_p.V = G.V

6     v = G.V[1]

7     v.color = BLACK

8     For i = 1 to |V|-1

9          j = 1

10        do

11            u = G.Adj[v][j]

12            j = j + 1

13        while u.color == BLACK

14        G_p.Adj[v] ← u

15        G_p.Adj[u] ← v

16        v = u

17        v.color = BLACK

18    return G_p

É incorreto afirmar que:

1. Seu tempo de execução é Ω(|V|), onde |V| é o número de vértices de G.
2. O grafo G_p resultante possui |V| arestas.
3. O algoritmo não estaria mais correto se o grau mínimo dos vértices fosse 1.
4. Dado as restrições, é impossível que j, na linha 11, seja maior que |G.Adj[v]|, ou seja, maior que o grau do vértice v.
5. N.D.A.

Ideia original de: Paulo Henrique Hack de Jesus

gui

MO417 - Questão para a prova oral

Número:

Enunciado: Sobre as propriedades da Busca em Profundidade, assinale a alternativa correta:
 

1. A Busca em Profundidade não produz nenhuma informação valiosa sobre a estrutura de um grafo.
2. Se restar um vértice não descoberto, então ele é selecionado como uma nova origem e a busca passará por todos os vértices novamente, até pelos vértices já visitados anteriormente.
3. Como na Busca em Largura, o subgrafo predecessor na Busca em Profundidade pode ser composto por várias árvores.
4. O tempo de execução do DFS é Θ(V + E) se e somente se sua representação for dada pela lista de adjacência.
5. NDA
    

Ideia original de: Luís Guilherme Cordiolli Russi

mig1

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

lau

MO417 - QUESTÃO PARA PROVA ORAL

Número:

 

Enunciado: Dado o grafo abaixo, suponha que tanto o seu vetor de listas de adjacência como cada uma de suas listas de adjacência estão armazenados em ordem alfabética. Após a execução do algoritmo de  busca em profundidade a partir do vértice "a", marque a alternativa que exibe corretamente a estrutura de parênteses.
 

1. (a (b (d d) (c c) a)  b) (e e) (f f)
2. (a (b (c c) (d d) (e e) (f f) b) a)
3. (a (b (c c) (d (e e) (f f) d) b) a)
4. (a (b (d (e e) (f f) d) b) (c c) a)
5. NDA.

 

Ideia original de: Laurindo de Sousa Britto Neto

2013-05-03

arm

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Para a lista {112,242,122,53,634,12} quantos conjuntos disjuntos e quantas arestas são geradas quando a função FIND-SET é definida com:
FIND-SET: x -> x mod 3.

1. 3 conjuntos e 3 arestas.
2. 2 conjuntos e 4 arestas.
3. 3 conjuntos e 2 arestas.
4. 1 conjunto e 3 arestas.
5. NDA.

Ideia original de: Armando Faz Hernández.