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

Un graphe est constitué de :

  1. ASommets (nœuds) reliés par des arêtes
  2. BUniquement des clés et des hachages
  3. CUniquement une racine et des feuilles
  4. DLignes et colonnes
2.Facile

Combien d'arêtes possède un arbre à n nœuds ?

  1. An + 1
  2. B2n
  3. Cn − 1
  4. Dn
3.Facile

Qu'est-ce que la propriété de tas max ?

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

Que se passe-t-il lorsqu'une table de hachage est rehachée après que son facteur de charge a dépassé un seuil ?

  1. AUne table plus grande est allouée et chaque clé y est réinsérée
  2. BLes clés existantes sont triées sur place
  3. CSeules les clés en collision sont déplacées dans une nouvelle liste de débordement à la fin de la table
  4. DLes clés les plus anciennes sont supprimées pour faire de la place
5.Moyen

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

  1. AUn arbre binaire de recherche
  2. BUne pile
  3. CUne file
  4. DUne table de hachage
6.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 croissant
  3. CL'ordre d'insertion
  4. DL'ordre par niveaux
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 stockent les données sans les trier
  3. CIls utilisent moins de mémoire que n'importe quel tableau, si bien que tout l'index tient toujours en mémoire centrale
  4. DIls n'ont pas besoin de rééquilibrage
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 réponses toujours exactes
  3. CDes faux négatifs possibles mais aucun faux positif
  4. DDes réponses uniquement pour des nombres

Corrigé

  1. 1. A · Sommets (nœuds) reliés par des arêtes
  2. 2. C · n − 1
  3. 3. C · La clé de chaque parent est supérieure ou égale aux clés de ses enfants
  4. 4. A · Une table plus grande est allouée et chaque clé y est réinsérée
  5. 5. B · Une pile
  6. 6. B · L'ordre croissant
  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.