MO417 - Questão para a prova oral

Número: 2013-079

Enunciado: É dado o seguinte grafo direcionado com pesos descrito por uma matriz de adjacências, em que uma entrada (i,j) diferente de 0 na matriz significa que há uma aresta de i para j.

   a  b  c  d

a| 0 -5 -3  0

b| 5  3  1  2

c| 4 -1  0  1

d| 0  0  2  0

Quais são, respectivamente, as distâncias entre o vértice inicial a e o final d, e entre o inicial d e o final a?

a)  -5 e -3
b)  -3 e 6
c)  -4 e -3
d)  -1 e -6
e)  N.D.A.

Ideia original de:  René du Raymond Sacramento

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-078

Enunciado: Seja G o grafo com 5 nós e 7 arestas abaixo.

Para que valores dos pesos de arestas a, b e c (podendo ser negativos) o algoritmo de Dijkstra executado em G tendo o nó 1 como origem retorna distâncias corretas para todos os vértices?

A) a = 14, b = -6, c = 8;
B) a = 12, b = -4, c = 1;
C) a = 8, b = -5, c = 5;
D) a = 5, b = -6, c = 10;
E) NDA

Ideia original de: Félix Carvalho Rodrigues

MO417- QUESTÃO PARA A PROVA ORAL

Número: 2013-077

Enunciado: É preciso conectar um conjunto de computadores entre si com cabos de rede, de modo que de cada um haja um caminho para qualquer outro.  Só se pode conectar um computador diretamente a outro, sem usar dispositivos intermediários.  No grafo a seguir estão representados os computadores como vértices e as distancias em metros que um cabo deve percorrer entre dois computadores, como arestas. Note que nem todos os pares de computadores podem ser conectados diretamente.  Indique qual seria o custo mínimo em reais para conectá-los, levando em conta que cada metro de cabo custa 1.5 reais.

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

Ideia original de: Sheila Katherine Venero Ferro

MO417 - Questão para a prova oral

Número: 2013-076

Enunciado: Considere o seguinte grafo não orientado ponderado e responda corretamente:

Qual das seguintes arestas pode ser parte de alguma das possíveis árvores espalhadas mínimas:

a) (f,g)

b) (b,d)

c) (b,c)

d) (a,b)

e) NDA

Ideia original de: Marleny Luque Carbajal

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-075

Enunciado: Dado o grafo abaixo, qual das alternativas apresenta o vértice com distância (d) e pai (p) corretos para uma árvore de caminhos mínimos enraizada no vértice a?

a) b: d = 3, p = a
b) c: d = 7, p = f
c) d: d = 8, p = c
d) e: d = 10, p = d
e) NDA

Ideia original de: Raphael Azzolini

MO417 - Questão para a prova oral

Número: 2013-074

Enunciado: Sobre o algoritmo de caminhos mínimos de Dijkstra, qual das alternativas abaixo está correta?

a. O algoritmo pode ser considerado como um algoritmo guloso
b. Dijkstra encontra os caminhos mais curtos mesmo com arestas de peso negativo, desde que não haja ciclos negativos
c. O algoritmo funciona apenas se não houver ciclos, ou seja, se o grafo de entrada for um DAG (Directed Acyclic Graph)
d. O algoritmo relaxa cada aresta duas vezes
e. NDA

Ideia original de: Jorge Augusto Hongo

MO417 - Questão para a prova oral

Número: 2013-073

Enunciado: O seguinte grafo mostra o tempo em minutos para viajar entre 8 cidades.

Assinale a alternativa correta:

a) O tempo mínimo para viajar de A a H é 38
b) O tempo mínimo para viajar de A a F é 25
c) A aresta (E,F) pertence ao caminho que tem o tempo mínimo para viajar de A a H
d) A aresta (B,D) pertence ao caminho que tem o tempo mínimo para viajar de A a H
e) NDA

Ideia original de: John Edgar Vargas Muñoz

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-072

Enunciado: Considere o seguinte tabuleiro 3x4 onde cada quadrado contém um número de pontos:

Imagine agora um jogo jogado neste tabuleiro, em que o objetivo consiste em deslocar sua peça do canto superior esquerdo até o canto inferior direito, através de uma sequência de movimentos para a direita ou para baixo, de forma de minimizar o somatório dos pontos correspondentes aos quadrados pelos quais você passou.  O jogo pode ser descrito como um problema de caminhos mínimos no grafo mostrado na figura abaixo:

Nestas condições, ao resolvermos o problema, quantos quadrados com número par de pontos NÃO estarão no caminho ótimo ?

(a) 2

(b) 3

(c) 4

(d) 5

(e) NDA

Ideia original de: Lucas Miguel de Carvalho

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

Enunciado: Dada a matriz de adjacências descrita abaixo, onde M[i,j] corresponde ao peso da ligação e o valor 0 a ausência de aresta, responda:

	A	B	C	D	E
