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 file qui retire l'élément situé à l'avant ?

  1. APush (empiler)
  2. BDequeue (défiler)
  3. CInsert (insérer)
  4. DEnqueue (enfiler)
2.Facile

Dans quel ordre un parcours postfixe (postorder) d'un arbre binaire visite-t-il les nœuds ?

  1. ALe sous-arbre droit, puis le nœud, puis le sous-arbre gauche
  2. BLe sous-arbre gauche, puis le nœud, puis le sous-arbre droit
  3. CLe nœud, puis le sous-arbre gauche, puis le sous-arbre droit
  4. DLe sous-arbre gauche, puis le sous-arbre droit, puis le nœud
3.Facile

Où se trouve le plus petit élément d'un tas binaire min ?

  1. ADans la feuille la plus à gauche
  2. BÀ la racine
  3. CDans une feuille quelconque, qu'il faut chercher
  4. DÀ la dernière position du tableau
4.Moyen

Un arbre binaire a pour racine 1, avec 2 comme enfant gauche et 3 comme enfant droit ; le nœud 2 a pour enfants 4 (gauche) et 5 (droit). Quel est le parcours postfixe ?

  1. A1 2 4 5 3
  2. B4 2 5 1 3
  3. C4 5 2 3 1
  4. D5 4 3 2 1
5.Moyen

Combien de temps prend la recherche d'un mot de longueur L dans un trie à alphabet fixe ?

  1. AO(n), où n est le nombre de mots
  2. BO(L × n)
  3. CO(L), quel que soit le nombre de mots stockés
  4. DO(log n), où n est le nombre de mots
6.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(n)
  3. CO(n²)
  4. DO(1)
7.Difficile

Quelle propriété un arbre rouge-noir doit-il respecter ?

  1. ATout nœud rouge doit avoir des enfants rouges, si bien que les nœuds rouges forment toujours des chaînes ininterrompues jusqu'aux feuilles
  2. BLa racine doit être rouge
  3. CTout chemin d'un nœud vers ses feuilles descendantes contient le même nombre de nœuds noirs
  4. DChaque nœud doit être rouge
8.Difficile

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

  1. AÀ trier les arêtes par poids
  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À stocker la distance actuelle de chaque sommet depuis la source pendant le parcours

Corrigé

  1. 1. B · Dequeue (défiler)
  2. 2. D · Le sous-arbre gauche, puis le sous-arbre droit, puis le nœud
  3. 3. B · À la racine
  4. 4. C · 4 5 2 3 1
  5. 5. C · O(L), quel que soit le nombre de mots stockés
  6. 6. D · O(1)
  7. 7. C · Tout chemin d'un nœud vers ses feuilles descendantes contient le même nombre de nœuds noirs
  8. 8. C · À vérifier si les deux extrémités d'une arête sont déjà reliées

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