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 que la propriété de tas max ?

  1. ALa clé de chaque parent est supérieure ou égale aux clés de ses enfants
  2. BLa clé de chaque enfant gauche est supérieure ou égale à celle de son frère droit
  3. CLes clés sont triées de gauche à droite
  4. DToutes les feuilles contiennent la clé maximale
2.Facile

Quelle structure de données utilise-t-on pour effectuer un parcours en largeur (par niveaux) d'un arbre ?

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

La profondeur d'un nœud dans un arbre est :

  1. ALe nombre d'arêtes de ce nœud jusqu'à la feuille la plus profonde
  2. BLe nombre d'enfants de ce nœud
  3. CLe nombre d'arêtes de la racine jusqu'à ce nœud
  4. DLe nombre de nœuds de son sous-arbre
4.Moyen

Combien de temps prend la recherche d'un mot de longueur L dans un trie à alphabet fixe ?

  1. AO(n), où n est le nombre de mots
  2. BO(log n), où n est le nombre de mots
  3. CO(L × n)
  4. DO(L), quel que soit le nombre de mots stockés
5.Moyen

Les arbres AVL et les arbres rouge-noir garantissent :

  1. AUne recherche en temps constant dans tous les cas
  2. BQu'aucun nœud n'a deux enfants
  3. CUne hauteur en O(log n) grâce au rééquilibrage
  4. DQue les clés sont stockées dans l'ordre d'insertion
6.Moyen

Quelle condition d'équilibre un arbre AVL maintient-il en chaque nœud ?

  1. AToutes les feuilles sont exactement à la même profondeur
  2. BChaque nœud est colorié en rouge ou en noir
  3. CLes hauteurs des sous-arbres gauche et droit diffèrent d'au plus 1
  4. DLes deux sous-arbres de chaque nœud contiennent exactement le même nombre de nœuds
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. ALeur facteur de branchement élevé maintient l'arbre peu profond, ce qui réduit les lectures disque lentes
  2. BIls n'ont pas besoin de rééquilibrage
  3. CIls stockent les données sans les trier
  4. DIls utilisent moins de mémoire que n'importe quel tableau, si bien que tout l'index tient toujours en mémoire centrale
8.Difficile

Un filtre de Bloom peut répondre à la question « cet élément appartient-il à l'ensemble ? » avec :

  1. ADes faux positifs possibles mais aucun faux négatif
  2. BDes faux négatifs possibles mais aucun faux positif
  3. CDes réponses toujours exactes
  4. DDes réponses uniquement pour des nombres

Corrigé

  1. 1. A · La clé de chaque parent est supérieure ou égale aux clés de ses enfants
  2. 2. C · Une file
  3. 3. C · Le nombre d'arêtes de la racine jusqu'à ce nœud
  4. 4. D · O(L), quel que soit le nombre de mots stockés
  5. 5. C · Une hauteur en O(log n) grâce au rééquilibrage
  6. 6. C · Les hauteurs des sous-arbres gauche et droit diffèrent d'au plus 1
  7. 7. A · Leur facteur de branchement élevé maintient l'arbre peu profond, ce qui réduit les lectures disque lentes
  8. 8. A · Des faux positifs possibles mais aucun faux négatif

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