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. ALa suppression de l'élément de tête
  2. BL'accès à l'élément d'indice i
  3. CLa lecture du premier élément
  4. DL'insertion en tête
2.Facile

Comment s'appelle l'opération de pile qui ajoute un élément au sommet ?

  1. APeek (consulter)
  2. BPop (dépiler)
  3. CPush (empiler)
  4. DEnqueue (enfiler)
3.Facile

Un graphe est constitué de :

  1. ASommets (nœuds) reliés par des arêtes
  2. BLignes et colonnes
  3. CUniquement une racine et des feuilles
  4. DUniquement des clés et des hachages
4.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 0
  2. BÀ l'indice 6
  3. CÀ l'indice 3
  4. DÀ l'indice 4
5.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. AUne liste simplement chaînée
  2. BUn tableau dynamique
  3. CUn tableau trié
  4. DUne liste doublement chaînée
6.Moyen

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

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

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

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

Quelle affirmation sur le tri par tas (heapsort) est correcte ?

  1. AIl nécessite un arbre binaire de recherche comme stockage supplémentaire, donc il utilise O(n) de mémoire en plus
  2. BIl s'exécute en O(n) sur toute entrée
  3. CIl est stable et nécessite O(n) mémoire supplémentaire
  4. DIl trie sur place en O(n log n) dans le pire cas, mais n'est pas stable

Corrigé

  1. 1. B · L'accès à l'élément d'indice i
  2. 2. C · Push (empiler)
  3. 3. A · Sommets (nœuds) reliés par des arêtes
  4. 4. D · À l'indice 4
  5. 5. D · Une liste doublement chaînée
  6. 6. C · O(L), quel que soit le nombre de mots stockés
  7. 7. C · Tout chemin d'un nœud vers ses feuilles descendantes contient le même nombre de nœuds noirs
  8. 8. D · Il trie sur place en O(n log n) dans le pire cas, mais n'est pas stable

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