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 est la principale différence entre un tableau statique et un tableau dynamique ?

  1. AUn tableau statique ne peut stocker que des nombres
  2. BUn tableau dynamique peut grandir en passant à un bloc de mémoire plus grand
  3. CUn tableau statique offre un accès par indice plus lent
  4. DUn tableau dynamique stocke ses éléments dans des nœuds chaînés, ce qui lui permet de grandir un élément à la fois
2.Facile

Quelle opération est en O(1) pour un tableau mais en O(n) pour une liste simplement chaînée ?

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

Qu'est-ce qu'un graphe orienté ?

  1. AUn graphe qui n'a pas de cycle
  2. BUn graphe dont toutes les arêtes ont un poids
  3. CUn graphe dont les arêtes ont une direction d'un sommet vers un autre
  4. DUn graphe dans lequel chaque paire de sommets distincts est reliée par une arête
4.Moyen

Les arbres AVL et les arbres rouge-noir garantissent :

  1. AQue les clés sont stockées dans l'ordre d'insertion
  2. BQu'aucun nœud n'a deux enfants
  3. CUne recherche en temps constant dans tous les cas
  4. DUne hauteur en O(log n) grâce au rééquilibrage
5.Moyen

Une table de hachage de taille 7 utilise h(k) = k mod 7 et le sondage linéaire. Après l'insertion de 10, où est stocké 17 ?

  1. AÀ l'indice 4
  2. BÀ l'indice 6
  3. CÀ l'indice 3
  4. DÀ l'indice 0
6.Moyen

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

  1. AUne file
  2. BUniquement une table de hachage
  3. CUn tas
  4. DUne pile
7.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 tas min reconstruit pour chaque fenêtre
  2. BUn tableau trié mis à jour par décalage
  3. CUne liste simplement chaînée des éléments de la fenêtre
  4. DUn deque contenant des indices par ordre décroissant de valeur
8.Difficile

Quel problème du sondage linéaire le double hachage réduit-il principalement ?

  1. ALe regroupement primaire (primary clustering), où se forment de longues suites de cases occupées
  2. BLe coût en O(n) de la lecture de la valeur d'une clé
  3. CLe besoin d'une fonction de hachage
  4. DLe besoin de stocker les clés dans la table

Corrigé

  1. 1. B · Un tableau dynamique peut grandir en passant à un bloc de mémoire plus grand
  2. 2. C · L'accès à l'élément d'indice i
  3. 3. C · Un graphe dont les arêtes ont une direction d'un sommet vers un autre
  4. 4. D · Une hauteur en O(log n) grâce au rééquilibrage
  5. 5. A · À l'indice 4
  6. 6. D · Une pile
  7. 7. D · Un deque contenant des indices par ordre décroissant de valeur
  8. 8. A · Le regroupement primaire (primary clustering), où se forment de longues suites de cases occupées

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