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. BPeek (consulter)
  3. CPush (empiler)
  4. DPop (dépiler)
2.Facile

Combien d'arêtes possède un arbre à n nœuds ?

  1. An
  2. B2n
  3. Cn + 1
  4. Dn − 1
3.Facile

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

  1. ALe nombre total d'arêtes du graphe
  2. BUne ligne de V valeurs booléennes
  3. CLa liste de ses sommets voisins
  4. DLe plus court chemin vers tous les autres sommets
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(1)
  3. CO(n)
  4. DO(n²)
5.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. ASeules les clés en collision sont déplacées dans une nouvelle liste de débordement à la fin de la table
  2. BLes clés les plus anciennes sont supprimées pour faire de la place
  3. CLes clés existantes sont triées sur place
  4. DUne table plus grande est allouée et chaque clé y est réinsérée
6.Moyen

Quelle condition d'équilibre un arbre AVL maintient-il en chaque nœud ?

  1. ALes deux sous-arbres de chaque nœud contiennent exactement le même nombre de nœuds
  2. BLes hauteurs des sous-arbres gauche et droit diffèrent d'au plus 1
  3. CChaque nœud est colorié en rouge ou en noir
  4. DToutes les feuilles sont exactement à la même profondeur
7.Difficile

L'algorithme de Kahn pour le tri topologique retire répétitivement les sommets de degré entrant 0. Quelle structure contient ces sommets ?

  1. AUne matrice d'adjacence indiquant quels sommets ont déjà été retirés
  2. BUn tas max ordonné par degré sortant
  3. CUne file (ou toute collection) des sommets de degré entrant 0
  4. DUne pile de toutes les arêtes visitées
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(n) en espace supplémentaire
  2. BO(n) en temps et O(1) 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 · Push (empiler)
  2. 2. D · n − 1
  3. 3. C · La liste de ses sommets voisins
  4. 4. B · O(1)
  5. 5. D · Une table plus grande est allouée et chaque clé y est réinsérée
  6. 6. B · Les hauteurs des sous-arbres gauche et droit diffèrent d'au plus 1
  7. 7. C · Une file (ou toute collection) des sommets de degré entrant 0
  8. 8. B · 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.