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

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 d'enfants de la racine
  4. DLe nombre de feuilles de l'arbre
2.Facile

Comment s'appelle l'opération de file qui retire l'élément situé à l'avant ?

  1. AInsert (insérer)
  2. BDequeue (défiler)
  3. CEnqueue (enfiler)
  4. DPush (empiler)
3.Facile

Dans quel ordre un parcours préfixe (preorder) d'un arbre binaire visite-t-il les nœuds ?

  1. ANiveau par niveau en partant du haut
  2. BLe nœud, puis le sous-arbre gauche, puis le sous-arbre droit
  3. CLe sous-arbre gauche, puis le sous-arbre droit, puis le nœud
  4. DLe sous-arbre gauche, puis le nœud, puis le sous-arbre droit
4.Moyen

Quelle est la complexité temporelle de la recherche d'une clé dans un arbre binaire de recherche équilibré ?

  1. AO(log n)
  2. BO(n)
  3. CO(1)
  4. DO(n log n)
5.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 pile
  2. BUne table de hachage
  3. CUn arbre binaire de recherche équilibré
  4. DUne liste chaînée non triée
6.Moyen

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

  1. AIl n'y a pas de maximum
  2. B0,5
  3. C1
  4. D2
7.Difficile

Pourquoi les arbres B (B-trees) sont-ils utilisés dans les bases de données et les systèmes de fichiers ?

  1. AIls stockent les données sans les trier
  2. BIls utilisent moins de mémoire que n'importe quel tableau, si bien que tout l'index tient toujours en mémoire centrale
  3. CLeur facteur de branchement élevé maintient l'arbre peu profond, ce qui réduit les lectures disque lentes
  4. DIls n'ont pas besoin de rééquilibrage
8.Difficile

Pourquoi les bases de données utilisent-elles souvent des arbres B+ plutôt que de simples B-arbres pour leurs index ?

  1. ALes arbres B+ utilisent des nœuds internes binaires, ce qui réduit le nombre de lectures sur disque
  2. BTous les enregistrements sont dans des feuilles chaînées, ce qui rend les parcours d'intervalle efficaces
  3. CLes arbres B+ n'ont pas besoin d'être équilibrés
  4. DLes arbres B+ ne stockent les données que dans la racine

Corrigé

  1. 1. B · Le nombre d'arêtes du plus long chemin de la racine à une feuille
  2. 2. B · Dequeue (défiler)
  3. 3. B · Le nœud, puis le sous-arbre gauche, puis le sous-arbre droit
  4. 4. A · O(log n)
  5. 5. C · Un arbre binaire de recherche équilibré
  6. 6. C · 1
  7. 7. C · Leur facteur de branchement élevé maintient l'arbre peu profond, ce qui réduit les lectures disque lentes
  8. 8. B · Tous les enregistrements sont dans des feuilles chaînées, ce qui rend les parcours d'intervalle efficaces

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