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

Que contient chaque nœud d'une liste doublement chaînée ?

  1. ADes données, un pointeur vers le nœud suivant et un pointeur vers le nœud précédent
  2. BDes données et uniquement un pointeur vers le nœud suivant
  3. CDes données et deux pointeurs, l'un vers le nœud suivant et l'autre vers le nœud d'après
  4. DDeux copies des données et un pointeur
2.Facile

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

  1. APile (stack)
  2. BFile (queue)
  3. CListe chaînée
  4. DTable de hachage
3.Facile

Qu'est-ce qui définit un arbre binaire ?

  1. AChaque nœud a exactement deux enfants
  2. BChaque nœud stocke un nombre binaire
  3. CL'arbre a exactement deux niveaux
  4. DChaque nœud a au plus deux enfants
4.Moyen

Une table de hachage de taille 7 utilise h(k) = k mod 7 et le sondage linéaire. Après l'insertion de 10, où est stocké 17 ?

  1. AÀ l'indice 0
  2. BÀ l'indice 3
  3. CÀ l'indice 4
  4. DÀ l'indice 6
5.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 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
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 linéaire (linear probing)
  2. BLe sondage quadratique (quadratic probing)
  3. CLe double hachage (double hashing)
  4. DLe chaînage séparé (separate chaining)
7.Difficile

Un nœud AVL est déséquilibré parce que le sous-arbre droit de son enfant gauche est devenu trop haut (cas gauche-droite). Quelle correction applique-t-on ?

  1. AUne rotation simple à gauche sur le nœud
  2. BUne rotation simple à droite sur le nœud
  3. CUne rotation à droite sur l'enfant gauche, puis une rotation à gauche sur le nœud
  4. DUne rotation à gauche sur l'enfant gauche, puis une rotation à droite sur le nœud
8.Difficile

Quel problème du sondage linéaire le double hachage réduit-il principalement ?

  1. ALe regroupement primaire (primary clustering), où se forment de longues suites de cases occupées
  2. BLe besoin de stocker les clés dans la table
  3. CLe coût en O(n) de la lecture de la valeur d'une clé
  4. DLe besoin d'une fonction de hachage

Corrigé

  1. 1. A · Des données, un pointeur vers le nœud suivant et un pointeur vers le nœud précédent
  2. 2. A · Pile (stack)
  3. 3. D · Chaque nœud a au plus deux enfants
  4. 4. C · À l'indice 4
  5. 5. A · On déplace le dernier élément à la racine et on le fait descendre
  6. 6. D · Le chaînage séparé (separate chaining)
  7. 7. D · Une rotation à gauche sur l'enfant gauche, puis une rotation à droite sur le nœud
  8. 8. A · Le regroupement primaire (primary clustering), où se forment de longues suites de cases occupées

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