A	0	1	2	0	0
B	1	0	0	2	5
C	2	0	0	0	7
D	0	2	0	0	4
E	0	5	7	4	0

Qual das alternativas abaixo corresponde, respectivamente, ao somatório dos pesos da árvore geradora mínima e da máxima?

1. 7, 14
2. 9, 18
3. 9, 21
4. 10, 13
5. NDA

Ideia original de: Alisson Linhares de Carvalho

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

Enunciado: Seja G o grafo com 5 nós e 7 arestas abaixo. É gerado uma minimum spanning tree T de G.

Qual a ordem de inserção das arestas em T se utilizarmos o algoritmo de Kruskal para gerar T? E qual será a ordem se utilizarmos o algoritmo de Prim, utilizando o vértice a como origem, para montar T?

A) Para o alg. Kruskal: (c,e), (b,e), (a,b), (a,e), para o alg. Prim: (a,b), (b,e), (c,e), (a,e);
B) Para o alg. Kruskal: (c,e), (b,e), (a,b), (d,e), para o alg. Prim: (a,b), (a,e), (b,c), (d,e);
C) Para o alg. Kruskal: (c,e), (b,e), (a,b), (d,e), para o alg. Prim: (a,b), (b,e), (c,e), (d,e);
D) Para o alg. Kruskal: (d,e), (a,b), (b,e), (c,e), para o alg. Prim: (a,b), (b,e), (c,e), (d,e);
E) NDA

Obs: as arestas não são direcionadas, dessa forma, para uma aresta e entre x e y, tanto (x,y) quanto (y,x) podem ser utilizados para representar e.

Ideia original de: Félix Carvalho Rodrigues

MO417 - Questão para a prova oral

Número: 2013-063

Enunciado: Dois grafos direcionados são dados a seguir, um representado por lista de adjacências e outro por matriz de adjacências.  Lembre-se que uma entrada (i,j) igual a 1 na matriz significa que há uma aresta de i para j.

Grafo A:

1: 2, 3

2: 4

3: 2, 5

4: 1, 2, 3

5: 2

Grafo B:

   1  2  3  4

1| 0  0  0  0

2| 1  0  0  0

3| 1  1  0  1

4| 0  1  1  0

Quais das seguintes afirmações sobre os graus de saída e entrada dos vértices destes grafos é verdadeira?  Elas estão no formato: GrafoVértice: (grau de SAÍDA, grau de ENTRADA).

 I  - A1: (2,1),  B2: (2,2)

II  - A2: (1,4),  B1: (0,2)

III - A4: (1,3),  B3: (3,1)

a)  I e II
b)  I, II e III
c)  Apenas a II
d)  Apenas a III
e)  N.D.A.

Ideia original de:  René du Raymond Sacramento

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

Enunciado: Execute uma busca em largura com o grafo representado pela seguinte matriz de adjacência e iniciando a partir do vértice "a".  Suponha que os vizinhos de um vértice são analisados em ordem alfabética.

	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.π=b, d.π=a, 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.π=d, d.π=f, e.π=a, f.π=d
e) NDA

Ideia original de: Sheila Katherine Venero Ferro

MO417 - Questão para a prova oral

Número: 2013-059

Enunciado: Uma das seguintes listas de adjacências representa um grafo não orientado G=(V,E) com cinco arestas e quatro vértices: a, b, c, d. Analise as representações e indique a alternativa CORRETA:

a) A representação I de G=(V,E) é correta e a soma dos comprimentos de todas as listas de adjacências é 2|E|
b) A representação II de G=(V,E) é correta e a soma dos comprimentos de todas as listas de adjacências é |E|
c) A representação II de G=(V,E) é correta e a quantidade de memória que ela exige é Θ(V+E)
d) A representação III de G=(V,E) é correta e a quantidade de memória que ela exige é Θ(V+E)
e) NDA

Ideia original de: Marleny Luque Carbajal

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

MO417 - Questão para a prova oral

Número: 2010-062

Enunciado: Dado um grafo G = (V,E) e o vértice de origem x, qual árvore de busca em largura seria possível:

A.	B.	C.	D.
E. NDA

Ideia original de: Fabian van ´t Hooft

MO417 - Questão para a prova oral

Número: 2010-061

Enunciado: Qual alternativa mostra a altura máxima de uma árvore com n elementos em uma floresta de conjuntos disjuntos que utiliza apenas a heurística de união por posto ?  Considere que a altura de uma árvore com um único elemento é 0 (zero).

1. 2
   
2. ⌊lg n⌋
   
3. ⌊n/2⌋
   
4. n - 1
   
5. NDA
   

Ideia original de: Pedro Henrique Del Bianco Hokama

MO417 - Questão para a prova oral

Número: 2010-060

