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

Como se chama o crescimento O(2ⁿ)?

  1. ALogarítmico
  2. BLinear
  3. CPolinomial
  4. DExponencial
2.Fácil

Quais são as três etapas de um algoritmo de divisão e conquista?

  1. AOrdenar, buscar, retornar
  2. BLer, calcular, escrever
  3. CChutar, verificar, repetir
  4. DDividir, conquistar, combinar
3.Fácil

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

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

Um algoritmo guloso (greedy):

  1. AUsa apenas recursão
  2. BTesta todas as soluções possíveis
  3. CFaz a melhor escolha local em cada passo
  4. DSempre fornece a solução ótima
5.Média

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

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

No problema de seleção de atividades, qual regra gulosa sempre dá o número máximo de atividades sem sobreposição?

  1. AEscolher a atividade que começa mais cedo
  2. BEscolher primeiro a atividade mais curta
  3. CEscolher primeiro a atividade com menos sobreposições e repetir com as compatíveis
  4. DEscolher a atividade que termina mais cedo e repetir com as compatíveis
7.Difícil

Qual é o custo amortizado de incrementar um contador binário, sabendo que um incremento pode inverter muitos bits?

  1. AO(n log n) por incremento
  2. BO(log n) por incremento
  3. CO(1) por incremento
  4. DO(n) por incremento
8.Difícil

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

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

Gabarito

  1. 1. D · Exponencial
  2. 2. D · Dividir, conquistar, combinar
  3. 3. B · O tempo máximo que ele leva entre todas as entradas de tamanho n
  4. 4. C · Faz a melhor escolha local em cada passo
  5. 5. C · O(n²)
  6. 6. D · Escolher a atividade que termina mais cedo e repetir com as compatíveis
  7. 7. C · O(1) por incremento
  8. 8. D · Reduzir um problema NP-difícil conhecido a X em tempo polinomial

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