MO417 - Questão para a prova oral

Número: 2010-073

Enunciado: Considerando a busca em profundidade realizada sobre o grafo a seguir, com os tempos de chegada e de partida apresentados em cada vértice, assinale a alternativa CORRETA:

1. I, II e III são arestas de árvore
2. IV é uma aresta cruzada
3. V é uma aresta de retorno
4. VI é uma aresta direta
5. NDA

Ideia original de: Priscila Tiemi Maeda Saito

MO417 - Questão para a prova oral

Número: 2009-122

Enunciado: Uma metódica secretária organiza os documentos de seu escritório da seguinte forma.  Ela dispõe de um armário A, com 3 gavetas: g₁, g₂ e g₃. Ela dispõe também de 3 pastas, p₁, p₂ e p₃, e de 3 envelopes, e₁, e₂ e e₃. Além disso, a secretária segue as seguintes regras:

a) documentos só podem ser guardados dentro de envelopes;
b) envelopes só podem ser guardados dentro de pastas;
c) pastas só podem ser guardadas dentro de gavetas e
d) as gavetas só podem estar dentro do armário.

Para procurar documentos, a secretária executa somente buscas em profundidade em seu armário. Ou seja, considerando o armário, as gavetas, as pastas e os envelopes como recipientes de um documento, do maior para o menor nesta ordem, ela sempre abrirá um recipiente maior para ter acesso a um menor. Além disso, sempre fechará os recipientes abertos antes de continuar procurando em outros de igual tamanho, e também ao terminar a busca.  Numa busca em profundidade como essa, as operações de abertura e fechamento de um recipiente detêm a propriedade de estrutura de parênteses. Se representarmos a abertura de um recipiente r como "(r" e o seu fechamento como "r)", a história da busca gerará uma expressão bem formada, com os parênteses corretamente aninhados.

Assim sendo, indique qual das alternativas abaixo NÃO representa corretamente uma possível história de busca a um documento feita pela secretária:

1. (A (g1 (p2 (e1 e1) (e2 e2) p2) g1) A)
2. (A (g2 (p3 (e1 e1) p3) g2) A)
3. (A (g2 (e3 (p3 p3) e3) g2) (g1 (p2 (e1 e1) p2) g1) A)
4. (A (g3 g3) (g1 (p2 p2) g1) (g2 (p1 (e3 e3) p1) g2) A)
5. NDA

Ideia original de: Fábio de Souza Azevedo

MO417 - Questão para a prova oral

Número: 2009-121

Enunciado: Considere a busca em profundidade abaixo, com tempos de chegada e partida em cada vértice, e assinale a alternativa verdadeira:

1. A aresta d é uma aresta de árvore.
2. A aresta e é uma aresta de retorno.
3. Existem duas arestas diretas.
4. Existem quatro arestas de árvore.
5. NDA

Ideia original de: José Vieira Maciel Borges

MO417 - Questão para a prova oral

Número: 2009-119

Enunciado: Considere o grafo abaixo:



Em seu estado atual uma ordenação topológica não pode ser realizada. Escolha, dentre as alternativas abaixo, aquela que indica duas arestas a serem removidas de modo que uma ordenação topológica seja possível.

1. (6, 2) e (6, 3)
2. (5, 2) e (7, 4)
3. (6, 2) e (3, 4)
4. (2, 4) e (1, 2)
5. NDA

Ideia original de: Bruno Conti Marini

MO417 - Questão para a prova oral

Número: 2009-117

Enunciado: Qual das afirmativas abaixo é VERDADEIRA:

1. Busca em profundidade sempre pode ser usada para determinar o menor caminho entre dois vértices.
2. Considerando uma busca em profundidade em um grafo: para todo vértice v, a primeira aresta percorrida a partir de v sempre é classificada como uma aresta de árvore.
3. Para grafos direcionados, se o vértice u foi descoberto antes do vértice v em uma busca em profundidade, então a aresta (v,u) é de retorno.
4. O algoritmo de Kruskal, usado para achar a árvore geradora mínima, não precisa necessariamente analisar todas as arestas do grafo para decidir sua inclusão na árvore.
5. NDA

Ideia original de: Luiz Augusto Muniz de Paula

MO417 - Questão para a prova oral

Número: 2003-146

