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

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

  1. AO(n²)
  2. BO(1)
  3. CO(log n)
  4. DO(n)
2.Fácil

O que descreve o tempo de execução no caso médio?

  1. AO valor intermediário entre os tempos de execução do melhor e do pior caso
  2. BO tempo no computador mais comum
  3. CO tempo esperado sobre uma dada distribuição de entradas de tamanho n
  4. DO tempo para uma entrada de comprimento médio
3.Fácil

O que significa uma operação rodar em tempo O(1)?

  1. ASempre leva exatamente um segundo
  2. BSeu tempo de execução não cresce com o tamanho da entrada
  3. CSó pode ser executada uma vez
  4. DProcessa exatamente um elemento por segundo de tempo de execução
4.Média

Por que a programação dinâmica não traz ganho real de velocidade para o merge sort?

  1. ASeus subproblemas não se sobrepõem, então não há nada para reaproveitar
  2. BO merge sort não tem estrutura recursiva
  3. CA programação dinâmica só funciona em problemas de grafos, não em vetores
  4. DO merge sort já é O(n)
5.Média

Qual é a complexidade de tempo de multiplicar duas matrizes n × n com o laço triplo padrão?

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

Qual é o tempo de execução do radix sort LSD para n inteiros com d dígitos na base k?

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

A ordenação topológica só é possível para:

  1. AGrafos acíclicos dirigidos (DAG)
  2. BGrafos não dirigidos
  3. CGrafos com pesos negativos
  4. DGrafos completos
8.Difícil

Qual limite está correto para log(n!)?

  1. AΘ(n)
  2. BΘ(n²)
  3. CΘ(log n)
  4. DΘ(n log n)

Gabarito

  1. 1. D · O(n)
  2. 2. C · O tempo esperado sobre uma dada distribuição de entradas de tamanho n
  3. 3. B · Seu tempo de execução não cresce com o tamanho da entrada
  4. 4. A · Seus subproblemas não se sobrepõem, então não há nada para reaproveitar
  5. 5. D · O(n³)
  6. 6. B · O(d(n + k))
  7. 7. A · Grafos acíclicos dirigidos (DAG)
  8. 8. D · Θ(n log n)

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