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

Quelle opération est en O(1) pour un tableau mais en O(n) pour une liste simplement chaînée ?

  1. AL'accès à l'élément d'indice i
  2. BL'insertion en tête
  3. CLa suppression de l'élément de tête
  4. DLa lecture du premier élément
2.Facile

Qu'est-ce que la racine d'un arbre ?

  1. ALe nœud ayant la plus grande valeur
  2. BLe nœud situé tout en haut, sans parent
  3. CUn nœud sans enfant
  4. DN'importe quel nœud au milieu
3.Facile

Dans une liste simplement chaînée, que contient le pointeur next du dernier nœud ?

  1. AL'adresse du premier nœud
  2. BLe nombre de nœuds de la liste
  3. CL'adresse du nœud précédent
  4. DNull (aucun nœud)
4.Moyen

Une application a besoin de recherches rapides, mais aussi de lister les clés dans l'ordre trié et de répondre à des requêtes par intervalle. Quelle structure convient le mieux ?

  1. AUne pile
  2. BUn arbre binaire de recherche équilibré
  3. CUne table de hachage
  4. DUne liste chaînée non triée
5.Moyen

Combien de nœuds possède un arbre binaire parfait de hauteur h, la hauteur étant comptée en arêtes ?

  1. A2h+1 − 1
  2. Bh2
  3. C2h
  4. D2h + 1
6.Moyen

Pourquoi un tas binaire peut-il être stocké dans un tableau sans aucun pointeur ?

  1. ALes tas ne contiennent jamais plus de 100 éléments
  2. BC'est un arbre binaire complet, donc les positions suivent des formules d'indice simples
  3. CToutes les clés d'un tas sont égales
  4. DLes tableaux maintiennent automatiquement les clés triées, donc aucun pointeur n'est nécessaire
7.Difficile

Les clés 5, 3, 8, 1 sont insérées dans cet ordre dans un tas binaire min vide stocké dans un tableau. Quel est le tableau final ?

  1. A[1, 5, 8, 3]
  2. B[3, 1, 8, 5]
  3. C[1, 3, 5, 8]
  4. D[1, 3, 8, 5]
8.Difficile

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

  1. ALes pierres tombales accélèrent le hachage
  2. BCela rend la table triée
  3. CLes 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
  4. DVider l'emplacement pourrait interrompre la séquence de sondage d'autres clés

Corrigé

  1. 1. A · L'accès à l'élément d'indice i
  2. 2. B · Le nœud situé tout en haut, sans parent
  3. 3. D · Null (aucun nœud)
  4. 4. B · Un arbre binaire de recherche équilibré
  5. 5. A · 2h+1 − 1
  6. 6. B · C'est un arbre binaire complet, donc les positions suivent des formules d'indice simples
  7. 7. D · [1, 3, 8, 5]
  8. 8. D · Vider l'emplacement pourrait interrompre la séquence de sondage d'autres clés

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