jac

MO417 - Questão para a prova oral

Número:

Enunciado: Em uma representação de conjuntos disjuntos através de grafos não orientado, suponha que é dado um grafo com n vértices.
Determine a quantidade mínima e máxima, respectivamente, de arestas que o grafo pode possuir para obtermos k conjuntos disjuntos.
Considere que não há mais de uma aresta entre dois vértices e que não há laços, ou seja, arestas com vértices idênticos nas extremidades.

a) n-k  e (n-k+1)(n-k)/2
b) n e (n-k)²
c) n-k e n(n-1)/2
d) n+k e n^k
e) NDA

Ideia original de: Jacqueline Midlej do Espírito Santo

ade

MO417 - QUESTÃO PARA A PROVA ORAL


Número:


Enunciado: Cada alternativa abaixo (exceto a alternativa e) exibe um conjunto de chaves em percurso de pós-ordem de uma árvore. Qual das alternativas obedece a propriedade de árvore de pesquisa binária?

a) { 1, 4, 7, 5, 3, 9, 12, 18, 16, 11, 8 }
b) { 1, 4, 3, 5, 7, 9, 12, 18, 16, 11, 8 }
c) { 1, 4, 7, 5, 3, 9, 12, 11, 16, 18, 8 }
d) { 1, 4, 3, 5, 7, 9, 16, 18, 12, 11, 8 }
e) NDA



Ideia original de: Ademar Takeo Akabane

acw

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Um dicionário futebolístico é indexado através de uma árvore Vermelho-Preto, onde cada nó é um ponteiro para uma lista de palavras iniciadas com a mesma letra.
Antes de inserir uma palavra no dicionário, o sistema verifica se o nó com a chave correspondente já está na árvore, se não estiver ele usa o método RB-INSERT abaixo para incluí-lo.
Sabendo que foram inseridas apenas as seguintes palavras no dicionário (Na mesma ordem em que são apresentadas), responda: Qual das alternativas abaixo está correta?

Futebol - Liga - Atacante - Meia - Equipe - Número - Goleiro - Obstrução

RB-INSERT(T, z) 01  y = T.nil 02  x = T.root 03  while (x != T.nil) { 04     y = x 05     if (z.key < x.key) 06          x = x.left 07     else x = x.right 08  } 09  z.p = y 10  if (y == T.nil) 11  {  T.root  = z } 12  elseif (z.key < y.key) 13  {  y.left  = z } 14  else 15  {  y.right = z } 16  z.left  = T.nil 17  z.right = T.nil 18  z.color = RED 19  RB-INSERT-FIXUP(T, z)

RB-INSERT-FIXUP(T, z) 01 while (z.p.color == RED) { 02    if (z.p == z.p.p.left) { 03       y = z.p.p.right 04       if (y.color == RED) { 05          z.p.color = BLACK 06          y.color   = BLACK 07          z.p.p.color = RED 08          z = z.p.p 09       } else { 10          if (z == z.p.right) { 11             z =  z.p 12             LEFT-ROTATE(T, z) } 13          z.p.color = BLACK 14          z.p.p.color = RED 15          RIGHT-ROTATE(T, z.p.p) } 16    } else { 17    /* Código igual a cláusula "then" 18     com "right" e "left" trocados.*/ } 19 } 20 T.root.color = BLACK

a. A altura de preto dessa árvore é 3.
b. O número de nós internos na cor preta é superior aos de cor vermelha.
c. Os nós com as chaves "G", "O" e "L" possuem a mesma cor.
d. Os nós com as chaves "F", "L" e "A" ficaram em níveis diferentes.
e. NDA

Ideia original de: Anderson Coelho Weller

2013-04-26

kim

MO417 - Questão para a prova oral

Número:

Enunciado: Considerando a árvore de pesquisa binária, assinale a alternativa que contém as afirmativas corretas:

I - A propriedade de árvore de pesquisa binária é irrelevante para o correto funcionamento da consulta em uma árvore de pesquisa binária.

II - A propriedade de árvore de pesquisa binária permite imprimir todas as chaves em sequência ordenada.

III - O custo de uma consulta em uma árvore de pesquisa binária é sempre O(lg n).

IV - O tempo de execução do método SEARCH-TREE é Ω(lg n).

V - O método SEARCH-TREE poderia ser implementado de forma iterativa para diminuir o gasto de memória do algoritmo.

(a) I, II e IV.

(b) II, III e V.

(c) I, II e V.
(d) II, IV e V 

(e) N.D.A 

Idéia original de: Kim Pontes Braga

ren

MO417 - Questão para a prova oral

Número:

Enunciado: Árvores rubro-negras podem ser implementadas sem o apontador para o pai nos nós. Isso economiza ϴ(n) de espaço na estrutura de dados. Quais das seguintes operações NÃO poderão mais ser realizadas em tempo O(lg n) numa árvore dessas (uma outra pergunta, cuja a resposta é a mesma alternativa, seria: "qual das seguintes operações necessita construir uma pilha com os nós visitados para ser implementada numa árvore dessas". Pode apagar esta parte entre parêntesis se preferir. Acho que é uma questão muito difícil para ser perguntada de qualquer jeito.) :

a)  Inserção.
b)  Busca.
c)  Sucessor.
d)  Deleção.
e)  N.D.A.

Ideia original de:  René du Raymond Sacramento

vla

MO417 - QUESTÃO PARA A PROVA ORAL
Número:
Enunciado: Dado o algoritmo do TREE-SUCCESSOR(x):

TREE-SUCCESSOR(x)
1  if x.right ≠ NIL
2     return TREE-MINIMUM(x.right)
3  y=x.p
4  while y ≠ NIL and x==y.right
5       x=y
6       y=y.p
7  return y


TREE-MINIMUM(x)
1  while x.left ≠ NIL
2     x=x.left
3  return x


Que acontece quando as linhas 1,2 e 4 do TREE-SUCCESSOR(x) são substituídas por:
1: if x.left ≠ NIL
2:TREE-MINIMUM(x.left)
4:while y ≠ NIL and x==y.left

a. o algoritmo encontra o successor
b. o algoritmo encontra o predecessor
c. o algoritmo encontra o segundo sucessor
d. o algoritmo encontra o segundo predecessor
e. NDA

Ideia original de: Vladimir Jaime Rocca Layza