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 fonctionne selon le principe « dernier entré, premier sorti » (LIFO) ?

  1. ATable de hachage
  2. BListe chaînée
  3. CFile (queue)
  4. DPile (stack)
2.Facile

Que fait une fonction de hachage dans une table de hachage ?

  1. AElle chiffre les valeurs de la table
  2. BElle compte le nombre de clés stockées
  3. CElle associe une clé à un indice de la table
  4. DElle trie les clés de la table
3.Facile

La hauteur d'un arbre est couramment définie comme :

  1. ALe nombre d'arêtes du plus long chemin de la racine à une feuille
  2. BLe nombre de feuilles de l'arbre
  3. CLe nombre d'enfants de la racine
  4. DLe nombre total de nœuds de l'arbre, en comptant la racine et chaque feuille
4.Moyen

Un parcours infixe (in-order) d'un arbre binaire de recherche visite les clés dans :

  1. AToujours l'ordre décroissant
  2. BL'ordre d'insertion
  3. CL'ordre croissant
  4. DL'ordre par niveaux
5.Moyen

Pourquoi le parcours d'un tableau est-il souvent bien plus rapide en pratique que celui d'une liste chaînée de même longueur ?

  1. ALes tableaux utilisent moins d'instructions pour comparer les valeurs
  2. BLes listes chaînées stockent toujours leurs éléments sur disque
  3. CLe parcours d'un tableau est en O(1) au total, alors que celui d'une liste chaînée est en O(n)
  4. DLes éléments d'un tableau sont contigus, ce qui exploite bien le cache du processeur
6.Moyen

Une table de hachage de taille 7 utilise h(k) = k mod 7 et le sondage linéaire. Après l'insertion de 10, où est stocké 17 ?

  1. AÀ l'indice 0
  2. BÀ l'indice 4
  3. CÀ l'indice 3
  4. DÀ l'indice 6
7.Difficile

Quelle structure de données permet un cache LRU (least recently used) avec get et put en O(1) ?

  1. AUne table de hachage combinée à une liste doublement chaînée
  2. BUniquement une pile
  3. CUniquement un arbre binaire de recherche
  4. DUn unique tableau trié
8.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 2 log2(n + 1)
  2. BLa hauteur est au plus n / 2
  3. CLa hauteur vaut exactement log2 n
  4. DLa hauteur est au plus log2 n + 1

Corrigé

  1. 1. D · Pile (stack)
  2. 2. C · Elle associe une clé à un indice de la table
  3. 3. A · Le nombre d'arêtes du plus long chemin de la racine à une feuille
  4. 4. C · L'ordre croissant
  5. 5. D · Les éléments d'un tableau sont contigus, ce qui exploite bien le cache du processeur
  6. 6. B · À l'indice 4
  7. 7. A · Une table de hachage combinée à une liste doublement chaînée
  8. 8. A · La hauteur est au plus 2 log2(n + 1)

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