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 stocke un dictionnaire (map) ?

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

Où se trouve le plus petit élément d'un tas binaire min ?

  1. AÀ la dernière position du tableau
  2. BDans une feuille quelconque, qu'il faut chercher
  3. CDans la feuille la plus à gauche
  4. DÀ la racine
3.Facile

Que fait l'opération peek (ou top) sur une pile ?

  1. AElle renvoie l'élément du sommet sans le retirer
  2. BElle retire l'élément du sommet et le renvoie
  3. CElle renvoie l'élément du fond de la pile
  4. DElle retire tous les éléments de la pile
4.Moyen

Comment trouve-t-on la clé minimale dans un arbre binaire de recherche ?

  1. AOn regarde uniquement la racine
  2. BOn visite toutes les feuilles et on les compare
  3. COn suit les enfants gauches depuis la racine jusqu'à ce qu'il n'y en ait plus
  4. DOn suit les enfants droits depuis la racine jusqu'à ce qu'il n'y en ait plus
5.Moyen

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

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

Un trie (arbre de préfixes) est particulièrement efficace pour :

  1. ALa recherche des plus courts chemins
  2. BLe tri de nombres
  3. CLes recherches par préfixe, comme l'autocomplétion
  4. DLe stockage de matrices
7.Difficile

La suppression d'un nœud ayant deux enfants dans un arbre binaire de recherche se fait généralement en :

  1. ASupprimant tout le sous-arbre
  2. BReconstruisant de zéro le sous-arbre situé en dessous et en réinsérant toutes les clés qu'il contenait
  3. CLe remplaçant par son successeur infixe (ou prédécesseur) puis en supprimant ce nœud
  4. DL'échangeant avec la racine
8.Difficile

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

  1. ALa racine doit être rouge
  2. BTout chemin d'un nœud vers ses feuilles descendantes contient le même nombre de nœuds noirs
  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. A · Des paires clé–valeur à clés uniques
  2. 2. D · À la racine
  3. 3. A · Elle renvoie l'élément du sommet sans le retirer
  4. 4. C · On suit les enfants gauches depuis la racine jusqu'à ce qu'il n'y en ait plus
  5. 5. D · Une liste d'adjacence
  6. 6. C · Les recherches par préfixe, comme l'autocomplétion
  7. 7. C · Le remplaçant par son successeur infixe (ou prédécesseur) puis en supprimant ce nœud
  8. 8. B · 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.