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 qu'un deque (file à double extrémité) ?

  1. AUne file qui ne permet la suppression qu'à l'arrière
  2. BUne file triée par priorité
  3. CDeux files distinctes partageant un même tableau
  4. DUne structure qui permet l'insertion et la suppression aux deux extrémités
2.Facile

Dans un arbre, que sont des nœuds frères ?

  1. ADes nœuds de même profondeur dans des sous-arbres différents
  2. BUn nœud et son parent
  3. CDes nœuds qui n'ont pas d'enfant
  4. DDes nœuds qui ont le même parent
3.Facile

Dans une table de hachage, qu'est-ce qu'une collision ?

  1. AUne clé ne peut pas du tout être hachée
  2. BDeux clés différentes sont associées au même indice
  3. CDeux clés égales sont stockées deux fois
  4. DLa table manque de mémoire
4.Moyen

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

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

Pourquoi un tas binaire peut-il être stocké dans un tableau sans aucun pointeur ?

  1. AToutes les clés d'un tas sont égales
  2. BLes tableaux maintiennent automatiquement les clés triées, donc aucun pointeur n'est nécessaire
  3. CC'est un arbre binaire complet, donc les positions suivent des formules d'indice simples
  4. DLes tas ne contiennent jamais plus de 100 éléments
6.Moyen

Dans une table de hachage à adressage ouvert, quel est le facteur de charge maximal possible ?

  1. AIl n'y a pas de maximum
  2. B2
  3. C1
  4. D0,5
7.Difficile

L'algorithme de Kahn pour le tri topologique retire répétitivement les sommets de degré entrant 0. Quelle structure contient ces sommets ?

  1. AUne pile de toutes les arêtes visitées
  2. BUn tas max ordonné par degré sortant
  3. CUne file (ou toute collection) des sommets de degré entrant 0
  4. DUne matrice d'adjacence indiquant quels sommets ont déjà été retirés
8.Difficile

Les clés 5, 3, 8, 1 sont insérées dans cet ordre dans un tas binaire min vide stocké dans un tableau. Quel est le tableau final ?

  1. A[1, 3, 8, 5]
  2. B[1, 3, 5, 8]
  3. C[3, 1, 8, 5]
  4. D[1, 5, 8, 3]

Corrigé

  1. 1. D · Une structure qui permet l'insertion et la suppression aux deux extrémités
  2. 2. D · Des nœuds qui ont le même parent
  3. 3. B · Deux clés différentes sont associées au même indice
  4. 4. A · À simplifier le code en supprimant les cas particuliers en tête ou en queue
  5. 5. C · C'est un arbre binaire complet, donc les positions suivent des formules d'indice simples
  6. 6. C · 1
  7. 7. C · Une file (ou toute collection) des sommets de degré entrant 0
  8. 8. A · [1, 3, 8, 5]

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