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. ALibérer la mémoire après le retour d'une fonction
  2. BStocker les résultats des appels de fonction pour répondre aux appels répétés depuis la mémoire
  3. CÉcrire des commentaires à côté de chaque ligne de code
  4. DConvertir automatiquement une récursion en boucle équivalente, si bien qu'aucune pile d'appels n'est nécessaire
2.Facile

La complexité spatiale mesure :

  1. ALa taille physique de l'ordinateur
  2. BLa quantité de mémoire dont un algorithme a besoin lorsque la taille de l'entrée augmente
  3. CL'espace disque du fichier du programme une fois compilé
  4. DLe nombre de lignes de code
3.Facile

Que décrit le temps d'exécution en moyenne ?

  1. ALe temps sur l'ordinateur le plus répandu
  2. BLa valeur intermédiaire entre les temps d'exécution du meilleur et du pire cas
  3. CLe temps pour une entrée de longueur moyenne
  4. DLe temps espéré selon une distribution donnée des entrées de taille n
4.Moyen

Dans le problème de sélection d'activités, quelle règle gloutonne donne toujours un nombre maximal d'activités sans chevauchement ?

  1. AChoisir d'abord l'activité la plus courte
  2. BChoisir l'activité qui commence le plus tôt
  3. CChoisir d'abord l'activité ayant le moins de chevauchements, puis recommencer avec les activités compatibles
  4. DChoisir l'activité qui se termine le plus tôt, puis recommencer avec les activités compatibles
5.Moyen

Le parcours en largeur (BFS) sur un graphe non pondéré trouve :

  1. AL'arbre couvrant de poids minimal
  2. BLes plus courts chemins en nombre d'arêtes depuis le nœud de départ
  3. CLes plus courts chemins dans les graphes qui contiennent des poids d'arêtes négatifs
  4. DUn ordre topologique dans tous les graphes
6.Moyen

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

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

Quel énoncé sur la notation petit o est correct ?

  1. An = o(n²), mais n n'est pas o(n)
  2. Bn = o(n), puisque toute fonction est un petit o d'elle-même
  3. C2n = o(n), car 2n croît lentement
  4. Dn² = o(n)
8.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. CL'accès aux tableaux est en O(n)
  4. DDe nombreuses clés peuvent entrer en collision dans le même compartiment

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. B · La quantité de mémoire dont un algorithme a besoin lorsque la taille de l'entrée augmente
  3. 3. D · Le temps espéré selon une distribution donnée des entrées de taille n
  4. 4. D · Choisir l'activité qui se termine le plus tôt, puis recommencer avec les activités compatibles
  5. 5. B · Les plus courts chemins en nombre d'arêtes depuis le nœud de départ
  6. 6. D · O(log n)
  7. 7. A · n = o(n²), mais n n'est pas o(n)
  8. 8. D · De nombreuses clés peuvent entrer en collision dans le même compartiment

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