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

Quelle structure de données convient le mieux à la fonction « annuler » (undo) d'un éditeur de texte ?

1. AGraphe
2. BPile (stack)
3. CFile (queue)
4. DEnsemble haché (hash set)

Dans un arbre binaire de recherche, les valeurs du sous-arbre gauche d'un nœud sont :

1. ASupérieures à la valeur du nœud
2. BInférieures à la valeur du nœud
3. CDans un ordre aléatoire
4. DÉgales à la valeur du nœud

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

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

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

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

Comment insère-t-on un nouvel élément dans un tas binaire ?

1. AOn le place à la racine et on le fait descendre
2. BOn l'insère à sa position triée en décalant d'un cran vers la droite tous les éléments plus grands
3. COn reconstruit entièrement le tas
4. DOn le place à la fin du tableau et on le fait remonter tant qu'il viole la propriété de tas

Quelle structure de données un programme en cours d'exécution utilise-t-il pour suivre les appels de fonction actifs et leurs variables locales ?

1. ALa file de la mémoire du tas
2. BUne table de hachage des fonctions
3. CLa pile d'appels
4. DUn arbre binaire de recherche de cadres

Pourquoi les bases de données utilisent-elles souvent des arbres B+ plutôt que de simples B-arbres pour leurs index ?

1. ATous les enregistrements sont dans des feuilles chaînées, ce qui rend les parcours d'intervalle efficaces
2. BLes arbres B+ ne stockent les données que dans la racine
3. CLes arbres B+ utilisent des nœuds internes binaires, ce qui réduit le nombre de lectures sur disque
4. DLes arbres B+ n'ont pas besoin d'être équilibrés

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. BPour garder le tableau trié
3. CParce que l'allocateur de mémoire ne peut libérer la mémoire que par quarts de bloc
4. DParce que diviser par deux à la moitié ferait perdre des éléments