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 graphe pondéré ?

  1. AUn graphe dans lequel certains sommets sont plus lourds que d'autres parce qu'ils ont plus d'arêtes
  2. BUn graphe ayant plus d'arêtes que de sommets
  3. CUn graphe dans lequel chaque arête a une valeur numérique, comme un coût ou une distance
  4. DUn graphe stocké sur disque
2.Facile

Un graphe est constitué de :

  1. AUniquement des clés et des hachages
  2. BUniquement une racine et des feuilles
  3. CLignes et colonnes
  4. DSommets (nœuds) reliés par des arêtes
3.Facile

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

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

Qu'est-ce qui est vrai de la matrice d'adjacence d'un graphe non orienté ?

  1. ASa diagonale principale contient toujours des 1
  2. BElle est symétrique par rapport à la diagonale principale
  3. CElle est toujours triangulaire supérieure
  4. DChaque ligne contient exactement un 1
5.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. CUne file de priorité min
  4. DUn ensemble sans ordre
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(E²)
  2. BO(V²)
  3. CO(V + E)
  4. DO(V × E)
7.Difficile

La complexité temporelle de decrease-key dans un tas binaire (la position de l'élément étant connue) est :

  1. AO(log n)
  2. BO(1)
  3. CO(n)
  4. DO(n log n)
8.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 recherche de l'objet peut échouer car il se trouve dans le compartiment de son ancien hachage
  2. BLa table lève une erreur au moment où le champ change
  3. CLa table déplace automatiquement la clé dans son nouveau compartiment
  4. DRien ne change, car le hachage d'une clé n'est calculé qu'une seule fois au démarrage du programme

Corrigé

  1. 1. C · Un graphe dans lequel chaque arête a une valeur numérique, comme un coût ou une distance
  2. 2. D · Sommets (nœuds) reliés par des arêtes
  3. 3. C · La liste de ses sommets voisins
  4. 4. B · Elle est symétrique par rapport à la diagonale principale
  5. 5. C · Une file de priorité min
  6. 6. C · O(V + E)
  7. 7. A · O(log n)
  8. 8. A · La recherche de l'objet peut échouer car il se trouve dans le compartiment de son ancien hachage

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