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

O tempo de execução de um algoritmo é O(n). Como se chama esse crescimento?

  1. AConstante
  2. BQuadrático
  3. CLogarítmico
  4. DLinear
2.Fácil

Qual é a complexidade de tempo do insertion sort no melhor caso, com um array já ordenado?

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

Qual é o O grande de 3n² + 5n + 2?

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

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

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

Qual é a complexidade de tempo amortizada de adicionar ao final de um array dinâmico que dobra sua capacidade quando fica cheio?

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

Qual é a complexidade de tempo do quicksort no pior caso?

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

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

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

Tomar as duas extremidades de cada aresta de um emparelhamento maximal dá uma cobertura de vértices. Quão boa é essa cobertura?

  1. ANo máximo o dobro do tamanho de uma cobertura de vértices mínima
  2. BDe qualidade desconhecida em relação ao ótimo
  3. CSempre uma cobertura de vértices mínima
  4. DNo máximo log n vezes o mínimo

Gabarito

  1. 1. D · Linear
  2. 2. A · O(n)
  3. 3. A · O(n²)
  4. 4. D · O(log n)
  5. 5. A · O(1)
  6. 6. B · O(n²)
  7. 7. A · Grafos acíclicos dirigidos (DAG)
  8. 8. A · No máximo o dobro do tamanho de uma cobertura de vértices mínima

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