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 l'opération peek (ou top) sur une pile ?

  1. AElle retire l'élément du sommet et le renvoie
  2. BElle retire tous les éléments de la pile
  3. CElle renvoie l'élément du fond de la pile
  4. DElle renvoie l'élément du sommet sans le retirer
2.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. BDeux files distinctes partageant un même tableau
  3. CUne file qui ne permet la suppression qu'à l'arrière
  4. DUne file triée par priorité
3.Facile

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

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

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

  1. AUne pile
  2. BUne file de priorité min
  3. CUne file FIFO
  4. DUn ensemble sans ordre
5.Moyen

Combien de temps faut-il pour vérifier si l'arête (u, v) existe avec une matrice d'adjacence ?

  1. AO(1)
  2. BO(E)
  3. CO(V)
  4. DO(log V)
6.Moyen

Quelle quantité de mémoire une liste d'adjacence utilise-t-elle pour un graphe à V sommets et E arêtes ?

  1. AO(V + E)
  2. BO(E²)
  3. CO(V × E)
  4. DO(V²)
7.Difficile

Un objet est stocké comme clé dans une table de hachage (hash map), puis un champ utilisé par sa fonction de hachage est modifié. Quel est le résultat probable ?

  1. ALa table déplace automatiquement la clé dans son nouveau compartiment
  2. BRien ne change, car le hachage d'une clé n'est calculé qu'une seule fois au démarrage du programme
  3. CLa recherche de l'objet peut échouer car il se trouve dans le compartiment de son ancien hachage
  4. DLa table lève une erreur au moment où le champ change
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. BLa racine doit être rouge
  3. CChaque nœud doit être rouge
  4. DTout nœud rouge doit avoir des enfants rouges, si bien que les nœuds rouges forment toujours des chaînes ininterrompues jusqu'aux feuilles

Corrigé

  1. 1. D · Elle renvoie l'élément du sommet sans le retirer
  2. 2. A · Une structure qui permet l'insertion et la suppression aux deux extrémités
  3. 3. B · Il stocke des éléments sans doublons
  4. 4. B · Une file de priorité min
  5. 5. A · O(1)
  6. 6. A · O(V + E)
  7. 7. C · La recherche de l'objet peut échouer car il se trouve dans le compartiment de son ancien hachage
  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.