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

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

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

Dans quel ordre un parcours postfixe (postorder) d'un arbre binaire visite-t-il les nœuds ?

  1. ALe sous-arbre gauche, puis le nœud, puis le sous-arbre droit
  2. BLe nœud, puis le sous-arbre gauche, puis le sous-arbre droit
  3. CLe sous-arbre droit, puis le nœud, puis le sous-arbre gauche
  4. DLe sous-arbre gauche, puis le sous-arbre droit, puis le nœud
3.Facile

Quelle structure est généralement utilisée pour implémenter une file de priorité ?

  1. AUn tas (heap)
  2. BUne pile (stack)
  3. CUne liste simplement chaînée non ordonnée
  4. DUne chaîne de caractères
4.Moyen

Quelle quantité de mémoire une liste d'adjacence utilise-t-elle pour un graphe à V sommets et E arêtes ?

  1. AO(E²)
  2. BO(V²)
  3. CO(V + E)
  4. DO(V × E)
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. BLes clés les plus anciennes sont supprimées pour faire de la place
  3. CSeules les clés en collision sont déplacées dans une nouvelle liste de débordement à la fin de la table
  4. DUne table plus grande est allouée et chaque clé y est réinsérée
6.Moyen

Vous avez une référence vers un nœud au milieu d'une liste. Dans quelle liste pouvez-vous le supprimer en O(1) ?

  1. AUn tableau dynamique
  2. BUn tableau trié
  3. CUne liste doublement chaînée
  4. DUne liste simplement chaînée
7.Difficile

Un arbre de Fenwick (binary indexed tree) sur un tableau de n nombres permet quelles opérations en O(log n) ?

  1. ALes requêtes de sommes préfixes et les mises à jour d'un seul élément
  2. BLe tri du tableau et la recherche dichotomique
  3. CL'insertion d'éléments à n'importe quelle position
  4. DLa recherche de la médiane en O(1)
8.Difficile

Quelle structure permet de calculer le maximum de chaque fenêtre de taille k dans un tableau en O(n) au total ?

  1. AUn deque contenant des indices par ordre décroissant de valeur
  2. BUne liste simplement chaînée des éléments de la fenêtre
  3. CUn tableau trié mis à jour par décalage
  4. DUn tas min reconstruit pour chaque fenêtre

Corrigé

  1. 1. A · Le nombre d'éléments stockés divisé par le nombre de compartiments
  2. 2. D · Le sous-arbre gauche, puis le sous-arbre droit, puis le nœud
  3. 3. A · Un tas (heap)
  4. 4. C · O(V + E)
  5. 5. D · Une table plus grande est allouée et chaque clé y est réinsérée
  6. 6. C · Une liste doublement chaînée
  7. 7. A · Les requêtes de sommes préfixes et les mises à jour d'un seul élément
  8. 8. A · Un deque contenant des indices par ordre décroissant de valeur

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