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 é o tempo de execução do counting sort para n inteiros no intervalo de 0 a k?

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

Qual algoritmo de ordenação escolhe um pivô e particiona o array em elementos menores e maiores?

  1. AQuicksort
  2. BMerge sort
  3. CBubble sort
  4. DInsertion sort
3.Fácil

Qual é a complexidade de tempo da busca binária em um array ordenado?

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

Qual algoritmo encontra os caminhos mínimos a partir de uma origem em um grafo com pesos de arestas não negativos?

  1. ABellman-Ford é necessário em todos os casos
  2. BBusca em profundidade (DFS)
  3. CAlgoritmo de Kruskal
  4. DAlgoritmo de Dijkstra
5.Média

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

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

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

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

22n está em O(2ⁿ)?

  1. ANão, porque 22n cresce mais devagar que 2ⁿ
  2. BSim, porque fatores constantes no expoente são sempre ignorados no O grande
  3. CNão, porque 22n = 4ⁿ e 4ⁿ / 2ⁿ = 2ⁿ cresce sem limite
  4. DSim, porque ambos são exponenciais
8.Difícil

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

  1. ACrescem no mesmo ritmo
  2. Bn! cresce mais rápido que 2ⁿ
  3. C2ⁿ cresce mais rápido que n!
  4. Dn! é O(n²)

Gabarito

  1. 1. A · O(n + k)
  2. 2. A · Quicksort
  3. 3. D · O(log n)
  4. 4. D · Algoritmo de Dijkstra
  5. 5. A · O(n²)
  6. 6. C · O(2ⁿ)
  7. 7. C · Não, porque 22n = 4ⁿ e 4ⁿ / 2ⁿ = 2ⁿ cresce sem limite
  8. 8. B · n! cresce mais rápido que 2ⁿ

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