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

Qual destas cresce mais devagar quando n fica grande?

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

Qual classe de complexidade cresce mais rápido para n grande?

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

Qual é a complexidade de tempo do insertion sort no pior caso?

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

O que a análise amortizada mede?

  1. AO custo da operação individual mais cara em qualquer ponto da sequência
  2. BO custo médio por operação ao longo de uma sequência de operações de pior caso
  3. CO custo de um algoritmo com a melhor entrada
  4. DO custo esperado sobre entradas aleatórias
5.Média

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

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

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

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

Como n! e 2ⁿ se comparam para n grande?

  1. An! é O(n²)
  2. Bn! cresce mais rápido que 2ⁿ
  3. C2ⁿ cresce mais rápido que n!
  4. DCrescem no mesmo ritmo
8.Difícil

Qual algoritmo encontra uma árvore geradora mínima adicionando repetidamente a aresta mais barata que não forma um ciclo?

  1. AAlgoritmo de Prim a partir de um nó
  2. BAlgoritmo de Dijkstra
  3. CAlgoritmo de Kruskal
  4. DFloyd-Warshall

Gabarito

  1. 1. A · O(log n)
  2. 2. B · O(2ⁿ)
  3. 3. D · O(n²)
  4. 4. B · O custo médio por operação ao longo de uma sequência de operações de pior caso
  5. 5. D · Ela continua chamando a si mesma até a pilha de chamadas estourar
  6. 6. C · O(n²)
  7. 7. B · n! cresce mais rápido que 2ⁿ
  8. 8. C · Algoritmo de Kruskal

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