Fiche d’exercices de Algorithmes et complexité avec corrigé

Fiche d’exercices de Algorithmes et complexité gratuite et imprimable : 8 exercices, du niveau facile au niveau examen, avec corrigé. Imprimez-la ou enregistrez-la en PDF.

Nouvelle ficheS’entraîner en ligne avec indices

Pour les enseignants : gratuite à imprimer, copier et utiliser en classe. Chaque nouvelle fiche a de nouvelles valeurs et son propre corrigé. Un lien vers ExamProblems sur la page de votre cours est apprécié.

Nom: ____________________   Date: ____________

1.Facile

Qu'exige la recherche dichotomique de son entrée ?

  1. ALe tableau ne doit pas avoir plus de 1000 éléments
  2. BLe tableau ne doit contenir que des nombres positifs
  3. CLa longueur du tableau doit être une puissance de deux
  4. DLe tableau doit être trié
2.Facile

Quelle est la complexité temporelle dans le meilleur cas du tri par insertion, sur un tableau déjà trié ?

  1. AO(1)
  2. BO(n)
  3. CO(n log n)
  4. DO(n²)
3.Facile

Le temps d'exécution d'un algorithme est O(n). Comment appelle-t-on cette croissance ?

  1. AQuadratique
  2. BConstante
  3. CLogarithmique
  4. DLinéaire
4.Moyen

La récurrence T(n) = 2T(n/2) + O(n) a pour solution :

  1. AO(log n)
  2. BO(n log n)
  3. CO(n)
  4. DO(n²)
5.Moyen

Quelle est la complexité temporelle du tri rapide (quicksort) dans le pire cas ?

  1. AO(n log n)
  2. BO(n²)
  3. CO(log n)
  4. DO(n)
6.Moyen

Quel algorithme de tri est stable ?

  1. ATri par tas
  2. BTri fusion
  3. CTri rapide (version en place habituelle)
  4. DTri par sélection (version habituelle)
7.Difficile

Quel est le coût amorti de l'incrémentation d'un compteur binaire, sachant qu'une incrémentation peut inverser de nombreux bits ?

  1. AO(n) par incrémentation
  2. BO(log n) par incrémentation
  3. CO(1) par incrémentation
  4. DO(n log n) par incrémentation
8.Difficile

Quelle affirmation concernant P et NP est correcte ?

  1. AIl a été démontré que P ≠ NP
  2. BNP signifie « non polynomial »
  3. CLes solutions des problèmes NP ne peuvent pas être vérifiées rapidement
  4. DTout problème de P appartient aussi à NP

Corrigé

  1. 1. D · Le tableau doit être trié
  2. 2. B · O(n)
  3. 3. D · Linéaire
  4. 4. B · O(n log n)
  5. 5. B · O(n²)
  6. 6. B · Tri fusion
  7. 7. C · O(1) par incrémentation
  8. 8. D · Tout problème de P appartient aussi à NP

Corrigés complets pas à pas : entraînez-vous sur ce thème sur examproblems.com.