MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-052

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, sem qualquer procedimento de balanceamento. Logo após, o nó com chave 6 é removido da árvore.

Qual a alternativa correta sobre a árvore resultante?

A) A árvore terá altura 3 e nó 8 terá profundidade 2;
B) A árvore terá altura 2 e nó 2 terá profundidade 1;
C) A árvore terá altura 3 e nó 5 terá profundidade 0;
D) A árvore terá altura 2 e nó 1 terá profundidade 1;
E) NDA

Ideia original de: Félix Carvalho Rodrigues

MO417 - Questão para a prova oral

Número: 2013-051

Enunciado: Em um grafo não orientado, com n vértices, determine a quantidade mínima e máxima, respectivamente, de arestas que pode haver para obtermos k componentes conexas.  Considere que não há mais de uma aresta entre dois vértices e que não há laços (um laço seria uma arestas com vértices idênticos nas extremidades).

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

Ideia original de: Jacqueline Midlej do Espírito Santo

MO417 - Questão para a prova oral

Número: 2013-046

Enunciado: Considere as seguintes cidades em uma árvore de busca binária, de altura 3:

Belém	Fortaleza	Recife
Belo Horizonte	Goiânia	Rio de Janeiro
Brasília	Guarulhos	Salvador
Campinas	Manaus	São Luís
Curitiba	Porto Alegre	São Paulo

 

Qual é a sequência correta de busca nesta árvore, se procuramos a cidade Natal?

1. Guarulhos, Campinas, Fortaleza, Goiânia.
2. Guarulhos, Rio de Janeiro, Porto Alegre, Manaus.
3. Guarulhos, Rio de Janeiro, Porto Alegre, Recife.
4. Guarulhos, Rio de Janeiro, São Luis, Salvador.
5. NDA 

Ideia original de: Julián Esteban Gutiérrez Posada

MO417 - Questão para a prova oral

Número: 2013-050

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. Qual das seguintes operações NÃO poderá ser realizada em tempo O(lg n) numa árvore assim?

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

Ideia original de:  René du Raymond Sacramento

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-049

Enunciado: Qual dos nós da árvore abaixo, se tiver o valor ou a cor alterados, faz com que a árvore obedeça todas as propriedades de uma árvore rubro-negra?

a) 4
b) 10
c) 12
d) 14
e) NDA

Ideia original de: Raphael Azzolini

MO417 - Questão para a prova oral

MO417 - Questão para a prova oral

Número: 2013-048

Enunciado: O seguinte algoritmo insere o nó z numa árvore binária de busca T.

TREE-INSERT(T,z)
1   y = NIL
2   x = T.root
3   while x <> NIL
4   y  = x
5 if z.key < y.key
6 x = x.left
7  else x = x.right
8   z.p = y
9   if y == NIL
10 T.root = z // tree T was empty
11 elseif z.key < y.key
12     y.left = z
13 else y.right = z

Depois de inserir os seguintes elementos (nessa ordem): 4, 6, 1, 2, 5, 9, 7 numa árvore vazia T, qual chave não fica numa folha de T?

a) 9
b) 7
c) 5
d) 2
e) NDA

Ideia original de: John Edgar Vargas Muñoz

MO417 - QUESTÃO PARA PROVA ORAL

Número: 2013-047


Enunciado: O conjunto de chaves { 3, 7, 5, 19, 18, 15, 25, 20, 10} exibe o percurso em pós-ordem de uma árvore de pesquisa binária. Qual alternativa exibe a chave e a altura ou profundidade correta de um nó desta árvore? Nota: a altura de um nó x é o número de arestas no caminho de x ao seu descendente mais distante; e a profundidade de um nó x é o número de arestas no caminho de x ao seu ascendente mais distante.

1. chave=7, profundidade=1
2. chave=15, altura=3
3. chave=19, profundidade=4
4. chave=20, altura=2
5. NDA.

Ideia original de: Laurindo de Sousa Britto Neto