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

Dans une table de hachage, qu'est-ce qu'une collision ?

  1. ADeux clés différentes sont associées au même indice
  2. BLa table manque de mémoire
  3. CDeux clés égales sont stockées deux fois
  4. DUne clé ne peut pas du tout être hachée
2.Facile

Comment les éléments d'un tableau sont-ils stockés en mémoire ?

  1. ADans un arbre de pages mémoire
  2. BDans un seul bloc contigu, les uns à la suite des autres
  3. CÀ des emplacements aléatoires choisis par un hachage
  4. DDe façon dispersée, reliés par des pointeurs
3.Facile

Quelle est la caractéristique essentielle d'un ensemble en tant que type abstrait de données ?

  1. AIl stocke des paires clé–valeur
  2. BIl stocke des éléments sans doublons
  3. CIl stocke des éléments dans l'ordre trié
  4. DIl ne permet l'accès qu'à une seule extrémité
4.Moyen

Un parcours infixe (in-order) d'un arbre binaire de recherche visite les clés dans :

  1. AL'ordre par niveaux
  2. BToujours l'ordre décroissant
  3. CL'ordre d'insertion
  4. DL'ordre croissant
5.Moyen

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

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

Combien de temps faut-il pour vérifier si l'arête (u, v) existe avec une matrice d'adjacence ?

  1. AO(1)
  2. BO(E)
  3. CO(V)
  4. DO(log V)
7.Difficile

Quelle propriété un arbre rouge-noir doit-il respecter ?

  1. ATout chemin d'un nœud vers ses feuilles descendantes contient le même nombre de nœuds noirs
  2. BChaque nœud doit être rouge
  3. CTout nœud rouge doit avoir des enfants rouges, si bien que les nœuds rouges forment toujours des chaînes ininterrompues jusqu'aux feuilles
  4. DLa racine doit être rouge
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 éviter des redimensionnements répétés lorsque des push et des pop alternent près de la limite
  2. BParce que l'allocateur de mémoire ne peut libérer la mémoire que par quarts de bloc
  3. CPour garder le tableau trié
  4. DParce que diviser par deux à la moitié ferait perdre des éléments

Corrigé

  1. 1. A · Deux clés différentes sont associées au même indice
  2. 2. B · Dans un seul bloc contigu, les uns à la suite des autres
  3. 3. B · Il stocke des éléments sans doublons
  4. 4. D · L'ordre croissant
  5. 5. C · On suit les enfants gauches depuis la racine jusqu'à ce qu'il n'y en ait plus
  6. 6. A · O(1)
  7. 7. A · Tout chemin d'un nœud vers ses feuilles descendantes contient le même nombre de nœuds noirs
  8. 8. A · 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.