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 algoritmo de ordenação troca repetidamente elementos adjacentes que estão na ordem errada?

  1. AMerge sort (ordenação por intercalação)
  2. BBubble sort (ordenação por bolha)
  3. CQuicksort
  4. DHeap sort
2.Fácil

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

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

A complexidade de espaço mede:

  1. AA quantidade de memória que um algoritmo precisa à medida que a entrada cresce
  2. BO tamanho físico do computador
  3. CO espaço em disco do arquivo do programa depois de compilado
  4. DO número de linhas de código
4.Média

Num array ordenado, você procura dois elementos cuja soma seja um alvo movendo um ponteiro de cada extremidade para dentro. Qual é a complexidade de tempo?

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

Qual é a complexidade de tempo de calcular o n-ésimo número de Fibonacci com uma tabela bottom-up?

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

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

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

22n está em O(2ⁿ)?

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

Por que o algoritmo de Dijkstra pode dar resultados errados quando alguns pesos de aresta são negativos?

  1. AEntra num laço infinito a cada aresta negativa
  2. BNúmeros negativos não podem ser armazenados numa fila de prioridade
  3. CUm vértice é finalizado ao ser extraído, mas uma aresta negativa posterior ainda poderia dar a ele um caminho mais curto
  4. DSó funciona em grafos não dirigidos

Gabarito

  1. 1. B · Bubble sort (ordenação por bolha)
  2. 2. C · O(2ⁿ)
  3. 3. A · A quantidade de memória que um algoritmo precisa à medida que a entrada cresce
  4. 4. B · O(n)
  5. 5. D · O(n)
  6. 6. A · O(n²)
  7. 7. B · Não, porque 22n = 4ⁿ e 4ⁿ / 2ⁿ = 2ⁿ cresce sem limite
  8. 8. C · Um vértice é finalizado ao ser extraído, mas uma aresta negativa posterior ainda poderia dar a ele um caminho mais curto

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