jun

MO417 - Questão para a prova oral

Numero:

Enunciado: Leia a seguintes afirmações e assinale a alternativa Correta

    I        Cada nó de uma árvore vermelho-preto tem atributo de cor, vermelho ou preto.

    II       Numa arvore vermelho-preto, todas as folhas (nil) são pretas.

    III     Numa arvore vermelho-preto, todos os filhos dos nós vermelhos são pretos.

   IV     Numa arvore vermelho-preto, todo caminho de um dado nó para qualquer de seus nós folhas descendentes contem o mesmo número de nós vermelhos.

    V       Numa arvore vermelho-preto, a raiz é vermelha.

  
Qual é a alternativa correta:

a) Somente I , II , III e IV são corretas

b) Somente I , II e III são corretas

c) Somente I , II , III , IV e V são corretas

d) Somente I , IV são corretas

e) NDA

                                             Ideia original de: Junior Cupe Casquina

osv

MO417 - Questão para prova oral

April 19th, 2013 · osvaldo · Exercises (MO417) No comments

Número:
Enunciado: Suponha a existência de uma red-black BST qualquer e assinale qual a altura resultante desta árvore, em função do número de elementos n, após a inserção do conjunto X = {1,50, 201, 328, 543, 702}.
a. n
b. log(n)

c. nlog(n)

d. 2n
e. NDA

Idéia original de: Osvaldo Andrade Neto

ota

MO417 - Questão para a prova oral
Numero:

Bob e Alice gostariam de troca mensagens entre eles sem que outras pessoas soubessem, assim eles estipularam o seguinte protocolo:
1. Converter toda a mensagem em representação numérica, ex: letra "A" se transforma 42.
2. Insere todas os números em uma árvore Red/Black
3. Definem em segredo qual número será a raiz e um caminhamento para a leitura desta árvore.

Desta forma, Bob envia para Alice o caminhamento pós-ordem da árvore, entretanto a mensagem, que nunca contém letras repetidas, só pode ser entendida caso seja feito o caminhamento inter-ordem para os nós a esquerda da raiz e pre-ordem para os nós a direita da raiz.  


Em relação a uma algoritmo que implementaria essa pequena confusão na mensagem, é correto afirmar.

I. Só seria atingido o balanceamento ótimo da árvore caso a mensagem fosse ordenada, com o elemento na posição mediana sendo a raiz.
II. Custo de realizar todos os três caminhamentos na árvore será sempre o mesmo independente do balanceamento da árvore.
III. A mensagem {12,9,47,27,11,5} é válida para Bob e Alice
IV.  Caso Bob enviasse  [a,b...z], para Alice, todas as varreduras resultariam na mesma mensagem, dado que a arvore seria uma "tripa", ou com todos os nós a direta do pai.


a. I e III 
b. II e IV
c. I e IV
d. II
e. N.D.A 
 

Ideia original de: Otávio Augusto Araújo Silva

mps

MO417 - Questão para a prova oral

Número:

Merlin, um especialista do Pôquer, deseja ensinar a Arturo sobre o uso das árvores binárias. Lembrando-se do seu intenso treinamento em Algortimos, utiliza um maço de 52 cartas, organizadas em quatro naipes (paus, copas, espadas, corações) e cada naipe organizado em uma árvore binaria. O Mago pede a Arturo para encontrar a carta 9 em cada naipe. Qual dos naipes a seguir não poderia ser uma sequencia de cartas examinadas corretamente?

a) Paus: 2, K, 4, 10, 5, 9
b) Copas: Q, 2, 4, J, 3, 9
c) Espadas: 3, K, 6, Q, 8, 9
d) Corações: K, A, 10, 3, 5, 9
e) NDA

NOTA: A = 1, J = 10, Q =11, K = 13.

Ideia original de: Marcelo Palma Salas

she

MO417- QUESTÃO PARA A PROVA ORAL
Número: 
Enunciado: 

Sejam os conjuntos:

A={26, 30,50}

B={18,20,24}

C={13,10,6}

Se você insere os elementos desses conjuntos numa árvore de busca binaria no seguinte ordem: os elementos dos conjuntos A,C e B, é correto afirmar que:

a) A árvore resultante é balanceado

b)A altura da subárvore esquerda da raiz é maior da que a subárvore direita

c) A visita em pós-ordem dos nós é 6,10,18,20,24,13,50,30,26

d) A altura máxima da árvore é 4

e) NDA

Ideia original de: Sheila Katherine Venero Ferro

mar

MO417 - Questão para a prova oral

Número:

Enunciado: Seja a seguinte árvore vermelho e preto :

Depois de inserir o número 3 na árvore, indique a resposta CORRETA:


a) O nó 7 é preto e seu pai é o nó 13
b) O nó 2 é vermelho e não tem filho esquerdo
c) O nó 4 é preto e seu filho esquerdo é o nó 3
d) O nó 13 é a raiz e seu filho esquerdo é o nó 14
e) NDA

Idéia original de: Marleny Luque Carbajal

tha

MO417 - Questão para a prova oral

Número:

Enunciado: Em uma implementação de cache têm-se um espaço fixo que permite armazenar pares compostos por (valor, numero_de_acessos).  Existem algumas restrições quanto à implementação dessa cache:

1. deve sempre conter os elementos mais acessados
2. o tempo para encontrar um elemento qualquer e o tempo para encontrar outro elemento qualquer devem ser os mais próximos possíveis
3. o tempo para encontrar um elemento e o tempo para descobrir se um elemento não se encontra na cache devem ser os mais próximos possíveis
4. periodicamente os elementos menos acessados devem ser descartados, sendo que a eficiência para encontrar esses elementos nao é prioritária em relação aos outros requisitos

Qual é a melhor estrutura de dados a ser utilizada para representar essa cache?

A) Vetor ordenado crescentemente em função do número de acessos.
B) Árvore binária balanceada ordenada pelo número de acessos.
C) Árvore binária balanceada ordenada pelo valor.
D)Vetor ordenado decrescentemente em função do número de acessos.
E) N.D.A

Ideia original de: Thaís Harumi Ussami