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

Qu'est-ce qu'un deque (file à double extrémité) ?

  1. AUne structure qui permet l'insertion et la suppression aux deux extrémités
  2. BUne file qui ne permet la suppression qu'à l'arrière
  3. CUne file triée par priorité
  4. DDeux files distinctes partageant un même tableau
2.Facile

Dans quel ordre un parcours préfixe (preorder) d'un arbre binaire visite-t-il les nœuds ?

  1. ALe nœud, puis le sous-arbre gauche, puis le sous-arbre droit
  2. BLe sous-arbre gauche, puis le sous-arbre droit, puis le nœud
  3. CLe sous-arbre gauche, puis le nœud, puis le sous-arbre droit
  4. DNiveau par niveau en partant du haut
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. BLa clé de chaque enfant gauche est supérieure ou égale à celle de son frère droit
  3. CLes clés sont triées de gauche à droite
  4. DToutes les feuilles contiennent la clé maximale
4.Moyen

Comment fonctionne l'extraction du minimum (extract-min) dans un tas binaire min ?

  1. AOn déplace le dernier élément à la racine et on le fait descendre
  2. BOn retire le dernier élément du tableau
  3. COn cherche le nouveau minimum parmi toutes les feuilles
  4. DOn retire la racine et on décale tous les éléments d'une case vers la gauche
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. A1
  2. Bn (il devient une liste chaînée)
  3. Clog₂ n
  4. D√n
6.Moyen

Quel type abstrait de données l'algorithme de Dijkstra utilise-t-il pour choisir le prochain sommet à traiter ?

  1. AUne file FIFO
  2. BUne pile
  3. CUn ensemble sans ordre
  4. DUne file de priorité min
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, 3, 8, 5]
  2. B[3, 1, 8, 5]
  3. C[1, 5, 8, 3]
  4. D[1, 3, 5, 8]
8.Difficile

Pourquoi un serveur pourrait-il choisir sa fonction de hachage au hasard dans une famille universelle ?

  1. APour supprimer le besoin de redimensionner la table
  2. BPour que la table de hachage soit triée
  3. CPour garantir que deux clés n'entrent jamais en collision, quelles que soient les clés envoyées par un attaquant
  4. DPour rendre très improbable qu'un attaquant puisse choisir de nombreuses clés qui entrent toutes en collision

Corrigé

  1. 1. A · Une structure qui permet l'insertion et la suppression aux deux extrémités
  2. 2. A · Le nœud, puis le sous-arbre gauche, puis le sous-arbre droit
  3. 3. A · La clé de chaque parent est supérieure ou égale aux clés de ses enfants
  4. 4. A · On déplace le dernier élément à la racine et on le fait descendre
  5. 5. B · n (il devient une liste chaînée)
  6. 6. D · Une file de priorité min
  7. 7. A · [1, 3, 8, 5]
  8. 8. D · Pour rendre très improbable qu'un attaquant puisse choisir de nombreuses clés qui entrent toutes en collision

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