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