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 opération est en O(1) pour un tableau mais en O(n) pour une liste simplement chaînée ?

  1. AL'accès à l'élément d'indice i
  2. BL'insertion en tête
  3. CLa suppression de l'élément de tête
  4. DLa lecture du premier élément
2.Facile

Comment s'appelle l'opération de file qui retire l'élément situé à l'avant ?

  1. ADequeue (défiler)
  2. BInsert (insérer)
  3. CEnqueue (enfiler)
  4. DPush (empiler)
3.Facile

Que stocke un dictionnaire (map) ?

  1. AUniquement des valeurs dans l'ordre d'insertion
  2. BDes paires clé–valeur à clés uniques
  3. CDes valeurs triées par taille
  4. DDes paires de clés égales
4.Moyen

Quelle structure de données est utilisée par le parcours en profondeur (DFS) dans sa version itérative ?

  1. AUn tas
  2. BUniquement une table de hachage
  3. CUne pile
  4. DUne file
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 est la complexité temporelle de la recherche d'une clé dans un arbre binaire de recherche équilibré ?

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

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

  1. ALa racine doit être rouge
  2. BTout chemin d'un nœud vers ses feuilles descendantes contient le même nombre de nœuds noirs
  3. CChaque nœud doit être rouge
  4. DTout nœud rouge doit avoir des enfants rouges, si bien que les nœuds rouges forment toujours des chaînes ininterrompues jusqu'aux feuilles
8.Difficile

Quel est le principal avantage d'une liste à enjambements (skip list) par rapport à une liste chaînée triée ?

  1. AElle n'utilise aucune mémoire supplémentaire
  2. BUne recherche en O(log n) en moyenne grâce à plusieurs niveaux de pointeurs avant
  3. CUne recherche en O(1) garantie, car chaque nœud stocke un pointeur vers tous les autres nœuds
  4. DElle stocke les clés sans ordre

Corrigé

  1. 1. A · L'accès à l'élément d'indice i
  2. 2. A · Dequeue (défiler)
  3. 3. B · Des paires clé–valeur à clés uniques
  4. 4. C · Une pile
  5. 5. B · Une table plus grande est allouée et chaque clé y est réinsérée
  6. 6. B · O(log n)
  7. 7. B · Tout chemin d'un nœud vers ses feuilles descendantes contient le même nombre de nœuds noirs
  8. 8. B · Une recherche en O(log n) en moyenne grâce à plusieurs niveaux de pointeurs avant

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