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. BHeap sort
  3. CQuicksort
  4. DBubble sort (ordenação por bolha)
2.Fácil

Qual estratégia de projeto o merge sort usa?

  1. AEscolha gulosa
  2. BProgramação dinâmica
  3. CDivisão e conquista
  4. DForça bruta
3.Fácil

Como funciona o selection sort?

  1. ATroca repetidamente elementos vizinhos que estão na ordem errada
  2. BDivide o array em metades e as intercala
  3. CEncontra repetidamente o mínimo da parte não ordenada e o troca para a frente
  4. DInsere cada elemento numa parte ordenada crescente por deslocamento
4.Média

Por que muitas rotinas de ordenação de bibliotecas passam para o insertion sort em subarrays muito pequenos?

  1. AAlgoritmos recursivos não conseguem lidar com arrays de menos de 10 elementos
  2. BO insertion sort usa menos memória que qualquer outro algoritmo de ordenação em entradas grandes
  3. CO insertion sort é O(n log n) no pior caso
  4. DO insertion sort tem pouco overhead e é rápido com entradas pequenas ou quase ordenadas
5.Média

O que o algoritmo de Floyd–Warshall calcula, e com que rapidez?

  1. AUma árvore geradora mínima em O(E log V)
  2. BCaminhos mínimos de um vértice de origem para todos os outros em O(V + E)
  3. CCaminhos mínimos entre todos os pares de vértices em O(V³)
  4. DUma ordenação topológica em O(V²)
6.Média

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

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

Qual é a diferença entre um problema indecidível e um intratável?

  1. AAmbos significam que o problema não tem nenhum algoritmo
  2. BProblemas intratáveis não podem ser resolvidos por nenhum algoritmo, enquanto os indecidíveis só exigem tempo exponencial
  3. CProblemas indecidíveis estão em NP, enquanto os intratáveis estão em P
  4. DNenhum algoritmo resolve um problema indecidível para todas as entradas, enquanto um intratável tem algoritmo, mas é lento demais
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. BReduzir X a um problema NP-difícil conhecido em tempo polinomial
  3. CReduzir um problema NP-difícil conhecido a X em tempo polinomial
  4. DMostrar que X pode ser verificado em tempo polinomial

Gabarito

  1. 1. D · Bubble sort (ordenação por bolha)
  2. 2. C · Divisão e conquista
  3. 3. C · Encontra repetidamente o mínimo da parte não ordenada e o troca para a frente
  4. 4. D · O insertion sort tem pouco overhead e é rápido com entradas pequenas ou quase ordenadas
  5. 5. C · Caminhos mínimos entre todos os pares de vértices em O(V³)
  6. 6. A · O(n)
  7. 7. D · Nenhum algoritmo resolve um problema indecidível para todas as entradas, enquanto um intratável tem algoritmo, mas é lento demais
  8. 8. C · 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.