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 destes tempos de execução é polinomial?

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

Um problema costuma ser chamado de tratável se:

  1. APode ser resolvido em tempo polinomial
  2. BSó pode ser resolvido testando todas as possibilidades
  3. CNão tem solução
  4. DPode ser resolvido em tempo constante
3.Fácil

O que a busca binária exige da sua entrada?

  1. AO tamanho do array deve ser uma potência de dois
  2. BO array deve conter só números positivos
  3. CO array deve estar ordenado
  4. DO array não pode ter mais de 1000 elementos
4.Média

Um quicksort usa sempre o primeiro elemento como pivô. Com qual entrada ele apresenta o comportamento de pior caso?

  1. AUm array em ordem aleatória
  2. BUm array de tamanho 2
  3. CUm array com todos os elementos diferentes
  4. DUm array que já está ordenado
5.Média

O que a análise amortizada mede?

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

Com moedas de 1, 3 e 4 e um valor de 6, quantas moedas o método guloso "maior moeda primeiro" usa, em comparação com o ótimo?

  1. AO guloso usa 2 moedas; o ótimo é 2
  2. BO guloso usa 3 moedas; o ótimo é 3
  3. CO guloso usa 3 moedas; o ótimo é 2
  4. DO guloso usa 4 moedas; o ótimo é 3
7.Difícil

Para mostrar que um novo problema X é NP-difícil, o que você precisa fazer?

  1. AReduzir X a um problema NP-difícil conhecido em tempo polinomial
  2. BMostrar que X pode ser verificado em tempo polinomial
  3. CMostrar que X não tem algoritmo polinomial para entradas pequenas
  4. DReduzir um problema NP-difícil conhecido a X em tempo polinomial
8.Difícil

Qual definição da classe NP está correta?

  1. AProblemas que nenhum algoritmo consegue resolver
  2. BProblemas que não podem ser resolvidos em tempo polinomial
  3. CProblemas que não são polinomiais
  4. DProblemas de decisão cujas respostas "sim" podem ser verificadas em tempo polinomial dado um certificado

Gabarito

  1. 1. A · O(n³)
  2. 2. A · Pode ser resolvido em tempo polinomial
  3. 3. C · O array deve estar ordenado
  4. 4. D · Um array que já está ordenado
  5. 5. C · O custo médio por operação ao longo de uma sequência de operações de pior caso
  6. 6. C · O guloso usa 3 moedas; o ótimo é 2
  7. 7. D · Reduzir um problema NP-difícil conhecido a X em tempo polinomial
  8. 8. D · Problemas de decisão cujas respostas "sim" podem ser verificadas em tempo polinomial dado um certificado

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