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

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

1. AInférieures à la valeur du nœud
2. BDans un ordre aléatoire
3. CSupérieures à la valeur du nœud
4. DÉgales à la valeur du nœud

Dans un arbre, qu'est-ce qu'une feuille ?

1. AUn nœud ayant exactement un enfant
2. BUn nœud sans parent
3. CUn nœud sans enfant
4. DLe nœud de plus grande valeur

Quelle structure de données fonctionne selon le principe « dernier entré, premier sorti » (LIFO) ?

1. ATable de hachage
2. BPile (stack)
3. CFile (queue)
4. DListe chaînée

Les clés 50, 30, 70, 20, 40 sont insérées dans cet ordre dans un arbre binaire de recherche vide. Quel est l'enfant gauche de 30 ?

1. A20
2. B70
3. C40
4. D50

Les arbres AVL et les arbres rouge-noir garantissent :

1. AUne hauteur en O(log n) grâce au rééquilibrage
2. BQue les clés sont stockées dans l'ordre d'insertion
3. CUne recherche en temps constant dans tous les cas
4. DQu'aucun nœud n'a deux enfants

Dans une file circulaire stockée dans un tableau de capacité n, comment calcule-t-on la position suivant l'indice i ?

1. A(i − 1) mod n
2. Bi + 1
3. C2i + 1
4. D(i + 1) mod n

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

L'insertion d'une clé dans un arbre AVL rend le sous-arbre gauche d'un nœud trop haut, et la nouvelle clé est allée dans le sous-arbre gauche de son enfant gauche (cas gauche-gauche). Quelle correction applique-t-on ?

1. AUne rotation simple à droite sur le nœud déséquilibré
2. BUne rotation simple à gauche sur le nœud déséquilibré
3. CUn recoloriage du nœud et de son enfant
4. DUne rotation à gauche sur l'enfant, puis une rotation à droite sur le nœud