Lista de exercícios de Algoritmos e complexidade com respostas

Lista de exercícios de Algoritmos e complexidade grátis para imprimir: 8 exercícios do nível fácil ao nível de prova, com gabarito. Imprima ou salve como PDF.

Nova lista de exercíciosPratique on-line com dicas

Para professores: pode imprimir, copiar e usar em aula gratuitamente. Cada nova folha tem novos valores e o seu próprio gabarito. Agradecemos um link para o ExamProblems na página da sua disciplina.

Nome: ____________________   Data: ____________

1.Fácil

Quanto é log₂ 1024?

  1. A10
  2. B512
  3. C12
  4. D32
2.Fácil

Qual notação descreve um limite superior de crescimento?

  1. AO grande (Big O)
  2. BTheta grande (Big Theta)
  3. CÔmega grande (Big Omega)
  4. DÔmega pequeno (little omega)
3.Fácil

Qual destes tempos de execução é polinomial?

  1. AO(nⁿ)
  2. BO(n!)
  3. CO(n³)
  4. DO(2ⁿ)
4.Média

No problema de seleção de atividades, qual regra gulosa sempre dá o número máximo de atividades sem sobreposição?

  1. AEscolher a atividade que termina mais cedo e repetir com as compatíveis
  2. BEscolher primeiro a atividade com menos sobreposições e repetir com as compatíveis
  3. CEscolher primeiro a atividade mais curta
  4. DEscolher a atividade que começa mais cedo
5.Média

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

  1. AExponencial
  2. BLinear
  3. CConstante
  4. DLogarítmica
6.Média

O limite inferior para ordenação baseada em comparações no pior caso é:

  1. AΩ(n²)
  2. BΩ(log n)
  3. CΩ(n)
  4. DΩ(n log n)
7.Difícil

Qual afirmação sobre a notação o pequeno está correta?

  1. An = o(n), já que toda função é o pequeno de si mesma
  2. B2n = o(n), porque 2n cresce devagar
  3. Cn² = o(n)
  4. Dn = o(n²), mas n não é o(n)
8.Difícil

Por que a busca binária não dá tempo O(log n) numa lista simplesmente encadeada?

  1. AChegar ao elemento do meio leva O(n) passos, pois não há acesso direto por índice
  2. BAs comparações entre nós de lista encadeada são mais lentas
  3. CListas encadeadas não podem ser ordenadas
  4. DA busca binária precisa de pelo menos o dobro da memória

Gabarito

  1. 1. A · 10
  2. 2. A · O grande (Big O)
  3. 3. C · O(n³)
  4. 4. A · Escolher a atividade que termina mais cedo e repetir com as compatíveis
  5. 5. A · Exponencial
  6. 6. D · Ω(n log n)
  7. 7. D · n = o(n²), mas n não é o(n)
  8. 8. A · Chegar ao elemento do meio leva O(n) passos, pois não há acesso direto por índice

Soluções completas passo a passo: pratique este tópico em examproblems.com.