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. C32
  4. D12
2.Fácil

O que é um algoritmo?

  1. AUma linguagem de programação criada para escrever fórmulas matemáticas
  2. BQualquer programa de computador com interface gráfica
  3. CUma estrutura de dados que armazena números
  4. DUma sequência finita de passos bem definidos que resolve um problema
3.Fácil

Quanta memória extra usa um merge sort padrão baseado em arrays?

  1. AO(n)
  2. BO(n²)
  3. CO(1)
  4. DO(log n)
4.Média

Qual é a solução da recorrência T(n) = T(n/2) + O(1)?

  1. AO(log n)
  2. BO(n log n)
  3. CO(n)
  4. DO(1)
5.Média

Qual é a solução da recorrência T(n) = T(n − 1) + O(1)?

  1. AO(log n)
  2. BO(2ⁿ)
  3. CO(n)
  4. DO(n²)
6.Média

Qual é a solução da recorrência T(n) = 2T(n/2) + O(1)?

  1. AO(n log n)
  2. BO(n)
  3. CO(n²)
  4. DO(log n)
7.Difícil

O algoritmo de Strassen multiplica matrizes usando 7, em vez de 8, multiplicações recursivas de blocos de metade do tamanho. Qual é o seu tempo de execução?

  1. AΘ(nlog₂ 7), cerca de n2,81
  2. BΘ(n² log n)
  3. CΘ(n³)
  4. DΘ(n2)
8.Difícil

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

  1. An² = o(n)
  2. Bn = o(n²), mas n não é o(n)
  3. C2n = o(n), porque 2n cresce devagar
  4. Dn = o(n), já que toda função é o pequeno de si mesma

Gabarito

  1. 1. A · 10
  2. 2. D · Uma sequência finita de passos bem definidos que resolve um problema
  3. 3. A · O(n)
  4. 4. A · O(log n)
  5. 5. C · O(n)
  6. 6. B · O(n)
  7. 7. A · Θ(nlog₂ 7), cerca de n2,81
  8. 8. B · n = o(n²), mas n não é o(n)

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