Algorithmique et structures de données : exercices et sujets d’examen

Notation grand O, temps d’exécution des algorithmes courants et compromis entre tableaux, listes chaînées, arbres, tables de hachage et graphes.

S’entraîner gratuitement sur ce coursS’entraîner sur ce coursPasser un examen blanc5 exercices gratuits chaque jour. Aucune carte bancaire requise.

Pack de révision (PDF)Formulaires, étapes de méthode et exercices avec corrigés complets, prêts à imprimer.

Thèmes de ce cours

  1. Algorithmes et complexitétermes et faits clés · appliquer les notions · cas et analyseQCM
  2. Structures de donnéestermes et faits clés · appliquer les notions · cas et analyseQCM
  3. Théorie des graphesdegrés et arêtes · chemins eulériens et arbres · plus courts chemins et arbres couvrantscalculs

Conseils pour l’examen de Algorithmique et structures de données

  • Pour des boucles imbriquées, multipliez les nombres d’itérations ; pour des boucles successives, gardez le terme le plus grand.
  • Connaissez le coût de la recherche, de l’insertion et de la suppression pour chaque structure de données.
  • Diviser l’entrée par deux à chaque étape donne un temps logarithmique.

Exemples corrigés

Algorithmes et complexitéFacile

Quelle notation décrit une borne supérieure de la croissance ?

  1. AGrand Oméga (Big Omega)
  2. BPetit oméga (little omega)
  3. CGrand O (Big O)
  4. DGrand Thêta (Big Theta)
Afficher les indices
  1. « Au plus ».
  2. Deux mauvaises réponses sont maintenant barrées. L'une des deux restantes est juste.
Afficher la réponse et l’explication

Pourquoi c'est la réponse

O donne une borne supérieure, Ω une borne inférieure et Θ une borne exacte (asymptotiquement serrée).

Réponse

C · Grand O (Big O)
Structures de donnéesMoyen

Comment fonctionne l'extraction du minimum (extract-min) dans un tas binaire min ?

  1. AOn retire le dernier élément du tableau
  2. BOn déplace le dernier élément à la racine et on le fait descendre
  3. COn retire la racine et on décale tous les éléments d'une case vers la gauche
  4. DOn cherche le nouveau minimum parmi toutes les feuilles
Afficher les indices
  1. Gardez l'arbre complet, puis corrigez l'ordre.
  2. Deux mauvaises réponses sont maintenant barrées. L'une des deux restantes est juste.
Afficher la réponse et l’explication

Pourquoi c'est la réponse

Le dernier élément comble le trou à la racine et est échangé avec son plus petit enfant jusqu'à ce que la propriété de tas soit respectée, en O(log n).

Réponse

B · On déplace le dernier élément à la racine et on le fait descendre

Comment fonctionne l’entraînement

  • « S’entraîner sur ce cours » mélange des exercices de tous ses thèmes, comme un vrai examen.
  • Chaque exercice a de nouvelles valeurs : vous apprenez la méthode, pas une réponse.
  • Bloqué ? Ouvrez d’abord un petit indice, et l’explication complète seulement si vous en avez besoin.
  • Les examens blancs sont chronométrés et sans indices ; vous obtenez votre score et une correction complète à la fin.

Cours associés

Fondements de l’informatiqueMathématiques discrètesRéseaux informatiques
S’entraîner gratuitement sur ce coursS’entraîner sur ce coursPasser un examen blanc5 exercices gratuits chaque jour. Aucune carte bancaire requise.