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

Que fait une fonction de hachage dans une table de hachage ?

  1. AElle trie les clés de la table
  2. BElle chiffre les valeurs de la table
  3. CElle associe une clé à un indice de la table
  4. DElle compte le nombre de clés stockées
2.Facile

Dans une représentation d'un graphe par listes d'adjacence, que stocke-t-on pour chaque sommet ?

  1. ALa liste de ses sommets voisins
  2. BUne ligne de V valeurs booléennes
  3. CLe nombre total d'arêtes du graphe
  4. DLe plus court chemin vers tous les autres sommets
3.Facile

Que stocke un dictionnaire (map) ?

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

Comment insère-t-on un nouvel élément dans un tas binaire ?

  1. AOn l'insère à sa position triée en décalant d'un cran vers la droite tous les éléments plus grands
  2. BOn le place à la racine et on le fait descendre
  3. COn le place à la fin du tableau et on le fait remonter tant qu'il viole la propriété de tas
  4. DOn reconstruit entièrement le tas
5.Moyen

Les arbres AVL et les arbres rouge-noir garantissent :

  1. AQue les clés sont stockées dans l'ordre d'insertion
  2. BUne recherche en temps constant dans tous les cas
  3. CQu'aucun nœud n'a deux enfants
  4. DUne hauteur en O(log n) grâce au rééquilibrage
6.Moyen

Quelle est la valeur de l'expression postfixée 3 4 + 2 * ?

  1. A24
  2. B10
  3. C11
  4. D14
7.Difficile

Quels sont les coûts en temps et en espace supplémentaire de l'inversion sur place d'une liste simplement chaînée ?

  1. AO(1) en temps et O(1) en espace supplémentaire
  2. BO(n) en temps et O(1) en espace supplémentaire
  3. CO(n) en temps et O(n) en espace supplémentaire
  4. DO(n log n) en temps et O(1) en espace supplémentaire
8.Difficile

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

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

Corrigé

  1. 1. C · Elle associe une clé à un indice de la table
  2. 2. A · La liste de ses sommets voisins
  3. 3. A · Des paires clé–valeur à clés uniques
  4. 4. C · On le place à la fin du tableau et on le fait remonter tant qu'il viole la propriété de tas
  5. 5. D · Une hauteur en O(log n) grâce au rééquilibrage
  6. 6. D · 14
  7. 7. B · O(n) en temps et O(1) en espace supplémentaire
  8. 8. A · Tout chemin d'un nœud vers ses feuilles descendantes contient le même nombre de nœuds noirs

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