Resumêra

Questão 1 (nível médio) - Qual afirmação descreve corretamente uma BST?

1.50 Médio

A) Em uma BST, valores à esquerda são sempre maiores que o nó. B) Em uma BST, para todo nó, valores da esquerda são menores que o nó e valores da direita são maiores. C) BST não permite inserção de novos valores. D) Em BST, todos os nós internos são folhas. E) BST garante ordenação apenas para números inteiros.

Resposta correta: B) Em uma BST, para todo nó, valores da esquerda são menores que o nó e valores da direita são maiores.

Observação: essa propriedade permite buscas eficientes, já que cada comparação reduz a área de pesquisa pela metade em média.

Questão 2 (difícil) - Limite de comparações para ordenar por comparação

2.50 Difícil

Qual é o limiar teórico de menor número de comparações necessárias, em pior caso, para ordenar n elementos por meio de comparações entre pares?

A) O(n) B) O(n log n) C) O(n^2) D) log2(n!) E) 2^n

Resposta correta: D) log2(n!)

Justificativa: existem n! permutações possíveis; cada comparação pode dividir o espaço de possibilidades pela metade em média, levando a um limite inferior de ~ log2(n!).

Questão 3 (difícil) - Altura de BST com uma sequência específica

2.50 Difícil

Considere a inserção dos valores na ordem: 5, 8, 2, 12, 14, 10, 9 em uma BST. Qual é a altura da árvore resultante?

A) 2 B) 3 C) 4 D) 5 E) 6

Resposta correta: C) 4

Explicação: seguindo a ordem de inserção, a BST resultante terá altura 4 (níveis 0 a 3); a distribuição apresentada no enunciado demonstra essa altura.

Questão 4 (extremamente difícil) - Limite inferior para ordenação por comparação

3.50 Extrema

Em ordenação por comparação, qual é o limite inferior teórico para a altura de um diagrama de decisão que ordena n elementos?

A) n B) log2(n!) C) n log2 n D) n^2 E) 2^n

Resposta correta: B) log2(n!)

Justificativa: como existem n! permutações, o espaço de decisões exige no mínimo log2(n!) passos para distinguir todas as ordenações possíveis.

Árvore de decisão: busca binária e ordenação

Questões sobre o assunto