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. BPush (empiler)
  3. CPop (dépiler)
  4. DPeek (consulter)
2.Facile

Quelle structure de données convient le mieux à la fonction « annuler » (undo) d'un éditeur de texte ?

  1. APile (stack)
  2. BFile (queue)
  3. CEnsemble haché (hash set)
  4. DGraphe
3.Facile

Qu'est-ce que la racine d'un arbre ?

  1. ALe nœud ayant la plus grande valeur
  2. BUn nœud sans enfant
  3. CLe nœud situé tout en haut, sans parent
  4. DN'importe quel nœud au milieu
4.Moyen

Comment insère-t-on un nouvel élément dans un tas binaire ?

  1. AOn l'insère à sa position triée en décalant d'un cran vers la droite tous les éléments plus grands
  2. BOn le place à la fin du tableau et on le fait remonter tant qu'il viole la propriété de tas
  3. COn reconstruit entièrement le tas
  4. DOn le place à la racine et on le fait descendre
5.Moyen

À quoi sert un nœud sentinelle (factice) dans une liste chaînée ?

  1. AÀ simplifier le code en supprimant les cas particuliers en tête ou en queue
  2. BÀ rendre la liste triée
  3. CÀ empêcher la liste de dépasser un nombre maximal fixe de nœuds
  4. DÀ stocker le nombre d'éléments
6.Moyen

Quelle est la hauteur, dans le pire des cas, d'un arbre binaire de recherche à n nœuds si les clés sont insérées dans l'ordre trié ?

  1. A√n
  2. Bn (il devient une liste chaînée)
  3. C1
  4. Dlog₂ n
7.Difficile

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

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

Un arbre de segments (segment tree) est généralement utilisé pour :

  1. ATrier des chaînes par ordre alphabétique en stockant chaque préfixe dans un nœud distinct de l'arbre
  2. BStocker les arêtes d'un graphe
  3. CRépondre à des requêtes sur intervalles (comme des sommes d'intervalles) et à des mises à jour en O(log n)
  4. DImplémenter une pile

Corrigé

  1. 1. B · Push (empiler)
  2. 2. A · Pile (stack)
  3. 3. C · Le nœud situé tout en haut, sans parent
  4. 4. B · On le place à la fin du tableau et on le fait remonter tant qu'il viole la propriété de tas
  5. 5. A · À simplifier le code en supprimant les cas particuliers en tête ou en queue
  6. 6. B · n (il devient une liste chaînée)
  7. 7. B · À vérifier si les deux extrémités d'une arête sont déjà reliées
  8. 8. C · Répondre à des requêtes sur intervalles (comme des sommes d'intervalles) et à des mises à jour en O(log n)

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