Fiche d’exercices de Structures de données avec corrigé

Fiche d’exercices de Structures de données 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 qu'un deque (file à double extrémité) ?

  1. AUne file triée par priorité
  2. BUne structure qui permet l'insertion et la suppression aux deux extrémités
  3. CUne file qui ne permet la suppression qu'à l'arrière
  4. DDeux files distinctes partageant un même tableau
2.Facile

Dans un arbre binaire de recherche, les valeurs du sous-arbre gauche d'un nœud sont :

  1. AÉgales à la valeur du nœud
  2. BDans un ordre aléatoire
  3. CSupérieures à la valeur du nœud
  4. DInférieures à la valeur du nœud
3.Facile

Quelle structure de données fonctionne selon le principe « dernier entré, premier sorti » (LIFO) ?

  1. ATable de hachage
  2. BFile (queue)
  3. CPile (stack)
  4. DListe chaînée
4.Moyen

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

  1. AOn déplace le dernier élément à la racine et on le fait descendre
  2. BOn retire le dernier élément du tableau
  3. COn cherche le nouveau minimum parmi toutes les feuilles
  4. DOn retire la racine et on décale tous les éléments d'une case vers la gauche
5.Moyen

Dans une table de hachage à adressage ouvert, quel est le facteur de charge maximal possible ?

  1. A0,5
  2. B2
  3. C1
  4. DIl n'y a pas de maximum
6.Moyen

Quelle méthode de résolution des collisions stocke les clés en collision dans une liste au sein du même compartiment ?

  1. ALe sondage quadratique (quadratic probing)
  2. BLe double hachage (double hashing)
  3. CLe sondage linéaire (linear probing)
  4. DLe chaînage séparé (separate chaining)
7.Difficile

Quelle propriété maintient tout B-arbre parfaitement équilibré ?

  1. ALes clés ne sont stockées que dans la racine
  2. BChaque nœud stocke une seule clé
  3. CChaque nœud a exactement deux enfants
  4. DToutes les feuilles sont à la même profondeur
8.Difficile

Quels sont les coûts en temps et en espace supplémentaire de l'inversion sur place d'une liste simplement chaînée ?

  1. AO(n) en temps et O(1) en espace supplémentaire
  2. BO(n) en temps et O(n) en espace supplémentaire
  3. CO(n log n) en temps et O(1) en espace supplémentaire
  4. DO(1) en temps et O(1) en espace supplémentaire

Corrigé

  1. 1. B · Une structure qui permet l'insertion et la suppression aux deux extrémités
  2. 2. D · Inférieures à la valeur du nœud
  3. 3. C · Pile (stack)
  4. 4. A · On déplace le dernier élément à la racine et on le fait descendre
  5. 5. C · 1
  6. 6. D · Le chaînage séparé (separate chaining)
  7. 7. D · Toutes les feuilles sont à la même profondeur
  8. 8. A · O(n) en temps et O(1) en espace supplémentaire

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