Enunciado: Considere o algoritmo de busca em largura em grafos. Dado o grafo a seguir, representado através da matriz de adjacências, e o vértice F como ponto de partida, uma das possíveis ordens em que os vértices são descobertos é dada por:

	A	B	C	D	E	F
A	0	1	1	0	0	0
B	1	0	0	1	0	0
C	1	0	0	1	1	0
D	0	1	1	0	1	1
E	0	0	1	1	0	1
F	0	0	0	1	1	0

1. F E D B C A
   
2. F D C E A B
   
3. F E D C B A
   
4. F E C D B A
   
5. NDA
   

Ideia original de: Thiago Augusto Lopes Genez

MO417 - Questão para a prova oral

Número: 2009-114

Enunciado: Sobre florestas de conjuntos disjuntos com heurísticas de união por posto e compressão de caminho é correto afirmar que:

1. A compressão de caminhos não altera o posto dos nós.
2. Na operação de união de conjuntos as raízes se conectam, tornando-se o pai a raiz da árvore de maior altura.
3. Após a operação de encontrar o representante do conjunto de um dado elemento, as folhas ficam todas no mesmo nível.
4. O tempo de execução da operação de criação de um conjunto com um elemento é ϴ(α(n)), onde α(n) é a inversa da função de Ackerman e n é o número total de elementos na estrutura.
5. NDA

Ideia original de: Milton Aparecido Soares Junior

MO417 - Questão para a prova oral

Número: 2009-110

Enunciado:

Dentre as operações que se pode realizar com conjuntos disjuntos, está a operação de UNION (x,y), em que se une o conjunto que contém x com o conjunto que contém y, e a operação FIND-SET(x), que retorna um ponteiro para o representante do conjunto que contém x. Utilizando a heurística de união por posto e a heurística de compressão de caminho, foram obtidas as duas árvores abaixo, que representam dois conjuntos disjuntos. A árvore da esquerda representa o conjunto disjunto {a, b, c, d} e a árvore da direita o conjunto disjunto {e, f}. A partir deste estado, foram realizadas as seguintes operações em sequência: UNION (d, f); FIND-SET (f); Assinale a alternativa que contém a resposta correta às seguintes duas perguntas: I. Qual a altura da árvore resultante após todas as operações? II. A operação FIND-SET( f ) retornou um ponteiro para qual nó?

1. I = 1, II = a
2. I = 1, II = e
3. I = 2, II = a
4. I = 2, II = e
5. NDA

Ideia original de: Paulo Gurgel Pinheiro

MO417 - Questão para a prova oral

Número: 2009-108

Enunciado: Sobre representação computacional de grafos, é INCORRETO afirmar que:

1. A representação por listas de adjacências tem a propriedade de que a quantidade de memória que ela exige é Θ(V+E), onde V é o numero de vértices e E o número de arestas. Todavia, esta propriedade só é válida para grafos não orientados.
   
2. A representação de grafos por listas de adjacências é vantajosa quando aplicada em grafos esparsos (número de arestas muito menor que o número de vértices ao quadrado), pois oferece uma representação compacta para esse tipo de grafo.
   
3. A representação de grafos por matriz de adjacências traz vantagens quando o grafo é denso (número de arestas próximo ao número de vértices ao quadrado) ou quando precisamos saber com rapidez se existe uma aresta conectando dois vértices dados.
   
4. A matriz de adjacências de um grafo não orientado é sempre igual à sua própria transposta (matriz simétrica). Desta forma, em algumas aplicações, pode compensar armazenar apenas as entradas contidas na diagonal e acima da diagonal da matriz, reduzindo assim quase pela metade a memória necessária para armazenar o grafo.
   
5. NDA

Ideia original de: Renato Hirata

MO417 - Questão para a prova oral

Número: 2009-107

Enunciado: Considerando as árvores apresentadas abaixo, indique quais delas representam uma possível floresta de conjuntos disjuntos com heurística de união por ordenação e compressão de caminho.

I.

II.

III.

1. I e II
2. I, II e III
3. II
4. II e III
5. NDA

Ideia original de: Gabriel de Souza Fedel

MO417 - Questão para a prova oral

Número: 2003-138

Enunciado: Indique a quantidade de memória exigida para representarmos um grafo G=(V,E), como “listas de adjacências” e como uma “matriz de adjacências”, respectivamente

1. Θ(V + E) e Θ(V²);
2. Θ(V²) e Θ(V + E);
3. Θ(V + E) e Θ(V + E);
4. Θ(V²) e Θ(V²);
5. n.d.a.

Ideia original de: Carlos Senna

MO417 - Questão para a prova oral

Número: 2003-135

Enunciado: Em relação ao algoritmo tradicional conhecido como BFS (Breadth-First Search, ou Busca em Largura) em grafos, é CORRETO afirmar que:

