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

Quelle opération est lente dans un tableau mais rapide en tête d'une liste chaînée ?

  1. AL'insertion au début
  2. BL'accès au 5e élément
  3. CLe calcul de la longueur d'un tableau de taille fixe
  4. DLa lecture du dernier élément par son indice
2.Facile

Qu'est-ce qu'un graphe pondéré ?

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

Comment s'appelle l'opération de pile qui ajoute un élément au sommet ?

  1. APop (dépiler)
  2. BPush (empiler)
  3. CPeek (consulter)
  4. DEnqueue (enfiler)
4.Moyen

Un réseau routier compte 100,000 carrefours, chacun relié à environ 4 autres. Quelle représentation est la plus adaptée ?

  1. AUn unique tableau trié de sommets
  2. BUne liste d'adjacence
  3. CUn tas binaire d'arêtes
  4. DUne matrice d'adjacence
5.Moyen

Quelle structure de données utilise-t-on pour vérifier si les parenthèses de "{[()]}" sont équilibrées ?

  1. AUne file
  2. BUn arbre binaire de recherche
  3. CUne table de hachage
  4. DUne pile
6.Moyen

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

  1. AOn cherche le nouveau minimum parmi toutes les feuilles
  2. BOn retire le dernier élément du tableau
  3. COn déplace le dernier élément à la racine et on le fait descendre
  4. DOn retire la racine et on décale tous les éléments d'une case vers la gauche
7.Difficile

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

  1. AChaque nœud doit être rouge
  2. BLa racine doit être rouge
  3. CTout chemin d'un nœud vers ses feuilles descendantes contient le même nombre de nœuds noirs
  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
8.Difficile

Dans l'algorithme de Kruskal pour l'arbre couvrant de poids minimal, à quoi sert la structure union-find ?

  1. AÀ vérifier si les deux extrémités d'une arête sont déjà reliées
  2. BÀ choisir le sommet de départ
  3. CÀ trier les arêtes par poids
  4. DÀ stocker la distance actuelle de chaque sommet depuis la source pendant le parcours

Corrigé

  1. 1. A · L'insertion au début
  2. 2. B · Un graphe dans lequel chaque arête a une valeur numérique, comme un coût ou une distance
  3. 3. B · Push (empiler)
  4. 4. B · Une liste d'adjacence
  5. 5. D · Une pile
  6. 6. C · On déplace le dernier élément à la racine et on le fait descendre
  7. 7. C · Tout chemin d'un nœud vers ses feuilles descendantes contient le même nombre de nœuds noirs
  8. 8. A · À vérifier si les deux extrémités d'une arête sont déjà reliées

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