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

Que fait une fonction de hachage dans une table de hachage ?

  1. AElle trie les clés de la table
  2. BElle compte le nombre de clés stockées
  3. CElle associe une clé à un indice de la table
  4. DElle chiffre les valeurs de la table
2.Facile

Dans quel ordre un parcours préfixe (preorder) d'un arbre binaire visite-t-il les nœuds ?

  1. ANiveau par niveau en partant du haut
  2. BLe sous-arbre gauche, puis le sous-arbre droit, puis le nœud
  3. CLe sous-arbre gauche, puis le nœud, puis le sous-arbre droit
  4. DLe nœud, puis le sous-arbre gauche, puis le sous-arbre droit
3.Facile

Quelle structure est généralement utilisée pour implémenter une file de priorité ?

  1. AUne chaîne de caractères
  2. BUne liste simplement chaînée non ordonnée
  3. CUn tas (heap)
  4. DUne pile (stack)
4.Moyen

Que se passe-t-il lorsqu'une table de hachage est rehachée après que son facteur de charge a dépassé un seuil ?

  1. ALes clés existantes sont triées sur place
  2. BSeules les clés en collision sont déplacées dans une nouvelle liste de débordement à la fin de la table
  3. CUne table plus grande est allouée et chaque clé y est réinsérée
  4. DLes clés les plus anciennes sont supprimées pour faire de la place
5.Moyen

Quelle quantité de mémoire une liste d'adjacence utilise-t-elle pour un graphe à V sommets et E arêtes ?

  1. AO(E²)
  2. BO(V × E)
  3. CO(V²)
  4. DO(V + E)
6.Moyen

Quelle quantité de mémoire une matrice d'adjacence utilise-t-elle pour un graphe à V sommets ?

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

Combien de temps faut-il pour rechercher une clé quelconque dans un tas binaire min de n éléments ?

  1. AO(n)
  2. BO(log log n)
  3. CO(1)
  4. DO(log n)
8.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. APour garder le tableau trié
  2. BParce que l'allocateur de mémoire ne peut libérer la mémoire que par quarts de bloc
  3. CParce que diviser par deux à la moitié ferait perdre des éléments
  4. DPour éviter des redimensionnements répétés lorsque des push et des pop alternent près de la limite

Corrigé

  1. 1. C · Elle associe une clé à un indice de la table
  2. 2. D · Le nœud, puis le sous-arbre gauche, puis le sous-arbre droit
  3. 3. C · Un tas (heap)
  4. 4. C · Une table plus grande est allouée et chaque clé y est réinsérée
  5. 5. D · O(V + E)
  6. 6. D · O(V²)
  7. 7. A · O(n)
  8. 8. D · Pour éviter des redimensionnements répétés lorsque des push et des pop alternent près de la limite

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