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

La hauteur d'un arbre est couramment définie comme :

1. ALe nombre total de nœuds de l'arbre, en comptant la racine et chaque feuille
2. BLe nombre de feuilles de l'arbre
3. CLe nombre d'enfants de la racine
4. DLe nombre d'arêtes du plus long chemin de la racine à une feuille

Combien d'arêtes possède un arbre à n nœuds ?

1. An
2. Bn − 1
3. Cn + 1
4. D2n

Qu'est-ce que le facteur de charge d'une table de hachage ?

1. ALe nombre de compartiments divisé par la longueur moyenne des clés stockées
2. BLe temps nécessaire pour charger la table depuis le disque
3. CLe nombre de collisions survenues jusqu'ici
4. DLe nombre d'éléments stockés divisé par le nombre de compartiments

Combien de temps prend la recherche d'un mot de longueur L dans un trie à alphabet fixe ?

1. AO(L), quel que soit le nombre de mots stockés
2. BO(L × n)
3. CO(n), où n est le nombre de mots
4. DO(log n), où n est le nombre de mots

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

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

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

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

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

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

Quel est le principal avantage d'une liste à enjambements (skip list) par rapport à une liste chaînée triée ?

1. AUne recherche en O(1) garantie, car chaque nœud stocke un pointeur vers tous les autres nœuds
2. BUne recherche en O(log n) en moyenne grâce à plusieurs niveaux de pointeurs avant
3. CElle stocke les clés sans ordre
4. DElle n'utilise aucune mémoire supplémentaire