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

Dans une liste simplement chaînée, chaque nœud contient :

  1. ADes données et un indice
  2. BDes données et une référence vers le nœud suivant
  3. CUniquement des données
  4. DDes données et des références vers tous les autres nœuds
2.Facile

Une table de hachage stocke les données sous forme de :

  1. AChaîne de longueur fixe
  2. BArbre à clés ordonnées
  3. CListe triée uniquement
  4. DPaires clé–valeur localisées par une fonction de hachage
3.Facile

Comment s'appelle l'opération de pile qui ajoute un élément au sommet ?

  1. APush (empiler)
  2. BEnqueue (enfiler)
  3. CPeek (consulter)
  4. DPop (dépiler)
4.Moyen

Un réseau routier compte 100,000 carrefours, chacun relié à environ 4 autres. Quelle représentation est la plus adaptée ?

  1. AUne matrice d'adjacence
  2. BUn unique tableau trié de sommets
  3. CUn tas binaire d'arêtes
  4. DUne liste d'adjacence
5.Moyen

Vous avez une référence vers un nœud au milieu d'une liste. Dans quelle liste pouvez-vous le supprimer en O(1) ?

  1. AUne liste doublement chaînée
  2. BUn tableau trié
  3. CUne liste simplement chaînée
  4. DUn tableau dynamique
6.Moyen

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

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

Quelle propriété maintient tout B-arbre parfaitement équilibré ?

  1. ALes clés ne sont stockées que dans la racine
  2. BToutes les feuilles sont à la même profondeur
  3. CChaque nœud stocke une seule clé
  4. DChaque nœud a exactement deux enfants
8.Difficile

Comment détecter si une liste simplement chaînée contient un cycle avec O(1) mémoire supplémentaire ?

  1. ATrier la liste et chercher des doublons
  2. BStocker chaque nœud visité dans un ensemble haché
  3. CCompter les nœuds jusqu'à dépasser le champ de longueur de la liste
  4. DAvancer un pointeur d'un pas et un autre de deux pas, et vérifier s'ils se rencontrent

Corrigé

  1. 1. B · Des données et une référence vers le nœud suivant
  2. 2. D · Paires clé–valeur localisées par une fonction de hachage
  3. 3. A · Push (empiler)
  4. 4. D · Une liste d'adjacence
  5. 5. A · Une liste doublement chaînée
  6. 6. D · Les hauteurs des sous-arbres gauche et droit diffèrent d'au plus 1
  7. 7. B · Toutes les feuilles sont à la même profondeur
  8. 8. D · Avancer un pointeur d'un pas et un autre de deux pas, et vérifier s'ils se rencontrent

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