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

O que é memoização?

  1. ALiberar memória depois que uma função retorna
  2. BArmazenar os resultados de chamadas de função para que chamadas repetidas sejam respondidas da memória
  3. CConverter automaticamente a recursão em um laço equivalente, de modo que não seja preciso pilha de chamadas
  4. DEscrever comentários ao lado de cada linha de código
2.Fácil

Qual algoritmo de ordenação troca repetidamente elementos adjacentes que estão na ordem errada?

  1. AQuicksort
  2. BBubble sort (ordenação por bolha)
  3. CHeap sort
  4. DMerge sort (ordenação por intercalação)
3.Fácil

Um laço começa com i = 1 e dobra i a cada iteração até i > n. Quantas iterações ele executa?

  1. ACerca de n / 2
  2. BCerca de log₂ n
  3. CCerca de n²
  4. DCerca de n
4.Média

O que significa um problema ter subestrutura ótima?

  1. AUma solução ótima pode ser construída a partir de soluções ótimas dos seus subproblemas
  2. BTodos os subproblemas têm o mesmo tamanho
  3. CO problema tem exatamente uma solução ótima, compartilhada por todos os subproblemas
  4. DO problema pode ser resolvido em tempo constante
5.Média

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

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

Qual é a complexidade de tempo de: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Caminhos simples mínimos podem ser encontrados em tempo polinomial. O que se sabe sobre encontrar o caminho simples mais longo entre dois vértices num grafo geral?

  1. AÉ indecidível
  2. BPode ser resolvido pelo algoritmo de Dijkstra com os pesos negados
  3. CÉ sempre solúvel em O(V + E)
  4. DÉ NP-difícil
8.Difícil

O insertion sort roda em O(n) com entrada ordenada. Isso contradiz o limite inferior Ω(n log n) da ordenação por comparação?

  1. ANão, o limite inferior vale para o pior caso entre todas as entradas, não para cada entrada
  2. BSim, portanto o limite inferior está errado
  3. CNão, porque o insertion sort não é uma ordenação por comparação
  4. DSim, mas só para arrays com menos de 100 elementos

Gabarito

  1. 1. B · Armazenar os resultados de chamadas de função para que chamadas repetidas sejam respondidas da memória
  2. 2. B · Bubble sort (ordenação por bolha)
  3. 3. B · Cerca de log₂ n
  4. 4. A · Uma solução ótima pode ser construída a partir de soluções ótimas dos seus subproblemas
  5. 5. D · O(log n)
  6. 6. D · O(n log n)
  7. 7. D · É NP-difícil
  8. 8. A · Não, o limite inferior vale para o pior caso entre todas as entradas, não para cada entrada

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