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 la racine d'un arbre ?

  1. ALe nœud ayant la plus grande valeur
  2. BUn nœud sans enfant
  3. CLe nœud situé tout en haut, sans parent
  4. DN'importe quel nœud au milieu
2.Facile

Quelle structure de données fonctionne selon le principe « dernier entré, premier sorti » (LIFO) ?

  1. APile (stack)
  2. BListe chaînée
  3. CTable de hachage
  4. DFile (queue)
3.Facile

Comment les éléments d'un tableau sont-ils stockés en mémoire ?

  1. ADans un arbre de pages mémoire
  2. BDans un seul bloc contigu, les uns à la suite des autres
  3. CDe façon dispersée, reliés par des pointeurs
  4. DÀ des emplacements aléatoires choisis par un hachage
4.Moyen

Un réseau routier compte 100,000 carrefours, chacun relié à environ 4 autres. Quelle représentation est la plus adaptée ?

  1. AUne liste d'adjacence
  2. BUn unique tableau trié de sommets
  3. CUne matrice d'adjacence
  4. DUn tas binaire d'arêtes
5.Moyen

À quoi sert un nœud sentinelle (factice) dans une liste chaînée ?

  1. AÀ empêcher la liste de dépasser un nombre maximal fixe de nœuds
  2. BÀ rendre la liste triée
  3. CÀ simplifier le code en supprimant les cas particuliers en tête ou en queue
  4. DÀ stocker le nombre d'éléments
6.Moyen

Une application a besoin de recherches rapides, mais aussi de lister les clés dans l'ordre trié et de répondre à des requêtes par intervalle. Quelle structure convient le mieux ?

  1. AUn arbre binaire de recherche équilibré
  2. BUne pile
  3. CUne table de hachage
  4. DUne liste chaînée non triée
7.Difficile

Quel est le temps d'exécution d'un parcours en largeur sur un graphe à V sommets stocké sous forme de matrice d'adjacence ?

  1. AO(V²)
  2. BO(V + E)
  3. CO(V)
  4. DO(E log V)
8.Difficile

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

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

Corrigé

  1. 1. C · Le nœud situé tout en haut, sans parent
  2. 2. A · Pile (stack)
  3. 3. B · Dans un seul bloc contigu, les uns à la suite des autres
  4. 4. A · Une liste d'adjacence
  5. 5. C · À simplifier le code en supprimant les cas particuliers en tête ou en queue
  6. 6. A · Un arbre binaire de recherche équilibré
  7. 7. A · O(V²)
  8. 8. D · 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.