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

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

  1. ATable de hachage
  2. BPile (stack)
  3. CFile (queue)
  4. DListe chaînée
2.Facile

Dans une représentation d'un graphe par listes d'adjacence, que stocke-t-on pour chaque sommet ?

  1. ALe plus court chemin vers tous les autres sommets
  2. BLa liste de ses sommets voisins
  3. CLe nombre total d'arêtes du graphe
  4. DUne ligne de V valeurs booléennes
3.Facile

Dans un arbre, qu'est-ce qu'une feuille ?

  1. AUn nœud sans parent
  2. BUn nœud ayant exactement un enfant
  3. CLe nœud de plus grande valeur
  4. DUn nœud sans enfant
4.Moyen

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

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

Un nœud d'un arbre binaire de recherche possède un sous-arbre droit. Où se trouve son successeur dans l'ordre infixe ?

  1. AAu nœud le plus à gauche de son sous-arbre droit
  2. BÀ son enfant droit, toujours
  3. CÀ son parent, toujours
  4. DAu nœud le plus à droite de son sous-arbre gauche
6.Moyen

Quel type abstrait de données l'algorithme de Dijkstra utilise-t-il pour choisir le prochain sommet à traiter ?

  1. AUn ensemble sans ordre
  2. BUne file FIFO
  3. CUne file de priorité min
  4. DUne pile
7.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. BLe remplaçant par son successeur infixe (ou prédécesseur) puis en supprimant ce nœud
  3. CL'échangeant avec la racine
  4. DReconstruisant de zéro le sous-arbre situé en dessous et en réinsérant toutes les clés qu'il contenait
8.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 utilisent moins de mémoire que n'importe quel tableau, si bien que tout l'index tient toujours en mémoire centrale
  2. BIls n'ont pas besoin de rééquilibrage
  3. CIls stockent les données sans les trier
  4. DLeur facteur de branchement élevé maintient l'arbre peu profond, ce qui réduit les lectures disque lentes

Corrigé

  1. 1. B · Pile (stack)
  2. 2. B · La liste de ses sommets voisins
  3. 3. D · Un nœud sans enfant
  4. 4. B · Les recherches par préfixe, comme l'autocomplétion
  5. 5. A · Au nœud le plus à gauche de son sous-arbre droit
  6. 6. C · Une file de priorité min
  7. 7. B · Le remplaçant par son successeur infixe (ou prédécesseur) puis en supprimant ce nœud
  8. 8. D · Leur facteur de branchement élevé maintient l'arbre peu profond, ce qui réduit les lectures disque lentes

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