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 « premier entré, premier sorti » (FIFO) ?

  1. ATas (heap)
  2. BArbre binaire
  3. CFile (queue)
  4. DPile (stack)
2.Facile

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

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

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

  1. ADeux copies des données et un pointeur
  2. BDes données et deux pointeurs, l'un vers le nœud suivant et l'autre vers le nœud d'après
  3. CDes données et uniquement un pointeur vers le nœud suivant
  4. DDes données, un pointeur vers le nœud suivant et un pointeur vers le nœud précédent
4.Moyen

Que se passe-t-il lorsqu'une table de hachage est rehachée après que son facteur de charge a dépassé un seuil ?

  1. ALes clés les plus anciennes sont supprimées pour faire de la place
  2. BUne table plus grande est allouée et chaque clé y est réinsérée
  3. CLes clés existantes sont triées sur place
  4. DSeules les clés en collision sont déplacées dans une nouvelle liste de débordement à la fin de la table
5.Moyen

Une application a besoin de recherches rapides, mais aussi de lister les clés dans l'ordre trié et de répondre à des requêtes par intervalle. Quelle structure convient le mieux ?

  1. AUne table de hachage
  2. BUne pile
  3. CUne liste chaînée non triée
  4. DUn arbre binaire de recherche équilibré
6.Moyen

Un parcours infixe (in-order) d'un arbre binaire de recherche visite les clés dans :

  1. AL'ordre d'insertion
  2. BL'ordre par niveaux
  3. CL'ordre croissant
  4. DToujours l'ordre décroissant
7.Difficile

Dans un tampon circulaire, front == rear peut signifier vide ou plein. Quelle est une manière courante de les distinguer ?

  1. ATenir un compteur d'éléments séparé, ou toujours laisser une case inutilisée
  2. BChoisir une taille de tampon égale à une puissance de deux
  3. CStocker front et rear dans la même variable
  4. DToujours vider le tampon dès que front est égal à rear, si bien que l'état est vide
8.Difficile

Quels sont les coûts en temps et en espace supplémentaire de l'inversion sur place d'une liste simplement chaînée ?

  1. AO(n) en temps et O(1) en espace supplémentaire
  2. BO(n) en temps et O(n) en espace supplémentaire
  3. CO(1) en temps et O(1) en espace supplémentaire
  4. DO(n log n) en temps et O(1) en espace supplémentaire

Corrigé

  1. 1. C · File (queue)
  2. 2. D · Un tas (heap)
  3. 3. D · Des données, un pointeur vers le nœud suivant et un pointeur vers le nœud précédent
  4. 4. B · Une table plus grande est allouée et chaque clé y est réinsérée
  5. 5. D · Un arbre binaire de recherche équilibré
  6. 6. C · L'ordre croissant
  7. 7. A · Tenir un compteur d'éléments séparé, ou toujours laisser une case inutilisée
  8. 8. A · O(n) en temps et O(1) en espace supplémentaire

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