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 le facteur de charge d'une table de hachage ?

  1. ALe nombre d'éléments stockés divisé par le nombre de compartiments
  2. BLe nombre de collisions survenues jusqu'ici
  3. CLe temps nécessaire pour charger la table depuis le disque
  4. DLe nombre de compartiments divisé par la longueur moyenne des clés stockées
2.Facile

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

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

Où se trouve le plus petit élément d'un tas binaire min ?

  1. AÀ la racine
  2. BDans une feuille quelconque, qu'il faut chercher
  3. CDans la feuille la plus à gauche
  4. DÀ la dernière position du tableau
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. BUn ensemble sans ordre
  3. CUne file de priorité min
  4. DUne file FIFO
5.Moyen

Combien de temps faut-il pour vérifier si l'arête (u, v) existe avec une matrice d'adjacence ?

  1. AO(1)
  2. BO(E)
  3. CO(log V)
  4. DO(V)
6.Moyen

Comment trouve-t-on la clé minimale dans un arbre binaire de recherche ?

  1. AOn suit les enfants gauches depuis la racine jusqu'à ce qu'il n'y en ait plus
  2. BOn regarde uniquement la racine
  3. COn suit les enfants droits depuis la racine jusqu'à ce qu'il n'y en ait plus
  4. DOn visite toutes les feuilles et on les compare
7.Difficile

Un tableau dynamique double de taille lorsqu'il est plein. Pourquoi de nombreuses implémentations ne le réduisent-elles que lorsqu'il est rempli au quart, et non à moitié ?

  1. AParce que l'allocateur de mémoire ne peut libérer la mémoire que par quarts de bloc
  2. BParce que diviser par deux à la moitié ferait perdre des éléments
  3. CPour éviter des redimensionnements répétés lorsque des push et des pop alternent près de la limite
  4. DPour garder le tableau trié
8.Difficile

Un nœud AVL est déséquilibré parce que le sous-arbre droit de son enfant gauche est devenu trop haut (cas gauche-droite). Quelle correction applique-t-on ?

  1. AUne rotation à gauche sur l'enfant gauche, puis une rotation à droite sur le nœud
  2. BUne rotation à droite sur l'enfant gauche, puis une rotation à gauche sur le nœud
  3. CUne rotation simple à gauche sur le nœud
  4. DUne rotation simple à droite sur le nœud

Corrigé

  1. 1. A · Le nombre d'éléments stockés divisé par le nombre de compartiments
  2. 2. D · Des nœuds qui ont le même parent
  3. 3. A · À la racine
  4. 4. C · Une file de priorité min
  5. 5. A · O(1)
  6. 6. A · On suit les enfants gauches depuis la racine jusqu'à ce qu'il n'y en ait plus
  7. 7. C · Pour éviter des redimensionnements répétés lorsque des push et des pop alternent près de la limite
  8. 8. A · Une rotation à gauche sur l'enfant gauche, puis une rotation à droite sur le nœud

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