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 est la principale différence entre un tableau statique et un tableau dynamique ?

  1. AUn tableau dynamique peut grandir en passant à un bloc de mémoire plus grand
  2. BUn tableau dynamique stocke ses éléments dans des nœuds chaînés, ce qui lui permet de grandir un élément à la fois
  3. CUn tableau statique offre un accès par indice plus lent
  4. DUn tableau statique ne peut stocker que des nombres
2.Facile

Quelle opération est lente dans un tableau mais rapide en tête d'une liste chaînée ?

  1. AL'accès au 5e élément
  2. BL'insertion au début
  3. CLa lecture du dernier élément par son indice
  4. DLe calcul de la longueur d'un tableau de taille fixe
3.Facile

Qu'est-ce que le facteur de charge d'une table de hachage ?

  1. ALe nombre de collisions survenues jusqu'ici
  2. BLe nombre de compartiments divisé par la longueur moyenne des clés stockées
  3. CLe temps nécessaire pour charger la table depuis le disque
  4. DLe nombre d'éléments stockés divisé par le nombre de compartiments
4.Moyen

Comment trouve-t-on la clé minimale dans un arbre binaire de recherche ?

  1. AOn suit les enfants gauches depuis la racine jusqu'à ce qu'il n'y en ait plus
  2. BOn regarde uniquement la racine
  3. COn visite toutes les feuilles et on les compare
  4. DOn suit les enfants droits depuis la racine jusqu'à ce qu'il n'y en ait plus
5.Moyen

Quelle est la hauteur, dans le pire des cas, d'un arbre binaire de recherche à n nœuds si les clés sont insérées dans l'ordre trié ?

  1. A√n
  2. Blog₂ n
  3. Cn (il devient une liste chaînée)
  4. D1
6.Moyen

Une file est implémentée avec deux piles : on empile sur une pile « in » et on dépile depuis une pile « out », remplie à partir de « in » lorsqu'elle est vide. Quel est le coût amorti par opération ?

  1. AO(n²)
  2. BO(1)
  3. CO(log n)
  4. DO(n)
7.Difficile

Dans le BST de racine 50, avec le sous-arbre gauche 30 (enfants 20, 40) et le sous-arbre droit 70 (enfants 60, 80), on supprime la racine en utilisant le successeur infixe. Quelle clé devient la nouvelle racine ?

  1. A40
  2. B80
  3. C70
  4. D60
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. BLes arbres B+ ne stockent les données que dans la racine
  3. CLes arbres B+ n'ont pas besoin d'être équilibrés
  4. DTous les enregistrements sont dans des feuilles chaînées, ce qui rend les parcours d'intervalle efficaces

Corrigé

  1. 1. A · Un tableau dynamique peut grandir en passant à un bloc de mémoire plus grand
  2. 2. B · L'insertion au début
  3. 3. D · Le nombre d'éléments stockés divisé par le nombre de compartiments
  4. 4. A · On suit les enfants gauches depuis la racine jusqu'à ce qu'il n'y en ait plus
  5. 5. C · n (il devient une liste chaînée)
  6. 6. B · O(1)
  7. 7. D · 60
  8. 8. D · 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.