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 liste simplement chaînée, que contient le pointeur next du dernier nœud ?

  1. ANull (aucun nœud)
  2. BL'adresse du premier nœud
  3. CL'adresse du nœud précédent
  4. DLe nombre de nœuds de la liste
2.Facile

Quelle est la caractéristique essentielle d'un ensemble en tant que type abstrait de données ?

  1. AIl ne permet l'accès qu'à une seule extrémité
  2. BIl stocke des éléments sans doublons
  3. CIl stocke des paires clé–valeur
  4. DIl stocke des éléments dans l'ordre trié
3.Facile

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

  1. AEnqueue (enfiler)
  2. BPop (dépiler)
  3. CPeek (consulter)
  4. DPush (empiler)
4.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. BLes tableaux maintiennent automatiquement les clés triées, donc aucun pointeur n'est nécessaire
  3. CC'est un arbre binaire complet, donc les positions suivent des formules d'indice simples
  4. DToutes les clés d'un tas sont égales
5.Moyen

Les clés 50, 30, 70, 20, 40 sont insérées dans cet ordre dans un arbre binaire de recherche vide. Quel est l'enfant gauche de 30 ?

  1. A20
  2. B50
  3. C70
  4. D40
6.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. BUn tableau dynamique
  3. CUne liste simplement chaînée
  4. DUne liste doublement chaînée
7.Difficile

En quoi un arbre radix (trie compressé) améliore-t-il un trie simple ?

  1. AIl stocke chaque mot dans une table de hachage à la racine au lieu de nœuds distincts
  2. BIl fusionne les chaînes de nœuds à enfant unique en une seule arête étiquetée par une chaîne
  3. CIl trie les enfants de chaque nœud par fréquence
  4. DIl ne garde que la première lettre de chaque mot
8.Difficile

Quel est le principal avantage d'une liste à enjambements (skip list) par rapport à une liste chaînée triée ?

  1. AElle n'utilise aucune mémoire supplémentaire
  2. BUne recherche en O(log n) en moyenne grâce à plusieurs niveaux de pointeurs avant
  3. CElle stocke les clés sans ordre
  4. DUne recherche en O(1) garantie, car chaque nœud stocke un pointeur vers tous les autres nœuds

Corrigé

  1. 1. A · Null (aucun nœud)
  2. 2. B · Il stocke des éléments sans doublons
  3. 3. D · Push (empiler)
  4. 4. C · C'est un arbre binaire complet, donc les positions suivent des formules d'indice simples
  5. 5. A · 20
  6. 6. D · Une liste doublement chaînée
  7. 7. B · Il fusionne les chaînes de nœuds à enfant unique en une seule arête étiquetée par une chaîne
  8. 8. B · Une recherche en O(log n) en moyenne grâce à plusieurs niveaux de pointeurs avant

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