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 structure de données fonctionne selon le principe « dernier entré, premier sorti » (LIFO) ?

  1. AListe chaînée
  2. BFile (queue)
  3. CPile (stack)
  4. DTable de hachage
2.Facile

Quelle opération est lente dans un tableau mais rapide en tête d'une liste chaînée ?

  1. AL'accès au 5e élément
  2. BL'insertion au début
  3. CLa lecture du dernier élément par son indice
  4. DLe calcul de la longueur d'un tableau de taille fixe
3.Facile

Qu'est-ce que la propriété de tas max ?

  1. ALa clé de chaque parent est supérieure ou égale aux clés de ses enfants
  2. BLes clés sont triées de gauche à droite
  3. CLa clé de chaque enfant gauche est supérieure ou égale à celle de son frère droit
  4. DToutes les feuilles contiennent la clé maximale
4.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 + 1
  4. D2h
5.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. CToutes les clés d'un tas sont égales
  4. DC'est un arbre binaire complet, donc les positions suivent des formules d'indice simples
6.Moyen

Combien de temps prend la recherche d'un mot de longueur L dans un trie à alphabet fixe ?

  1. AO(L), quel que soit le nombre de mots stockés
  2. BO(log n), où n est le nombre de mots
  3. CO(n), où n est le nombre de mots
  4. DO(L × n)
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+ ne stockent les données que dans la racine
  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+ n'ont pas besoin d'être équilibrés
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. CUne recherche en O(1) garantie, car chaque nœud stocke un pointeur vers tous les autres nœuds
  4. DElle stocke les clés sans ordre

Corrigé

  1. 1. C · Pile (stack)
  2. 2. B · L'insertion au début
  3. 3. A · La clé de chaque parent est supérieure ou égale aux clés de ses enfants
  4. 4. A · 2h+1 − 1
  5. 5. D · C'est un arbre binaire complet, donc les positions suivent des formules d'indice simples
  6. 6. A · O(L), quel que soit le nombre de mots stockés
  7. 7. B · Tous les enregistrements sont dans des feuilles chaînées, ce qui rend les parcours d'intervalle efficaces
  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.