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 les éléments d'un tableau sont-ils stockés en mémoire ?

  1. AÀ des emplacements aléatoires choisis par un hachage
  2. BDans un seul bloc contigu, les uns à la suite des autres
  3. CDe façon dispersée, reliés par des pointeurs
  4. DDans un arbre de pages mémoire
2.Facile

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

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

La hauteur d'un arbre est couramment définie comme :

  1. ALe nombre de feuilles de l'arbre
  2. BLe nombre d'arêtes du plus long chemin de la racine à une feuille
  3. CLe nombre d'enfants de la racine
  4. DLe nombre total de nœuds de l'arbre, en comptant la racine et chaque feuille
4.Moyen

Vous avez une référence vers un nœud au milieu d'une liste. Dans quelle liste pouvez-vous le supprimer en O(1) ?

  1. AUn tableau trié
  2. BUne liste doublement chaînée
  3. CUn tableau dynamique
  4. DUne liste simplement chaînée
5.Moyen

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

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

Quel est le coût de l'insertion d'un élément au milieu d'un tableau de n éléments ?

  1. AO(n²), car chaque élément se déplace n fois
  2. BO(1), car l'indice est connu
  3. CO(n), car les éléments suivants doivent être décalés
  4. DO(log n), grâce à la recherche dichotomique
7.Difficile

Dans une table de hachage à adressage ouvert, pourquoi la suppression se fait-elle souvent avec un marqueur « pierre tombale » (tombstone) ?

  1. ALes clés supprimées doivent être conservées pour toujours pour des raisons de sécurité, si bien que les emplacements ne peuvent jamais être réutilisés
  2. BCela rend la table triée
  3. CLes pierres tombales accélèrent le hachage
  4. DVider l'emplacement pourrait interrompre la séquence de sondage d'autres clés
8.Difficile

Quel est le temps d'exécution d'un parcours en largeur sur un graphe à V sommets stocké sous forme de matrice d'adjacence ?

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

Corrigé

  1. 1. B · Dans un seul bloc contigu, les uns à la suite des autres
  2. 2. B · Le nombre d'arêtes de la racine jusqu'à ce nœud
  3. 3. B · Le nombre d'arêtes du plus long chemin de la racine à une feuille
  4. 4. B · Une liste doublement chaînée
  5. 5. C · On suit les enfants gauches depuis la racine jusqu'à ce qu'il n'y en ait plus
  6. 6. C · O(n), car les éléments suivants doivent être décalés
  7. 7. D · Vider l'emplacement pourrait interrompre la séquence de sondage d'autres clés
  8. 8. A · O(V²)

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