eri

MO417 - Questão para a prova oral

Número:

Enunciado : Considere a representação de conjuntos disjuntos por listas ligadas abaixo e a definição de suas operações MAKE_SET, UNION e FIND_SET definidas a seguir.

• Inicio: ponteiro para o objeto inicial da lista;
• Fim: ponteiro para o objeto final da lista;
• Cada objeto da lista contém:
• Um elemento de conjunto;
• Um ponteiro para o objeto contendo o próximo elemento do conjunto.
• Este ponteiro do último objeto da lista apontará para NIL.

• MAKE_SET(x): cria um novo conjunto cujo único elemento (e representante do conjunto) é x;
• UNION(x,y): une os conjuntos que contêm x e y em um novo conjunto que é a união desses dois conjuntos. O representante do conjunto resultante é o representante do conjunto de y.
• FIND_SET(x): retorna um ponteiro para o representante que contêm x.

Nesse contexto, qual o tempo de execução no pior caso dos algoritmos para MAKE_SET, FIND_SET e UNION, respectivamente.

a)      Θ(1), Θ(1), Θ(n).

b)     Θ(1), Θ(n), Θ(n).

c)      Θ(n), Θ(1), Θ(n).

d)     Com os parâmetros definidos nas funções, é impossível fazer os três algoritmos da forma como foram definidos.

e)      N.D.A. 

Ideia original de:  Erick Aguiar Donato

ali

MO417 - Questão para a prova oral

Número:

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 fundamentais 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 II e III são verdadeiras
d) Somente as afirmações I e II são verdadeiras
e) NDE

Ideia original de: Alisson Linhares de Carvalho

dam

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Suponha uma implementação de conjuntos disjuntos com o uso de florestas, que ofereça os seguintes comandos:

1. Make-Set(x): cria um conjunto cujo único elemento é x;

2. Find-Set(x): retorna o elemento representante do conjunto de x, com o uso da heurística de path compression;

3. Union(x, y): unifica os conjuntos de x e de y, com o uso da heurística de union by rank (seu código segue abaixo).

Union(x, y) // mesma implem. de "Intro. to Algorithms" (Cormen et al., 3a ed)

1. e1 = Find-Set(x);

2. e2 = Find-Set(y);

3. if e1.rank > e2.rank

4.      e2.pai = e1;

5. else

6.      e1.pai = e2;

7.      if e1.rank == e2.rank;

8.           e2.rank = e2.rank + 1;

Selecione a árvore resultante da seguinte sequência de comandos, onde cada nó é rotulado com seu elemento x, e seu valor de rank r (<x, r>):

01. Make-Set(a);

02. Make-Set(b);

03. Make-Set(c);

04. Make-Set(d);

05. Make-Set(e);

06. Make-Set(f);

07. Make-Set(g);

08. Union(b, a);

09. Union(e, d);

10. Union(d, f);

11. Union(d, a);

12. Union(g, c);

13. Union(f, g);

a.   b.

c.        d.

e. N.D.A

Ideia original de: Daniel Henriques Moreira

jho

MO417 - Questão para a prova oral

Número: 

Enunciado: Sobre as representações para conjuntos disjuntos é correto afirmar que :

1. Na representação por listas ligadas é utilizada a heurística weighted-union onde a idéia é sempre concatenar a maior lista no final da menor.
2. Usando a representação por listas ligadas e a heurística weighted-union, uma sequência de m operações (MAKE-SET + UNION + FIND-SET) gasta tempo O(m + mlgm).
3. A representação por disjoint-set forest é uma melhoria assintótica em relação com a representação por listas ligadas, porque utiliza as heurísticas weighted-union e path compression.
4. A idéia da heurística path compression consiste em: ao tentar determinar o representante (raiz da árvore) de um nó fazemos com que todos os nós no caminho apontem para a raiz.
5. NDA.

Ideia original de: Jhon Anthony Campos Arteaga

hil

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Considere que as linhas abaixo representam os passos para construção de uma coleção de conjuntos disjuntos a partir de um grafo com dois componentes conectados:

Aresta processada	Coleção de conjuntos disjuntos
Conjuntos iniciais	{a}	{b}	{c}	{d}	{e}	{f}	{g}
Aresta 1	{a,b}		{c}	{d}	{e}	{f}	{g}
Aresta 2	{a,b,c}			{d}	{e}	{f}	{g}
Aresta 3	{a,b,c}			{d}	{e}	{f}	{g}
Aresta 4	{a,b,c,d}				{e}	{f}	{g}
Aresta 5	{a,b,c,d}				{e}	{f}	{g}
Aresta 6	{a,b,c,d}				{e}	{f}	{g}
Aresta 7	{a,b,c,d}				{e,f}		{g}
Aresta 8	{a,b,c,d}				{e,f,g}

A sequência de passos na ordem que aparece acima pode ter sido obtida a partir de qual dos grafos abaixo?

a)
b)
c)
d)
e)	N. D. A.

Ideia original de: Hilário Seibel Júnior

dac

MO417 - Questao para a prova oral 

Numero:

Enunciado:  Sobre a determinação de componentes conexos em um grafo não orientado e utilizando uma função MAKE-SET(xi) e UNION(xi, xj) em uma função para construção do grafo, sendo seus custos e número de operações, respectivamente, O(1) com n operações e O(n) com n - 1 operações. Quantos objetos serão atualizados na execução de UNION(x6, x7)?

a. 6

b. n-5

c. 3

d. n

e. NDA

Ideia original de: Danilo Carneiro

fel

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Suponha que a sequência de números 5,8,2,6,1,7 é inserida na ordem dada em uma árvore binária de busca A vazia. Logo após, o nó raiz é removido da árvore A.

Qual será a altura da árvore A e o nó com qual valor ficará como raiz?

A) A árvore A terá altura 3 e nó raiz com valor 5;
B) A árvore A terá altura 2 e nó raiz com valor 6;
C) A árvore A terá altura 3 e nó raiz com valor 7;
D) A árvore A terá altura 2 e nó raiz com valor 2;
E) NDA

Ideia original de: Félix Carvalho Rodrigues