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

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

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

Que fait l'opération peek (ou top) sur une pile ?

  1. AElle retire tous les éléments de la pile
  2. BElle renvoie l'élément du fond de la pile
  3. CElle renvoie l'élément du sommet sans le retirer
  4. DElle retire l'élément du sommet et le renvoie
3.Facile

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

  1. AÀ la racine
  2. BÀ la dernière position du tableau
  3. CDans une feuille quelconque, qu'il faut chercher
  4. DDans la feuille la plus à gauche
4.Moyen

Quelle condition d'équilibre un arbre AVL maintient-il en chaque nœud ?

  1. ALes hauteurs des sous-arbres gauche et droit diffèrent d'au plus 1
  2. BToutes les feuilles sont exactement à la même profondeur
  3. CLes deux sous-arbres de chaque nœud contiennent exactement le même nombre de nœuds
  4. DChaque nœud est colorié en rouge ou en noir
5.Moyen

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

  1. A24
  2. B14
  3. C10
  4. D11
6.Moyen

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

  1. A2
  2. B1
  3. CIl n'y a pas de maximum
  4. D0,5
7.Difficile

Pourquoi les bases de données utilisent-elles souvent des arbres B+ plutôt que de simples B-arbres pour leurs index ?

  1. ALes arbres B+ n'ont pas besoin d'être équilibrés
  2. BTous les enregistrements sont dans des feuilles chaînées, ce qui rend les parcours d'intervalle efficaces
  3. CLes arbres B+ utilisent des nœuds internes binaires, ce qui réduit le nombre de lectures sur disque
  4. DLes arbres B+ ne stockent les données que dans la racine
8.Difficile

Quels sont les coûts en temps et en espace supplémentaire de l'inversion sur place d'une liste simplement chaînée ?

  1. AO(1) en temps et O(1) en espace supplémentaire
  2. BO(n log n) en temps et O(1) en espace supplémentaire
  3. CO(n) en temps et O(1) en espace supplémentaire
  4. DO(n) en temps et O(n) en espace supplémentaire

Corrigé

  1. 1. D · Deux clés différentes sont associées au même indice
  2. 2. C · Elle renvoie l'élément du sommet sans le retirer
  3. 3. A · À la racine
  4. 4. A · Les hauteurs des sous-arbres gauche et droit diffèrent d'au plus 1
  5. 5. B · 14
  6. 6. B · 1
  7. 7. B · Tous les enregistrements sont dans des feuilles chaînées, ce qui rend les parcours d'intervalle efficaces
  8. 8. C · O(n) en temps et O(1) en espace supplémentaire

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