A) O mesmo algoritmo pode ser usado quer o grafo de entrada seja representado com listas de adjacências ou com uma matriz de adjacências.
 
B) O algoritmo é executado em tempo linear no tamanho da representação com listas de adjacências.
 
C) Independentemente da ordem na qual os vizinhos de um determinado vértice são visitados, o resultado da busca em largura é sempre o mesmo, ou seja, a árvore gerada é sempre a mesma.
 
D) Um dos resultados do algoritmo é o número de arestas de um caminho mais longo desde o vértice origem s até um vértice qualquer v.
 
E) N.D.A.

Ideia original de: Marcelo Fantinato

MO417 - Questão para a prova oral

Número: 2003-134

Enunciado: Considere uma estrutura que representa conjuntos disjuntos através de árvores. Seja A uma árvore que implementa esta estrutura e um nó x de A diferente da raiz. Imediatamente após a execução de uma operação FIND-SET(x) (busca para encontrar o representante do conjunto a que pertence x), e considerando que esta operação realiza a heurística de compressão de caminhos, é correto afirmar que

A) Todos os nós que são filhos de x na árvore antes deste FIND-SET passarão a apontar diretamente para o nó raiz de A.

B) Se x é um nó que possui filhos antes do FIND-SET, ele deixará de tê-los, pois passsará a ser um nó folha.

C) Se antes do FIND-SET o elemento p é pai de x e p não é a raiz de A, então os filhos de x passam a ser filhos de p.

D) Se antes do FIND-SET o elemento p é pai de x e p não é a raiz de A, então x deixará de ser filho de p.

E) NDA

Ideia original de: André Santanchè

MO417 - Questão para a prova oral

Número: 2013-056

Enunciado: Dado o conjunto A = {x1, x2, x3, x4, x5, x6}, e os seguintes algoritmos:

MAKE-SET(x) 1    x.p = x 2    x.rank = 0		UNION(x, y) 1    LINK(FIND-SET(x), FIND-SET(y))
FIND-SET(x) 1   if x ≠ x.p 2       x.p = FIND-SET(x.p) 3   return x.p		LINK(x, y) 1    if x.rank > y.rank 2       y.p = x 3   else x.p = y 4        if x.rank == y.rank 5        y.rank = y.rank + 1

O valor rank de cada um dos elementos de A depois das seguintes operações (nesta mesma ordem): MAKE-SET(xi) para i=1:6 ; UNION(x1, x5); UNION(x3, x4); UNION(x2, x6); UNION(x1, x2); UNION(x3, x1); é?

a) x1=1, x2=0, x3=1, x4=0, x5=2, x6=0

b) x1=0, x2=0, x3=0, x4=1, x5=1, x6=2

c) x1=0, x2=0, x3=0, x4=2, x5=1, x6=1

d) x1=1, x2=2, x3=1, x4=0, x5=0, x6=1

e) NDA.



Ideia original de: Carlos Eduardo Alfaro Morales

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-055

Enunciado: Considerando uma árvore rubro-negra com n chaves, quais das afirmativas abaixo são verdadeiras ?

I. Uma busca percorre no máximo 2(lg n) nós.
II. Se n=300, pode haver 200 nós vermelhos na árvore.
III. A árvore não pode ser constituída apenas por nós pretos.

1. Apenas I
2. Apenas II
3. I e II
4. II e III
5. NDA

MO417 - Questão para a prova oral

Número: 2013-054

Enunciado: Considere as operações sobre conjuntos disjuntos e um cenário no qual MAKE-SET é executado n vezes e depois UNION é executado m vezes, sendo cada operação UNION sobre conjutos A e A tais que A ≠ B. Se k é o número de conjuntos resultantes, assinale a alternativa válida para todas as possíveis combinações de n, m e k:

a) n > k +m
b) k = n!/m!(n-m)!
c) Se m = n/2, então k = m
d) Se k = 2m, então n é par
e) NDA

Ideia original de: Anderson Carlos Sousa e Santos

MO417 - Questão para a prova oral

Número: 2013-053

Enunciado: Dada a árvore vermelho-preta acima, devidamente colorida e balanceada, suponha a inserção do elemento 28. Lembrando que o novo nó, por padrão, é sempre vermelho e após a inserção poderá ser recolorido, buscando não violar as propriedades da árvore, quais das alternativas abaixo são verdadeiras?

I. A altura da árvore, após a inserção do nó 28, será 4.
II. A altura preta da árvore, antes da inserção do nó 28, é 3.
III. A impressão em pré-ordem, após a inserção do nó 28, será [25,11,6,19,14,37,28,42]

a) Todas as afirmações são verdadeiras.
b) Somente as afirmações I e III são verdadeiras
c) Somente as afirmações I e II são verdadeiras
d) Somente as afirmações II e III são verdadeiras
e) NDE

Ideia original de: Alisson Linhares de Carvalho