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

Quelles sont les trois étapes d'un algorithme « diviser pour régner » ?

  1. ALire, calculer, écrire
  2. BDeviner, vérifier, recommencer
  3. CDiviser, régner, combiner
  4. DTrier, chercher, renvoyer
2.Facile

Un algorithme en O(n) prend 3 secondes pour n = 1 million. Combien de temps prend-il environ pour n = 2 millions ?

  1. A6 secondes
  2. B3 secondes
  3. C12 secondes
  4. D9 secondes
3.Facile

Combien de mémoire supplémentaire utilise un tri fusion standard sur tableau ?

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

Quel algorithme trouve les plus courts chemins depuis une source dans un graphe dont les poids des arêtes sont positifs ou nuls ?

  1. AL'algorithme de Dijkstra
  2. BLe parcours en profondeur (DFS)
  3. CBellman-Ford est nécessaire dans tous les cas
  4. DL'algorithme de Kruskal
5.Moyen

Quel algorithme de tri est stable ?

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

Quelle est la solution de la récurrence T(n) = T(n/2) + O(1) ?

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

Comment l'algorithme de Bellman-Ford détecte-t-il un cycle de poids négatif accessible depuis la source ?

  1. AIl exécute deux fois l'algorithme de Dijkstra et compare les deux résultats de distances
  2. BAprès V − 1 tours, il vérifie si une arête peut encore être relâchée
  3. CIl vérifie si une arête a un poids négatif
  4. DIl compte les cycles par un parcours en profondeur
8.Difficile

Pourquoi toute recherche par comparaisons dans un tableau trié nécessite-t-elle Ω(log n) comparaisons dans le pire cas ?

  1. ALa recherche dichotomique est le seul algorithme possible, et elle nécessite log₂ n comparaisons
  2. BChaque élément doit être comparé au moins une fois
  3. CChaque comparaison prend un temps logarithmique
  4. DUn arbre de décision à n issues possibles doit avoir une profondeur d'au moins log₂ n

Corrigé

  1. 1. C · Diviser, régner, combiner
  2. 2. A · 6 secondes
  3. 3. C · O(n)
  4. 4. A · L'algorithme de Dijkstra
  5. 5. C · Tri fusion
  6. 6. C · O(log n)
  7. 7. B · Après V − 1 tours, il vérifie si une arête peut encore être relâchée
  8. 8. D · Un arbre de décision à n issues possibles doit avoir une profondeur d'au moins log₂ n

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