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 opération est lente dans un tableau mais rapide en tête d'une liste chaînée ?

  1. ALa lecture du dernier élément par son indice
  2. BLe calcul de la longueur d'un tableau de taille fixe
  3. CL'accès au 5e élément
  4. DL'insertion au début
2.Facile

Quelle est la caractéristique essentielle d'un ensemble en tant que type abstrait de données ?

  1. AIl stocke des paires clé–valeur
  2. BIl stocke des éléments dans l'ordre trié
  3. CIl ne permet l'accès qu'à une seule extrémité
  4. DIl stocke des éléments sans doublons
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. BLe plus court chemin vers tous les autres sommets
  3. CLa liste de ses sommets voisins
  4. DUne ligne de V valeurs booléennes
4.Moyen

Un tampon circulaire (ring buffer) est couramment utilisé pour implémenter :

  1. AUne fonction de hachage
  2. BUn arbre binaire de recherche
  3. CUne file de taille fixe
  4. DUn parcours de graphe
5.Moyen

Quelle structure de données est utilisée par le parcours en profondeur (DFS) dans sa version itérative ?

  1. AUne file
  2. BUne pile
  3. CUn tas
  4. DUniquement une table de hachage
6.Moyen

Les arbres AVL et les arbres rouge-noir garantissent :

  1. AUne hauteur en O(log n) grâce au rééquilibrage
  2. BQue les clés sont stockées dans l'ordre d'insertion
  3. CQu'aucun nœud n'a deux enfants
  4. DUne recherche en temps constant dans tous les cas
7.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 log n) en temps et O(1) en espace supplémentaire
  2. BO(n) en temps et O(1) en espace supplémentaire
  3. CO(n) en temps et O(n) en espace supplémentaire
  4. DO(1) en temps et O(1) en espace supplémentaire
8.Difficile

Dans une table de hachage à adressage ouvert, pourquoi la suppression se fait-elle souvent avec un marqueur « pierre tombale » (tombstone) ?

  1. ALes clés supprimées doivent être conservées pour toujours pour des raisons de sécurité, si bien que les emplacements ne peuvent jamais être réutilisés
  2. BLes pierres tombales accélèrent le hachage
  3. CCela rend la table triée
  4. DVider l'emplacement pourrait interrompre la séquence de sondage d'autres clés

Corrigé

  1. 1. D · L'insertion au début
  2. 2. D · Il stocke des éléments sans doublons
  3. 3. C · La liste de ses sommets voisins
  4. 4. C · Une file de taille fixe
  5. 5. B · Une pile
  6. 6. A · Une hauteur en O(log n) grâce au rééquilibrage
  7. 7. B · O(n) en temps et O(1) en espace supplémentaire
  8. 8. D · Vider l'emplacement pourrait interrompre la séquence de sondage d'autres clés

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