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 structure de données utilise-t-on pour effectuer un parcours en largeur (par niveaux) d'un arbre ?

  1. AUne file
  2. BUne table de hachage
  3. CUne file de priorité
  4. DUne pile
2.Facile

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

  1. ATas (heap)
  2. BFile (queue)
  3. CArbre binaire
  4. DPile (stack)
3.Facile

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

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

Une application a besoin de recherches rapides, mais aussi de lister les clés dans l'ordre trié et de répondre à des requêtes par intervalle. Quelle structure convient le mieux ?

  1. AUne table de hachage
  2. BUn arbre binaire de recherche équilibré
  3. CUne liste chaînée non triée
  4. DUne pile
5.Moyen

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

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

Quelle quantité de mémoire une matrice d'adjacence utilise-t-elle pour un graphe à V sommets ?

  1. AO(V²)
  2. BO(log V)
  3. CO(V + E)
  4. DO(E)
7.Difficile

Quelle garantie les règles des arbres rouge-noir donnent-elles sur la hauteur d'un arbre à n clés ?

  1. ALa hauteur est au plus log2 n + 1
  2. BLa hauteur vaut exactement log2 n
  3. CLa hauteur est au plus 2 log2(n + 1)
  4. DLa hauteur est au plus n / 2
8.Difficile

La suppression d'un nœud ayant deux enfants dans un arbre binaire de recherche se fait généralement en :

  1. AReconstruisant de zéro le sous-arbre situé en dessous et en réinsérant toutes les clés qu'il contenait
  2. BSupprimant tout le sous-arbre
  3. CL'échangeant avec la racine
  4. DLe remplaçant par son successeur infixe (ou prédécesseur) puis en supprimant ce nœud

Corrigé

  1. 1. A · Une file
  2. 2. B · File (queue)
  3. 3. D · Des données et une référence vers le nœud suivant
  4. 4. B · Un arbre binaire de recherche équilibré
  5. 5. B · On suit les enfants gauches depuis la racine jusqu'à ce qu'il n'y en ait plus
  6. 6. A · O(V²)
  7. 7. C · La hauteur est au plus 2 log2(n + 1)
  8. 8. D · Le remplaçant par son successeur infixe (ou prédécesseur) puis en supprimant ce nœud

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