Fiche d’exercices de Structures de données avec corrigé

Que stocke un dictionnaire (map) ?

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

Dans quel ordre un parcours postfixe (postorder) d'un arbre binaire visite-t-il les nœuds ?

1. ALe nœud, puis le sous-arbre gauche, puis le sous-arbre droit
2. BLe sous-arbre gauche, puis le nœud, puis le sous-arbre droit
3. CLe sous-arbre gauche, puis le sous-arbre droit, puis le nœud
4. DLe sous-arbre droit, puis le nœud, puis le sous-arbre gauche

Dans un graphe, qu'est-ce qu'un cycle ?

1. AUn chemin qui commence et se termine au même sommet
2. BUn sommet sans arête
3. CUne arête de poids nul
4. DUn chemin qui passe par tous les sommets

Vous avez une référence vers un nœud au milieu d'une liste. Dans quelle liste pouvez-vous le supprimer en O(1) ?

1. AUne liste simplement chaînée
2. BUn tableau trié
3. CUn tableau dynamique
4. DUne liste doublement chaînée

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

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

Pourquoi le parcours d'un tableau est-il souvent bien plus rapide en pratique que celui d'une liste chaînée de même longueur ?

1. ALes éléments d'un tableau sont contigus, ce qui exploite bien le cache du processeur
2. BLes tableaux utilisent moins d'instructions pour comparer les valeurs
3. CLes listes chaînées stockent toujours leurs éléments sur disque
4. DLe parcours d'un tableau est en O(1) au total, alors que celui d'une liste chaînée est en O(n)

Que fait un arbre splay (splay tree) après chaque accès ?

1. AIl recolorie les nœuds du chemin de recherche
2. BIl déplace le nœud accédé vers une feuille
3. CIl fait remonter le nœud accédé jusqu'à la racine par des rotations
4. DIl reconstruit tout l'arbre sous forme équilibrée

Un tableau dynamique double de taille lorsqu'il est plein. Pourquoi de nombreuses implémentations ne le réduisent-elles que lorsqu'il est rempli au quart, et non à moitié ?

1. APour éviter des redimensionnements répétés lorsque des push et des pop alternent près de la limite
2. BParce que diviser par deux à la moitié ferait perdre des éléments
3. CParce que l'allocateur de mémoire ne peut libérer la mémoire que par quarts de bloc
4. DPour garder le tableau trié