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

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

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

Quelle est la principale différence entre un tableau statique et un tableau dynamique ?

  1. AUn 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. BUn tableau statique offre un accès par indice plus lent
  3. CUn tableau dynamique peut grandir en passant à un bloc de mémoire plus grand
  4. DUn tableau statique ne peut stocker que des nombres
3.Facile

Dans une liste simplement chaînée, chaque nœud contient :

  1. ADes données et un indice
  2. BDes données et une référence vers le nœud suivant
  3. CUniquement des données
  4. DDes données et des références vers tous les autres nœuds
4.Moyen

Quel type abstrait de données l'algorithme de Dijkstra utilise-t-il pour choisir le prochain sommet à traiter ?

  1. AUne pile
  2. BUne file de priorité min
  3. CUne file FIFO
  4. DUn ensemble sans ordre
5.Moyen

Quelle méthode de résolution des collisions stocke les clés en collision dans une liste au sein du même compartiment ?

  1. ALe double hachage (double hashing)
  2. BLe sondage linéaire (linear probing)
  3. CLe chaînage séparé (separate chaining)
  4. DLe sondage quadratique (quadratic probing)
6.Moyen

Combien de temps prend la recherche d'un mot de longueur L dans un trie à alphabet fixe ?

  1. AO(L), quel que soit le nombre de mots stockés
  2. BO(L × n)
  3. CO(log n), où n est le nombre de mots
  4. DO(n), où n est le nombre de mots
7.Difficile

Un arbre de segments (segment tree) est généralement utilisé pour :

  1. ATrier des chaînes par ordre alphabétique en stockant chaque préfixe dans un nœud distinct de l'arbre
  2. BRépondre à des requêtes sur intervalles (comme des sommes d'intervalles) et à des mises à jour en O(log n)
  3. CStocker les arêtes d'un graphe
  4. DImplémenter une pile
8.Difficile

Quels sont les coûts en temps et en espace supplémentaire de l'inversion sur place d'une liste simplement chaînée ?

  1. AO(n) en temps et O(n) en espace supplémentaire
  2. BO(1) en temps et O(1) en espace supplémentaire
  3. CO(n log n) en temps et O(1) en espace supplémentaire
  4. DO(n) en temps et O(1) en espace supplémentaire

Corrigé

  1. 1. A · Elle associe une clé à un indice de la table
  2. 2. C · Un tableau dynamique peut grandir en passant à un bloc de mémoire plus grand
  3. 3. B · Des données et une référence vers le nœud suivant
  4. 4. B · Une file de priorité min
  5. 5. C · Le chaînage séparé (separate chaining)
  6. 6. A · O(L), quel que soit le nombre de mots stockés
  7. 7. B · Répondre à des requêtes sur intervalles (comme des sommes d'intervalles) et à des mises à jour en O(log n)
  8. 8. D · O(n) en temps et O(1) en espace supplémentaire

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