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 escolhe um pivô e particiona o array em elementos menores e maiores?

  1. AMerge sort
  2. BInsertion sort
  3. CBubble sort
  4. DQuicksort
2.Fácil

O que descreve o tempo de execução de um algoritmo no pior caso?

  1. AO tempo esperado que leva com uma entrada aleatória de tamanho n
  2. BO tempo que leva com a menor entrada
  3. CO tempo que leva num computador lento
  4. DO tempo máximo que ele leva entre todas as entradas de tamanho n
3.Fácil

O que é um algoritmo de força bruta?

  1. AUm que chuta uma resposta ao acaso
  2. BUm que testa todas as soluções candidatas possíveis
  3. CUm que sempre usa recursão
  4. DUm que roda em vários processadores
4.Média

O limite inferior para ordenação baseada em comparações no pior caso é:

  1. AΩ(n²)
  2. BΩ(log n)
  3. CΩ(n)
  4. DΩ(n log n)
5.Média

Qual é a complexidade de tempo do algoritmo de Bellman–Ford num grafo com V vértices e E arestas?

  1. AO(E log V)
  2. BO(V + E)
  3. CO(V³ × E)
  4. DO(V × E)
6.Média

Você ordena um array de n elementos uma vez e depois responde a k consultas de pertinência com busca binária. Qual é o custo total?

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

Para qual variante da mochila a regra gulosa "pegar os itens em ordem de valor por peso" sempre dá uma resposta ótima?

  1. ANenhuma das variantes
  2. BA mochila 0/1, em que os itens devem ser sempre levados inteiros
  3. CAs duas variantes
  4. DA mochila fracionária, em que os itens podem ser divididos
8.Difícil

22n está em O(2ⁿ)?

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

Gabarito

  1. 1. D · Quicksort
  2. 2. D · O tempo máximo que ele leva entre todas as entradas de tamanho n
  3. 3. B · Um que testa todas as soluções candidatas possíveis
  4. 4. D · Ω(n log n)
  5. 5. D · O(V × E)
  6. 6. C · O(n log n + k log n)
  7. 7. D · A mochila fracionária, em que os itens podem ser divididos
  8. 8. B · Não, porque 22n = 4ⁿ e 4ⁿ / 2ⁿ = 2ⁿ cresce sem limite

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