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

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

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

Que fait une fonction de hachage dans une table de hachage ?

  1. AElle chiffre les valeurs de la table
  2. BElle associe une clé à un indice de la table
  3. CElle trie les clés de la table
  4. DElle compte le nombre de clés stockées
3.Facile

Que fait l'opération peek (ou top) sur une pile ?

  1. AElle retire tous les éléments de la pile
  2. BElle renvoie l'élément du sommet sans le retirer
  3. CElle retire l'élément du sommet et le renvoie
  4. DElle renvoie l'élément du fond de la pile
4.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(n²)
  4. DO(log n)
5.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. ALes clés existantes sont triées sur place
  2. BUne table plus grande est allouée et chaque clé y est réinsérée
  3. CLes clés les plus anciennes sont supprimées pour faire de la place
  4. DSeules les clés en collision sont déplacées dans une nouvelle liste de débordement à la fin de la table
6.Moyen

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

  1. AUne file
  2. BUne table de hachage
  3. CUn arbre binaire de recherche
  4. DUne pile
7.Difficile

Comment détecter si une liste simplement chaînée contient un cycle avec O(1) mémoire supplémentaire ?

  1. AStocker chaque nœud visité dans un ensemble haché
  2. BCompter les nœuds jusqu'à dépasser le champ de longueur de la liste
  3. CAvancer un pointeur d'un pas et un autre de deux pas, et vérifier s'ils se rencontrent
  4. DTrier la liste et chercher des doublons
8.Difficile

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

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

Corrigé

  1. 1. A · Dans un seul bloc contigu, les uns à la suite des autres
  2. 2. B · Elle associe une clé à un indice de la table
  3. 3. B · Elle renvoie l'élément du sommet sans le retirer
  4. 4. B · O(1)
  5. 5. B · Une table plus grande est allouée et chaque clé y est réinsérée
  6. 6. D · Une pile
  7. 7. C · Avancer un pointeur d'un pas et un autre de deux pas, et vérifier s'ils se rencontrent
  8. 8. D · Des faux positifs possibles mais aucun faux négatif

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