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 un arbre, que sont des nœuds frères ?

  1. ADes nœuds de même profondeur dans des sous-arbres différents
  2. BDes nœuds qui ont le même parent
  3. CDes nœuds qui n'ont pas d'enfant
  4. DUn nœud et son parent
2.Facile

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

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

Quelle structure de données fonctionne selon le principe « dernier entré, premier sorti » (LIFO) ?

  1. APile (stack)
  2. BListe chaînée
  3. CTable de hachage
  4. DFile (queue)
4.Moyen

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

  1. ALes deux sous-arbres de chaque nœud contiennent exactement le même nombre de nœuds
  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. DToutes les feuilles sont exactement à la même profondeur
5.Moyen

Quelle est la valeur de l'expression postfixée 3 4 + 2 * ?

  1. A14
  2. B10
  3. C11
  4. D24
6.Moyen

Dans une file circulaire stockée dans un tableau de capacité n, comment calcule-t-on la position suivant l'indice i ?

  1. A(i − 1) mod n
  2. Bi + 1
  3. C(i + 1) mod n
  4. D2i + 1
7.Difficile

Quelle garantie les règles des arbres rouge-noir donnent-elles sur la hauteur d'un arbre à n clés ?

  1. ALa hauteur est au plus 2 log2(n + 1)
  2. BLa hauteur vaut exactement log2 n
  3. CLa hauteur est au plus log2 n + 1
  4. DLa hauteur est au plus n / 2
8.Difficile

Pourquoi ne peut-on pas simplement supprimer des éléments d'un filtre de Bloom standard en remettant leurs bits à zéro ?

  1. ALes bits d'un filtre de Bloom ne peuvent pas être modifiés après sa création
  2. BCes bits peuvent aussi appartenir à d'autres éléments, ce qui provoquerait des faux négatifs
  3. CLa suppression porterait le taux de faux positifs à 100%
  4. DLes filtres de Bloom stockent les éléments complets, qui sont introuvables une fois hachés

Corrigé

  1. 1. B · Des nœuds qui ont le même parent
  2. 2. B · Le nombre d'éléments stockés divisé par le nombre de compartiments
  3. 3. A · Pile (stack)
  4. 4. C · Les hauteurs des sous-arbres gauche et droit diffèrent d'au plus 1
  5. 5. A · 14
  6. 6. C · (i + 1) mod n
  7. 7. A · La hauteur est au plus 2 log2(n + 1)
  8. 8. B · Ces bits peuvent aussi appartenir à d'autres éléments, ce qui provoquerait des faux négatifs

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