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

Comment s'appelle l'opération de file qui retire l'élément situé à l'avant ?

  1. APush (empiler)
  2. BDequeue (défiler)
  3. CEnqueue (enfiler)
  4. DInsert (insérer)
2.Facile

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

  1. ADes données et uniquement un pointeur vers le nœud suivant
  2. BDes données, un pointeur vers le nœud suivant et un pointeur vers le nœud précédent
  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
3.Facile

Dans quel ordre un parcours préfixe (preorder) d'un arbre binaire visite-t-il les nœuds ?

  1. ALe sous-arbre gauche, puis le nœud, puis le sous-arbre droit
  2. BNiveau par niveau en partant du haut
  3. CLe nœud, puis le sous-arbre gauche, puis le sous-arbre droit
  4. DLe sous-arbre gauche, puis le sous-arbre droit, puis le nœud
4.Moyen

Dans un tas binaire stocké dans un tableau commençant à l'indice 0, où se trouve le parent du nœud d'indice i ?

  1. AÀ l'indice i − 1
  2. BÀ l'indice 2i + 1
  3. CÀ l'indice ⌊i / 2⌋ + 1
  4. DÀ l'indice ⌊(i − 1) / 2⌋
5.Moyen

Dans un tas binaire min stocké dans un tableau (indices commençant à 0), les enfants du nœud d'indice i se trouvent aux indices :

  1. A2i et 2i + 1
  2. B2i + 1 et 2i + 2
  3. Ci/2 et i/2 + 1
  4. Di + 1 et i + 2
6.Moyen

Quelle structure de données est utilisée par le parcours en profondeur (DFS) dans sa version itérative ?

  1. AUn tas
  2. BUne pile
  3. CUne file
  4. DUniquement une table de hachage
7.Difficile

Que fait un arbre splay (splay tree) après chaque accès ?

  1. AIl recolorie les nœuds du chemin de recherche
  2. BIl fait remonter le nœud accédé jusqu'à la racine par des rotations
  3. CIl déplace le nœud accédé vers une feuille
  4. DIl reconstruit tout l'arbre sous forme équilibrée
8.Difficile

Un tableau dynamique double de taille lorsqu'il est plein. Pourquoi de nombreuses implémentations ne le réduisent-elles que lorsqu'il est rempli au quart, et non à moitié ?

  1. APour éviter des redimensionnements répétés lorsque des push et des pop alternent près de la limite
  2. BParce que diviser par deux à la moitié ferait perdre des éléments
  3. CParce que l'allocateur de mémoire ne peut libérer la mémoire que par quarts de bloc
  4. DPour garder le tableau trié

Corrigé

  1. 1. B · Dequeue (défiler)
  2. 2. B · Des données, un pointeur vers le nœud suivant et un pointeur vers le nœud précédent
  3. 3. C · Le nœud, puis le sous-arbre gauche, puis le sous-arbre droit
  4. 4. D · À l'indice ⌊(i − 1) / 2⌋
  5. 5. B · 2i + 1 et 2i + 2
  6. 6. B · Une pile
  7. 7. B · Il fait remonter le nœud accédé jusqu'à la racine par des rotations
  8. 8. A · Pour éviter des redimensionnements répétés lorsque des push et des pop alternent près de la limite

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