Enunciado: Escolha, entre as alternativas abaixo, aquela que representa uma ordenação topológica do seguinte grafo acíclico orientado, obtida através de busca por profundidade, produzindo os seguintes carimbos de tempos ( x / y = tempo de descoberta / tempo de término ):

  A) A E B H G C F D
  B) E A H B C G F D
  C) A E H B C G F D
  D) A ordem dos tempos não pode estar correta
  E) n.d.a.

Ideia original de: Ivan Brunetto

MO417 - Questão para a prova oral

Número: 2013-071

Enunciado: Considere uma busca em profundidade no seguinte grafo orientado, supondo que vértices são processados em ordem alfabética e que as listas de adjacência também estão em ordem alfabética:

Qual das seguintes afirmações é correta?

a) A busca resulta em 3 "DFS trees", 7 "cross edges", 1 "back edge" e pode ser ordenado topologicamente.
b) A busca resulta em 3 "DFS trees", 7 "cross edges", 1 "back edge" e não pode ser ordenado topologicamente.
c) A busca resulta em 3 "DFS trees", 1 "cross edges", 7 "back edge" e não pode ser ordenado topologicamente.
d) A busca resulta em 3 "DFS trees", 1 "cross edges", 7 "back edge" e pode ser ordenado topologicamente.
e) NDA.

Ideia original de: Carlos Eduardo Alfaro Morales

MO417 - Questão para a prova oral

Número: 2013-070

Enunciado: Considere uma busca em profundidade no grafo abaixo.

 

Definimos d[u] como o carimbo de tempo registrado quando u é descoberto e f[u] como o carimbo de tempo registrado quando a busca termina de examinar a lista de adjacências de u. Visto que a busca pode iniciar-se a partir de qualquer vértice, e continuar em componentes ainda não atingidas reiniciando-se também em qualquer vértice não ainda descoberto, é possível afirmar que:

1. Se d[A] > d[E] então f[A] < f[E]
2. Se d[A] < d[B] então f[C] > f[E]
3. Se f[F] < f[B] então d[B] < d[F]
4. Se d[F] < d[B] então d[A] < d[D]
5. NDA

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-068

Enunciado: Após a realização de uma busca em profundidade no grafo abaixo, todas as arestas foram classificadas como cruzadas (cross edges).

 

Em que ordem os vértices podem ter sido visitados para a obtenção deste resultado?

1. a - b - c - d
2. a - b - d - c
3. a - c - b - d
4. d - c - b - a
5. N.D.A.

Ideia original de: Daniel Henriques Moreira

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-067

Enunciado: Execute uma busca em profundidade no grafo abaixo, supondo que as listas de adjacências estejam em ordem alfabética. Toda vez que for reiniciá-la, pegue o primeiro vértice em ordem alfabética que ainda não foi visitado. Com base na classificação das arestas da busca em profundidade, pode-se dizer que o algoritmo encontrará durante o percurso:

Lembrete: 

I) Aresta de Árvore: faz parte de uma árvore de busca em profundidade;

II) Aresta de Retorno: liga um descendente a um ancestral;

III) Aresta Diretas: liga um ancestral a um descendente que não seja filho;

IV) Arestas Cruzadas: as demais.

a) 7 Arestas de Árvore e 2 Arestas de Retorno
b) 2 Arestas Diretas e 2 Arestas Cruzadas
c) 8 Arestas de Árvore e 1 Arestas de Retorno
d) 2 Arestas Diretas e 3 Arestas Cruzadas
e) NDA 
 

Ideia original de: Ademar Takeo Akabane

MO417 - Questão para a prova oral

Número: 2013-066

Enunciado : Sabe-se que foi feita uma busca em profundidade no grafo abaixo, a partir do vértice A.

Podemos afirmar com absoluta certeza que:

a)      A aresta (F,D) é uma aresta de árvore.

b)     A aresta (C,A) é uma aresta de retorno.

c)      A aresta (E,C) é uma aresta cruzada.

d)     A aresta (B,E) é uma aresta cruzada.

e)      N.D.A. 

Ideia original de: Erick Aguiar Donato

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-065

Enunciado: A partir do grafo orientado G = (V, E), com V = {1,2,3,4,5,6} e E = {(1,3), (2,6), (3,2), (3,5), (5,1), (5,4), (6,2), (6,4)}, analise as seguintes afirmações:

