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 de compartiments divisé par la longueur moyenne des clés stockées
  2. BLe nombre d'éléments stockés divisé par le nombre de compartiments
  3. CLe temps nécessaire pour charger la table depuis le disque
  4. DLe nombre de collisions survenues jusqu'ici
2.Facile

Qu'est-ce qu'un graphe pondéré ?

  1. AUn graphe stocké sur disque
  2. BUn graphe dans lequel certains sommets sont plus lourds que d'autres parce qu'ils ont plus d'arêtes
  3. CUn graphe dans lequel chaque arête a une valeur numérique, comme un coût ou une distance
  4. DUn graphe ayant plus d'arêtes que de sommets
3.Facile

Comment s'appelle l'opération de file qui retire l'élément situé à l'avant ?

  1. ADequeue (défiler)
  2. BInsert (insérer)
  3. CEnqueue (enfiler)
  4. DPush (empiler)
4.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(log V)
  3. CO(E)
  4. DO(V)
5.Moyen

Quelle est la valeur de l'expression postfixée 3 4 + 2 * ?

  1. A11
  2. B14
  3. C10
  4. D24
6.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 chaînage séparé (separate chaining)
  2. BLe sondage quadratique (quadratic probing)
  3. CLe sondage linéaire (linear probing)
  4. DLe double hachage (double hashing)
7.Difficile

Quelle garantie les règles des arbres rouge-noir donnent-elles sur la hauteur d'un arbre à n clés ?

  1. ALa hauteur est au plus 2 log2(n + 1)
  2. BLa hauteur est au plus n / 2
  3. CLa hauteur vaut exactement log2 n
  4. DLa hauteur est au plus log2 n + 1
8.Difficile

L'insertion d'une clé dans un arbre AVL rend le sous-arbre gauche d'un nœud trop haut, et la nouvelle clé est allée dans le sous-arbre gauche de son enfant gauche (cas gauche-gauche). Quelle correction applique-t-on ?

  1. AUne rotation simple à gauche sur le nœud déséquilibré
  2. BUne rotation à gauche sur l'enfant, puis une rotation à droite sur le nœud
  3. CUn recoloriage du nœud et de son enfant
  4. DUne rotation simple à droite sur le nœud déséquilibré

Corrigé

  1. 1. B · Le nombre d'éléments stockés divisé par le nombre de compartiments
  2. 2. C · Un graphe dans lequel chaque arête a une valeur numérique, comme un coût ou une distance
  3. 3. A · Dequeue (défiler)
  4. 4. A · O(1)
  5. 5. B · 14
  6. 6. A · Le chaînage séparé (separate chaining)
  7. 7. A · La hauteur est au plus 2 log2(n + 1)
  8. 8. D · Une rotation simple à droite sur le nœud déséquilibré

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