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 pile qui ajoute un élément au sommet ?

  1. AEnqueue (enfiler)
  2. BPop (dépiler)
  3. CPush (empiler)
  4. DPeek (consulter)
2.Facile

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

  1. AChaque nœud stocke un nombre binaire
  2. BChaque nœud a au plus deux enfants
  3. CChaque nœud a exactement deux enfants
  4. DL'arbre a exactement deux niveaux
3.Facile

Que fait l'opération peek (ou top) sur une pile ?

  1. AElle retire l'élément du sommet et le renvoie
  2. BElle renvoie l'élément du sommet sans le retirer
  3. CElle retire tous les éléments de la pile
  4. DElle renvoie l'élément du fond de la pile
4.Moyen

Pourquoi le parcours d'un tableau est-il souvent bien plus rapide en pratique que celui d'une liste chaînée de même longueur ?

  1. ALes tableaux utilisent moins d'instructions pour comparer les valeurs
  2. BLes listes chaînées stockent toujours leurs éléments sur disque
  3. CLes éléments d'un tableau sont contigus, ce qui exploite bien le cache du processeur
  4. DLe parcours d'un tableau est en O(1) au total, alors que celui d'une liste chaînée est en O(n)
5.Moyen

Quelle est la valeur de l'expression postfixée 3 4 + 2 * ?

  1. A14
  2. B24
  3. C11
  4. D10
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 file
  3. CUniquement une table de hachage
  4. DUne pile
7.Difficile

Vous devez conserver les k plus petites valeurs d'un flux de n nombres en utilisant O(k) mémoire. Quelle approche fonctionne en O(n log k) ?

  1. AUn tas min contenant les n valeurs, dont on extrait les k plus petites à la fin
  2. BUn tableau trié de toutes les n valeurs
  3. CUn tas max de taille k, dont on remplace la racine lorsqu'une valeur plus petite arrive
  4. DUne file FIFO des k dernières valeurs
8.Difficile

Comment détecter si une liste simplement chaînée contient un cycle avec O(1) mémoire supplémentaire ?

  1. AAvancer un pointeur d'un pas et un autre de deux pas, et vérifier s'ils se rencontrent
  2. BStocker chaque nœud visité dans un ensemble haché
  3. CTrier la liste et chercher des doublons
  4. DCompter les nœuds jusqu'à dépasser le champ de longueur de la liste

Corrigé

  1. 1. C · Push (empiler)
  2. 2. B · Chaque nœud a au plus deux enfants
  3. 3. B · Elle renvoie l'élément du sommet sans le retirer
  4. 4. C · Les éléments d'un tableau sont contigus, ce qui exploite bien le cache du processeur
  5. 5. A · 14
  6. 6. D · Une pile
  7. 7. C · Un tas max de taille k, dont on remplace la racine lorsqu'une valeur plus petite arrive
  8. 8. A · Avancer un pointeur d'un pas et un autre de deux pas, et vérifier s'ils se rencontrent

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