I - Conseguimos tornar G um grafo fortemente conexo invertendo o sentido de apenas uma de suas arestas.
II - Para que G tenha exatamente dois componentes fortemente conexos, faz-se necessário inverter o sentido de mais de duas de suas arestas.
III - É possível obter uma ordenação topológica para o grafo G, caso sejam removidas duas de suas arestas.

Assinale a alternativa correta:

a. I, II e III estão corretas.
b. apenas II e III estão corretas.
c. apenas I e III estão corretas.
d. apenas I e II estão corretas.
e. NDA

Ideia original de: Anderson Coelho Weller

MO417 - Questão para a prova oral

Número: 2013-062

Enunciado: Suponha que numa busca em profundidade (depth-first search) os nós recebem cores segundo o seguinte esquema:
BRANCO - nunca foi visitado
CINZA - já foi visitado, mas sua sub-árvore ainda não foi totalmente explorada
PRETO - sua sub-árvore já foi totalmente explorada

Ao encontrar uma aresta (u,v) durante a busca, quais das afirmações abaixo são corretas?

I - Se v estiver BRANCO, (u,v) será uma aresta de árvore (tree edge)
II - Se v estiver CINZA, (u,v) será uma aresta de cruzamento (cross edge)
III - Se v estiver PRETO, (u,v) será uma aresta de cruzamento (cross edge) ou uma aresta de avanço (forward edge), em grafos orientados, e tal situação não ocorre em grafos não-orientados

a. apenas I
b. apenas II
c. I e II
d. II e III
e. NDA

Ideia original de: Jorge Augusto Hongo

MO417 - Questão para a prova oral

Número: 2013-058

Enunciado: Qual alternativa contém uma lista de arestas que, se removidas do grafo abaixo, tornam possível obter uma ordenação topológica?

a) 1 e 9

b) 1 e 10

c) 3 e 9

d) 5 e 8

e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - Questão para a prova oral

Número: 2013-057

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 estejam 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

MO417 - Questão para a prova oral

Número: 2010-069

Enunciado: Percursos em árvores binárias podem ser implementados utilizando-se a ideia de busca em profundidade em grafos. Existem basicamente três tipos de percursos:

• pré-ordem: Primeiro se visita a raiz, depois a subárvore esquerda e então a subárvore direita
• in-ordem: Primeiro se visita a subárvore esquerda, depois a raiz e então a subárvore direita
• pós-ordem: Primeiro se visita a subárvore esquerda, depois a subárvore direita, e então a raiz

Um percurso em pré-ordem em uma árvore binária A visitou os vértices na sequência:
h, o, x, r, j, s, p, t, z, k, i.
Um outro percurso in-ordem na mesma árvore binária A visitou os vértices na sequência:
r, x, j, o, s, h, z, t, k, p, i.
Das alternativas abaixo, qual é um possível percurso pós-ordem para a árvore A?

1. i, p, t, z, k, h, o, s, x, j, r
2. r, j, s, x, o, z, k, i, t, p, h
3. i, z, k, t, p, s, j, r, x, o, h
4. r, j, x, s, o, z, k, t, i, p, h
5. NDA

Ideia original de: Leonardo de Paula Rosa Piga

MO417 - Questão para a prova oral

Número: 2010-068

Enunciado: Considere o grafo orientado a seguir, onde será realizada uma busca em profundidade partindo-se do vértice de cor branca. Durante a busca, gera-se uma floresta de busca em profundidade e classificam-se as arestas como segue:
I) Arestas de Árvore (que fazem parte de uma árvore de busca em profundidade).
II) Arestas Diretas (que ligam um ancestral a um descendente).
III) Arestas de Retorno (que ligam um descendente a um ancestral).
IV) Arestas Cruzadas (as demais).

Mesmo sem saber a ordem em que alguns vértices serão visitados, pode-se ter certeza que o algoritmo encontrará durante o percurso, PELO MENOS:

1. 1 Aresta de Retorno e 2 Arestas Cruzadas
2. 1 Aresta Direta, 1 Aresta Cruzada e 1 Aresta de Retorno
3. 1 Aresta Cruzada e 2 Arestas de Retorno
4. 8 Arestas de Árvore
5. NDA

Ideia original de: Ewerton Almeida Silva