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

Comment fonctionne le tri par sélection ?

  1. AIl divise le tableau en deux moitiés et les fusionne
  2. BIl échange à plusieurs reprises les éléments voisins mal ordonnés
  3. CIl cherche à plusieurs reprises le minimum de la partie non triée et l'échange vers l'avant
  4. DIl insère chaque élément dans une partie triée croissante par décalages
2.Facile

Qu'est-ce qu'un algorithme ?

  1. AUn langage de programmation conçu pour écrire des formules mathématiques
  2. BUne structure de données qui stocke des nombres
  3. CTout programme informatique doté d'une interface graphique
  4. DUne suite finie d'étapes bien définies qui résout un problème
3.Facile

Quelle notation décrit une borne inférieure de croissance ?

  1. AΩ (grand Oméga)
  2. BΘ (grand Thêta)
  3. CO (grand O)
  4. Do (petit o)
4.Moyen

Quel énoncé sur une fonction récursive sans cas de base atteignable est correct ?

  1. AElle s'exécute en temps O(1)
  2. BElle continue de s'appeler jusqu'au débordement de la pile d'appels
  3. CElle renvoie automatiquement 0
  4. DLe compilateur la transforme toujours en une boucle qui se termine sans danger
5.Moyen

Dans un tableau trié, vous cherchez deux éléments dont la somme vaut une cible en déplaçant un pointeur depuis chaque extrémité vers l'intérieur. Quelle est la complexité temporelle ?

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

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

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

Les plus courts chemins simples peuvent être trouvés en temps polynomial. Que sait-on de la recherche du plus long chemin simple entre deux sommets dans un graphe quelconque ?

  1. AOn peut le résoudre avec l'algorithme de Dijkstra en prenant l'opposé des poids
  2. BC'est NP-difficile
  3. CC'est toujours résoluble en O(V + E)
  4. DC'est indécidable
8.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 log n) par incrémentation
  2. BO(n) par incrémentation
  3. CO(log n) par incrémentation
  4. DO(1) par incrémentation

Corrigé

  1. 1. C · Il cherche à plusieurs reprises le minimum de la partie non triée et l'échange vers l'avant
  2. 2. D · Une suite finie d'étapes bien définies qui résout un problème
  3. 3. A · Ω (grand Oméga)
  4. 4. B · Elle continue de s'appeler jusqu'au débordement de la pile d'appels
  5. 5. A · O(n)
  6. 6. A · O(n log n)
  7. 7. B · C'est NP-difficile
  8. 8. D · O(1) par incrémentation

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