Lista de exercícios de Algoritmos e complexidade com respostas

O que a busca binária exige da sua entrada?

1. AO array não pode ter mais de 1000 elementos
2. BO array deve conter só números positivos
3. CO array deve estar ordenado
4. DO tamanho do array deve ser uma potência de dois

Um laço começa com i = 1 e dobra i a cada iteração até i > n. Quantas iterações ele executa?

1. ACerca de n²
2. BCerca de n / 2
3. CCerca de n
4. DCerca de log₂ n

Como funciona o selection sort?

1. ATroca repetidamente elementos vizinhos que estão na ordem errada
2. BDivide o array em metades e as intercala
3. CEncontra repetidamente o mínimo da parte não ordenada e o troca para a frente
4. DInsere cada elemento numa parte ordenada crescente por deslocamento

Aproximadamente quantas comparações a busca binária precisa no pior caso num array ordenado de 1,000,000 de elementos?

1. ACerca de 1,000
2. BCerca de 100
3. CCerca de 20
4. DCerca de 500,000

A complexidade de tempo do Fibonacci recursivo ingênuo (fib(n) = fib(n−1) + fib(n−2)) é:

1. ALinear
2. BLogarítmica
3. CConstante
4. DExponencial

Qual afirmação sobre uma função recursiva sem caso base alcançável está correta?

1. AEla continua chamando a si mesma até a pilha de chamadas estourar
2. BO compilador sempre a transforma em um laço que termina com segurança
3. CEla retorna 0 automaticamente
4. DEla roda em tempo O(1)

O insertion sort roda em O(n) com entrada ordenada. Isso contradiz o limite inferior Ω(n log n) da ordenação por comparação?

1. ANão, porque o insertion sort não é uma ordenação por comparação
2. BSim, mas só para arrays com menos de 100 elementos
3. CSim, portanto o limite inferior está errado
4. DNão, o limite inferior vale para o pior caso entre todas as entradas, não para cada entrada

Por que a busca média em uma tabela hash é O(1), mas o pior caso é O(n)?

1. AMuitas chaves podem colidir no mesmo bucket
2. BAs chaves precisam ser ordenadas primeiro
3. CFunções hash são lentas
4. DArrays têm acesso O(n)