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

Qu'est-ce qu'un graphe pondéré ?

  1. AUn graphe dans lequel chaque arête a une valeur numérique, comme un coût ou une distance
  2. BUn graphe stocké sur disque
  3. CUn graphe dans lequel certains sommets sont plus lourds que d'autres parce qu'ils ont plus d'arêtes
  4. DUn graphe ayant plus d'arêtes que de sommets
2.Facile

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

  1. APile (stack)
  2. BEnsemble haché (hash set)
  3. CGraphe
  4. DFile (queue)
3.Facile

Dans un arbre, que sont des nœuds frères ?

  1. AUn nœud et son parent
  2. BDes nœuds qui n'ont pas d'enfant
  3. CDes nœuds de même profondeur dans des sous-arbres différents
  4. DDes nœuds qui ont le même parent
4.Moyen

Un trie (arbre de préfixes) est particulièrement efficace pour :

  1. ALe stockage de matrices
  2. BLes recherches par préfixe, comme l'autocomplétion
  3. CLa recherche des plus courts chemins
  4. DLe tri de nombres
5.Moyen

Comment trouve-t-on la clé minimale dans un arbre binaire de recherche ?

  1. AOn suit les enfants gauches depuis la racine jusqu'à ce qu'il n'y en ait plus
  2. BOn suit les enfants droits depuis la racine jusqu'à ce qu'il n'y en ait plus
  3. COn visite toutes les feuilles et on les compare
  4. DOn regarde uniquement la racine
6.Moyen

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

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

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

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

L'insertion d'une clé dans un arbre AVL rend le sous-arbre gauche d'un nœud trop haut, et la nouvelle clé est allée dans le sous-arbre gauche de son enfant gauche (cas gauche-gauche). Quelle correction applique-t-on ?

  1. AUne rotation à gauche sur l'enfant, puis une rotation à droite sur le nœud
  2. BUn recoloriage du nœud et de son enfant
  3. CUne rotation simple à droite sur le nœud déséquilibré
  4. DUne rotation simple à gauche sur le nœud déséquilibré

Corrigé

  1. 1. A · Un graphe dans lequel chaque arête a une valeur numérique, comme un coût ou une distance
  2. 2. A · Pile (stack)
  3. 3. D · Des nœuds qui ont le même parent
  4. 4. B · Les recherches par préfixe, comme l'autocomplétion
  5. 5. A · On suit les enfants gauches depuis la racine jusqu'à ce qu'il n'y en ait plus
  6. 6. B · À simplifier le code en supprimant les cas particuliers en tête ou en queue
  7. 7. D · Toutes les feuilles sont à la même profondeur
  8. 8. C · Une rotation simple à droite sur le nœud déséquilibré

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