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 file qui retire l'élément situé à l'avant ?

  1. AInsert (insérer)
  2. BDequeue (défiler)
  3. CEnqueue (enfiler)
  4. DPush (empiler)
2.Facile

Que stocke un dictionnaire (map) ?

  1. AUniquement des valeurs dans l'ordre d'insertion
  2. BDes paires clé–valeur à clés uniques
  3. CDes valeurs triées par taille
  4. DDes paires de clés égales
3.Facile

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

  1. ALes clés sont triées de gauche à droite
  2. BLa clé de chaque parent est supérieure ou égale aux clés de ses enfants
  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

Une file est implémentée avec deux piles : on empile sur une pile « in » et on dépile depuis une pile « out », remplie à partir de « in » lorsqu'elle est vide. Quel est le coût amorti par opération ?

  1. AO(1)
  2. BO(n²)
  3. CO(n)
  4. DO(log n)
5.Moyen

Quelle est la hauteur, dans le pire des cas, d'un arbre binaire de recherche à n nœuds si les clés sont insérées dans l'ordre trié ?

  1. An (il devient une liste chaînée)
  2. B√n
  3. C1
  4. Dlog₂ n
6.Moyen

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

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

Quelle propriété un arbre rouge-noir doit-il respecter ?

  1. AChaque nœud doit être rouge
  2. BTout chemin d'un nœud vers ses feuilles descendantes contient le même nombre de nœuds noirs
  3. CTout nœud rouge doit avoir des enfants rouges, si bien que les nœuds rouges forment toujours des chaînes ininterrompues jusqu'aux feuilles
  4. DLa racine doit être rouge
8.Difficile

Que fait un arbre splay (splay tree) après chaque accès ?

  1. AIl déplace le nœud accédé vers une feuille
  2. BIl recolorie les nœuds du chemin de recherche
  3. CIl fait remonter le nœud accédé jusqu'à la racine par des rotations
  4. DIl reconstruit tout l'arbre sous forme équilibrée

Corrigé

  1. 1. B · Dequeue (défiler)
  2. 2. B · Des paires clé–valeur à clés uniques
  3. 3. B · La clé de chaque parent est supérieure ou égale aux clés de ses enfants
  4. 4. A · O(1)
  5. 5. A · n (il devient une liste chaînée)
  6. 6. B · C'est un arbre binaire complet, donc les positions suivent des formules d'indice simples
  7. 7. B · Tout chemin d'un nœud vers ses feuilles descendantes contient le même nombre de nœuds noirs
  8. 8. C · Il fait remonter le nœud accédé jusqu'à la racine par des rotations

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