MO417 - Questão para a prova oral

Número:

Enunciado: O seguinte algoritmo insere o nó z numa árvore T.

TREE-INSERT(T,z)
1   y = NIL
2   x = T.root
3   while x <> NIL
4   y  = x
5 if z.key < x.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 não é uma folha de T?

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

Ideia original de: John Edgar Vargas Muñoz

MO417 - Questão para a prova oral

Número:

Enunciado: Um palindromo é qualquer sequência que é exatamente o mesmo que sua reversão, por exemplo ARA ou RACECAR. Qual é o ordem do tempo de execução de um algoritmo que utiliza programação dinámica que retorna o comprimento da maior subsequência palíndroma de uma sequência de n elementos.

a) O(n³)
b) Θ(n³)
c) O(n²)
d) O(n)
e) NDA



Ideia original de: John Edgar Vargas Muñoz