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'est-ce que la mémoïsation ?

  1. AConvertir automatiquement une récursion en boucle équivalente, si bien qu'aucune pile d'appels n'est nécessaire
  2. BStocker les résultats des appels de fonction pour répondre aux appels répétés depuis la mémoire
  3. CLibérer la mémoire après le retour d'une fonction
  4. DÉcrire des commentaires à côté de chaque ligne de code
2.Facile

Qu'est-ce que la récursivité ?

  1. AUn type de structure de données
  2. BUne méthode de tri
  3. CUne fonction qui s'appelle elle-même sur des entrées plus petites
  4. DUne boucle qui ne se termine jamais
3.Facile

Quel est le grand O de 3n² + 5n + 2 ?

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

Pourquoi la programmation dynamique n'apporte-t-elle aucune accélération réelle au tri fusion ?

  1. ASes sous-problèmes ne se chevauchent pas, il n'y a donc rien à réutiliser
  2. BLa programmation dynamique ne fonctionne que sur les problèmes de graphes, pas sur les tableaux
  3. CLe tri fusion n'a pas de structure récursive
  4. DLe tri fusion est déjà en O(n)
5.Moyen

Que mesure l'analyse amortie ?

  1. ALe coût de l'unique opération la plus chère, où qu'elle se trouve dans la suite
  2. BLe coût espéré sur des entrées aléatoires
  3. CLe coût d'un algorithme sur la meilleure entrée
  4. DLe coût moyen par opération sur une suite d'opérations de pire cas
6.Moyen

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

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

Pourquoi une recherche dans une table de hachage est-elle en O(1) en moyenne mais en O(n) dans le pire cas ?

  1. ALes fonctions de hachage sont lentes
  2. BLes clés doivent d'abord être triées
  3. CDe nombreuses clés peuvent entrer en collision dans le même compartiment
  4. DL'accès aux tableaux est en O(n)
8.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. AC'est toujours résoluble en O(V + E)
  2. BOn peut le résoudre avec l'algorithme de Dijkstra en prenant l'opposé des poids
  3. CC'est indécidable
  4. DC'est NP-difficile

Corrigé

  1. 1. B · Stocker les résultats des appels de fonction pour répondre aux appels répétés depuis la mémoire
  2. 2. C · Une fonction qui s'appelle elle-même sur des entrées plus petites
  3. 3. C · O(n²)
  4. 4. A · Ses sous-problèmes ne se chevauchent pas, il n'y a donc rien à réutiliser
  5. 5. D · Le coût moyen par opération sur une suite d'opérations de pire cas
  6. 6. C · O(2ⁿ)
  7. 7. C · De nombreuses clés peuvent entrer en collision dans le même compartiment
  8. 8. D · C'est NP-difficile

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