1.Fácil
O que é um algoritmo?
- AQualquer programa de computador com interface gráfica
- BUma linguagem de programação criada para escrever fórmulas matemáticas
- CUma sequência finita de passos bem definidos que resolve um problema
- DUma estrutura de dados que armazena números
2.Fácil
Um laço começa com i = 1 e dobra i a cada iteração até i > n. Quantas iterações ele executa?
- ACerca de n / 2
- BCerca de n
- CCerca de log₂ n
- DCerca de n²
3.Fácil
Um algoritmo com dois laços aninhados, cada um executado n vezes, normalmente tem qual complexidade?
- AO(n²)
- BO(n)
- CO(log n)
- DO(2n)
4.Média
A complexidade de tempo do Fibonacci recursivo ingênuo (fib(n) = fib(n−1) + fib(n−2)) é:
- AConstante
- BLogarítmica
- CExponencial
- DLinear
5.Média
Qual é o tempo de execução do radix sort LSD para n inteiros com d dígitos na base k?
- AO(n²)
- BO(dn log k)
- CO(n log n)
- DO(d(n + k))
6.Média
Qual é a solução da recorrência T(n) = 2T(n/2) + O(1)?
- AO(n)
- BO(log n)
- CO(n log n)
- DO(n²)
7.Difícil
A ordenação topológica só é possível para:
- AGrafos não dirigidos
- BGrafos acíclicos dirigidos (DAG)
- CGrafos com pesos negativos
- DGrafos completos
8.Difícil
O algoritmo de programação dinâmica de Held–Karp resolve o problema do caixeiro-viajante de forma exata. Qual é o seu tempo de execução para n cidades?
- AO(n!)
- BO(n² 2ⁿ)
- CO(n³)
- DO(2n²)
Gabarito
- 1. C · Uma sequência finita de passos bem definidos que resolve um problema
- 2. C · Cerca de log₂ n
- 3. A · O(n²)
- 4. C · Exponencial
- 5. D · O(d(n + k))
- 6. A · O(n)
- 7. B · Grafos acíclicos dirigidos (DAG)
- 8. B · O(n² 2ⁿ)
Soluções completas passo a passo: pratique este tópico em examproblems.com.