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 quel ordre un parcours préfixe (preorder) d'un arbre binaire visite-t-il les nœuds ?

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

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

  1. ADequeue (défiler)
  2. BInsert (insérer)
  3. CPush (empiler)
  4. DEnqueue (enfiler)
3.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. CNull (aucun nœud)
  4. DL'adresse du premier nœud
4.Moyen

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

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

Un trie (arbre de préfixes) est particulièrement efficace pour :

  1. ALe stockage de matrices
  2. BLes recherches par préfixe, comme l'autocomplétion
  3. CLe tri de nombres
  4. DLa recherche des plus courts chemins
6.Moyen

Quelle est la complexité temporelle de la recherche d'une clé dans un arbre binaire de recherche équilibré ?

  1. AO(1)
  2. BO(n log n)
  3. CO(log n)
  4. DO(n)
7.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. CCompter les nœuds jusqu'à dépasser le champ de longueur de la liste
  4. DTrier la liste et chercher des doublons
8.Difficile

La suppression d'un nœud ayant deux enfants dans un arbre binaire de recherche se fait généralement en :

  1. ASupprimant tout le sous-arbre
  2. BL'échangeant avec la racine
  3. CReconstruisant de zéro le sous-arbre situé en dessous et en réinsérant toutes les clés qu'il contenait
  4. DLe remplaçant par son successeur infixe (ou prédécesseur) puis en supprimant ce nœud

Corrigé

  1. 1. B · Le nœud, puis le sous-arbre gauche, puis le sous-arbre droit
  2. 2. A · Dequeue (défiler)
  3. 3. C · Null (aucun nœud)
  4. 4. C · On déplace le dernier élément à la racine et on le fait descendre
  5. 5. B · Les recherches par préfixe, comme l'autocomplétion
  6. 6. C · O(log n)
  7. 7. A · Avancer un pointeur d'un pas et un autre de deux pas, et vérifier s'ils se rencontrent
  8. 8. D · Le remplaçant par son successeur infixe (ou prédécesseur) puis en supprimant ce nœud

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