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. BL'insertion au début
  3. CL'accès au 5e élément
  4. DLe calcul de la longueur d'un tableau de taille fixe
2.Facile

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

  1. AArbre binaire
  2. BTas (heap)
  3. CFile (queue)
  4. DPile (stack)
3.Facile

Qu'est-ce qui définit un arbre binaire ?

  1. AL'arbre a exactement deux niveaux
  2. BChaque nœud a au plus deux enfants
  3. CChaque nœud stocke un nombre binaire
  4. DChaque nœud a exactement deux enfants
4.Moyen

Quelle structure de données un programme en cours d'exécution utilise-t-il pour suivre les appels de fonction actifs et leurs variables locales ?

  1. ALa pile d'appels
  2. BUn arbre binaire de recherche de cadres
  3. CLa file de la mémoire du tas
  4. DUne table de hachage des fonctions
5.Moyen

Quelle méthode de résolution des collisions stocke les clés en collision dans une liste au sein du même compartiment ?

  1. ALe sondage linéaire (linear probing)
  2. BLe chaînage séparé (separate chaining)
  3. CLe double hachage (double hashing)
  4. DLe sondage quadratique (quadratic probing)
6.Moyen

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

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

Dans l'algorithme de Kruskal pour l'arbre couvrant de poids minimal, à quoi sert la structure union-find ?

  1. AÀ stocker la distance actuelle de chaque sommet depuis la source pendant le parcours
  2. BÀ choisir le sommet de départ
  3. CÀ vérifier si les deux extrémités d'une arête sont déjà reliées
  4. DÀ trier les arêtes par poids
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 log 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

Corrigé

  1. 1. B · L'insertion au début
  2. 2. C · File (queue)
  3. 3. B · Chaque nœud a au plus deux enfants
  4. 4. A · La pile d'appels
  5. 5. B · Le chaînage séparé (separate chaining)
  6. 6. A · Une file de taille fixe
  7. 7. C · À vérifier si les deux extrémités d'une arête sont déjà reliées
  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.