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 « premier entré, premier sorti » (FIFO) ?

  1. ATas (heap)
  2. BFile (queue)
  3. CPile (stack)
  4. DArbre binaire
2.Facile

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

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

Qu'est-ce qu'un graphe orienté ?

  1. AUn graphe qui n'a pas de cycle
  2. BUn graphe dans lequel chaque paire de sommets distincts est reliée par une arête
  3. CUn graphe dont toutes les arêtes ont un poids
  4. DUn graphe dont les arêtes ont une direction d'un sommet vers un autre
4.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. AUn tableau trié
  2. BUne liste doublement chaînée
  3. CUne liste simplement chaînée
  4. DUn tableau dynamique
5.Moyen

Dans une table de hachage à adressage ouvert, quel est le facteur de charge maximal possible ?

  1. A1
  2. B2
  3. CIl n'y a pas de maximum
  4. D0,5
6.Moyen

Quelle structure de données utilise-t-on pour vérifier si les parenthèses de "{[()]}" sont équilibrées ?

  1. AUne file
  2. BUne pile
  3. CUne table de hachage
  4. DUn arbre binaire de recherche
7.Difficile

Pour qu'une table de hachage fonctionne correctement, quelle règle le hachage et l'égalité doivent-ils respecter ?

  1. ADes clés différentes doivent avoir des valeurs de hachage différentes
  2. BLes valeurs de hachage doivent être des nombres premiers
  3. CDes valeurs de hachage égales impliquent des clés égales
  4. DDes clés égales doivent avoir des valeurs de hachage égales
8.Difficile

Un tableau dynamique double de taille lorsqu'il est plein. Pourquoi de nombreuses implémentations ne le réduisent-elles que lorsqu'il est rempli au quart, et non à moitié ?

  1. APour garder le tableau trié
  2. BParce que diviser par deux à la moitié ferait perdre des éléments
  3. CParce que l'allocateur de mémoire ne peut libérer la mémoire que par quarts de bloc
  4. DPour éviter des redimensionnements répétés lorsque des push et des pop alternent près de la limite

Corrigé

  1. 1. B · File (queue)
  2. 2. B · Le nombre d'arêtes du plus long chemin de la racine à une feuille
  3. 3. D · Un graphe dont les arêtes ont une direction d'un sommet vers un autre
  4. 4. B · Une liste doublement chaînée
  5. 5. A · 1
  6. 6. B · Une pile
  7. 7. D · Des clés égales doivent avoir des valeurs de hachage égales
  8. 8. D · Pour éviter des redimensionnements répétés lorsque des push et des pop alternent près de la limite

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