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

Comment s'appelle l'opération de pile qui ajoute un élément au sommet ?

  1. APop (dépiler)
  2. BPeek (consulter)
  3. CEnqueue (enfiler)
  4. DPush (empiler)
2.Facile

La profondeur d'un nœud dans un arbre est :

  1. ALe nombre d'arêtes de ce nœud jusqu'à la feuille la plus profonde
  2. BLe nombre d'enfants de ce nœud
  3. CLe nombre d'arêtes de la racine jusqu'à ce nœud
  4. DLe nombre de nœuds de son sous-arbre
3.Facile

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

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

Les arbres AVL et les arbres rouge-noir garantissent :

  1. AUne recherche en temps constant dans tous les cas
  2. BQue les clés sont stockées dans l'ordre d'insertion
  3. CQu'aucun nœud n'a deux enfants
  4. DUne hauteur en O(log n) grâce au rééquilibrage
5.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 suit les enfants droits depuis la racine jusqu'à ce qu'il n'y en ait plus
  3. COn regarde uniquement la racine
  4. DOn visite toutes les feuilles et on les compare
6.Moyen

Dans un tas binaire min stocké dans un tableau (indices commençant à 0), les enfants du nœud d'indice i se trouvent aux indices :

  1. A2i + 1 et 2i + 2
  2. Bi/2 et i/2 + 1
  3. Ci + 1 et i + 2
  4. D2i et 2i + 1
7.Difficile

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

  1. AO(1)
  2. BO(log log n)
  3. CO(log n)
  4. DO(n)
8.Difficile

Un objet est stocké comme clé dans une table de hachage (hash map), puis un champ utilisé par sa fonction de hachage est modifié. Quel est le résultat probable ?

  1. ALa table lève une erreur au moment où le champ change
  2. BRien ne change, car le hachage d'une clé n'est calculé qu'une seule fois au démarrage du programme
  3. CLa table déplace automatiquement la clé dans son nouveau compartiment
  4. DLa recherche de l'objet peut échouer car il se trouve dans le compartiment de son ancien hachage

Corrigé

  1. 1. D · Push (empiler)
  2. 2. C · Le nombre d'arêtes de la racine jusqu'à ce nœud
  3. 3. B · Elle renvoie l'élément du sommet sans le retirer
  4. 4. D · Une hauteur en O(log n) grâce au rééquilibrage
  5. 5. A · On suit les enfants gauches depuis la racine jusqu'à ce qu'il n'y en ait plus
  6. 6. A · 2i + 1 et 2i + 2
  7. 7. D · O(n)
  8. 8. D · La recherche de l'objet peut échouer car il se trouve dans le compartiment de son ancien hachage

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