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

Dans une liste simplement chaînée, que contient le pointeur next du dernier nœud ?

  1. AL'adresse du nœud précédent
  2. BLe nombre de nœuds de la liste
  3. CL'adresse du premier nœud
  4. DNull (aucun nœud)
2.Facile

Quelle structure est généralement utilisée pour implémenter une file de priorité ?

  1. AUn tas (heap)
  2. BUne chaîne de caractères
  3. CUne pile (stack)
  4. DUne liste simplement chaînée non ordonnée
3.Facile

La profondeur d'un nœud dans un arbre est :

  1. ALe nombre d'enfants de ce nœud
  2. BLe nombre d'arêtes de ce nœud jusqu'à la feuille la plus profonde
  3. CLe nombre d'arêtes de la racine jusqu'à ce nœud
  4. DLe nombre de nœuds de son sous-arbre
4.Moyen

Une file est implémentée avec deux piles : on empile sur une pile « in » et on dépile depuis une pile « out », remplie à partir de « in » lorsqu'elle est vide. Quel est le coût amorti par opération ?

  1. AO(log n)
  2. BO(n)
  3. CO(n²)
  4. DO(1)
5.Moyen

Dans une file circulaire stockée dans un tableau de capacité n, comment calcule-t-on la position suivant l'indice i ?

  1. A(i + 1) mod n
  2. B2i + 1
  3. Ci + 1
  4. D(i − 1) mod n
6.Moyen

Un arbre binaire a pour racine 1, avec 2 comme enfant gauche et 3 comme enfant droit ; le nœud 2 a pour enfants 4 (gauche) et 5 (droit). Quel est le parcours postfixe ?

  1. A1 2 4 5 3
  2. B5 4 3 2 1
  3. C4 2 5 1 3
  4. D4 5 2 3 1
7.Difficile

Pourquoi les arbres B (B-trees) sont-ils utilisés dans les bases de données et les systèmes de fichiers ?

  1. AIls stockent les données sans les trier
  2. BIls utilisent moins de mémoire que n'importe quel tableau, si bien que tout l'index tient toujours en mémoire centrale
  3. CIls n'ont pas besoin de rééquilibrage
  4. DLeur facteur de branchement élevé maintient l'arbre peu profond, ce qui réduit les lectures disque lentes
8.Difficile

Pourquoi ne peut-on pas simplement supprimer des éléments d'un filtre de Bloom standard en remettant leurs bits à zéro ?

  1. ALes bits d'un filtre de Bloom ne peuvent pas être modifiés après sa création
  2. BCes bits peuvent aussi appartenir à d'autres éléments, ce qui provoquerait des faux négatifs
  3. CLa suppression porterait le taux de faux positifs à 100%
  4. DLes filtres de Bloom stockent les éléments complets, qui sont introuvables une fois hachés

Corrigé

  1. 1. D · Null (aucun nœud)
  2. 2. A · Un tas (heap)
  3. 3. C · Le nombre d'arêtes de la racine jusqu'à ce nœud
  4. 4. D · O(1)
  5. 5. A · (i + 1) mod n
  6. 6. D · 4 5 2 3 1
  7. 7. D · Leur facteur de branchement élevé maintient l'arbre peu profond, ce qui réduit les lectures disque lentes
  8. 8. B · Ces bits peuvent aussi appartenir à d'autres éléments, ce qui provoquerait des faux négatifs

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