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

Dans quel ordre un parcours préfixe (preorder) d'un arbre binaire visite-t-il les nœuds ?

1. ALe sous-arbre gauche, puis le nœud, puis le sous-arbre droit
2. BLe sous-arbre gauche, puis le sous-arbre droit, puis le nœud
3. CNiveau par niveau en partant du haut
4. DLe nœud, puis le sous-arbre gauche, puis le sous-arbre droit

Que contient chaque nœud d'une liste doublement chaînée ?

1. ADes données, un pointeur vers le nœud suivant et un pointeur vers le nœud précédent
2. BDes données et deux pointeurs, l'un vers le nœud suivant et l'autre vers le nœud d'après
3. CDes données et uniquement un pointeur vers le nœud suivant
4. DDeux copies des données et un pointeur

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

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

Quelle quantité de mémoire une matrice d'adjacence utilise-t-elle pour un graphe à V sommets ?

1. AO(V²)
2. BO(V + E)
3. CO(E)
4. DO(log V)

Un tampon circulaire (ring buffer) est couramment utilisé pour implémenter :

1. AUne fonction de hachage
2. BUn arbre binaire de recherche
3. CUne file de taille fixe
4. DUn parcours de graphe

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 regarde uniquement la racine
4. DOn suit les enfants gauches depuis la racine jusqu'à ce qu'il n'y en ait plus

Un arbre de segments (segment tree) est généralement utilisé pour :

1. ATrier des chaînes par ordre alphabétique en stockant chaque préfixe dans un nœud distinct de l'arbre
2. BImplémenter une pile
3. CStocker les arêtes d'un graphe
4. DRépondre à des requêtes sur intervalles (comme des sommes d'intervalles) et à des mises à jour en O(log n)

Un nœud AVL est déséquilibré parce que le sous-arbre droit de son enfant gauche est devenu trop haut (cas gauche-droite). Quelle correction applique-t-on ?

1. AUne rotation à droite sur l'enfant gauche, puis une rotation à gauche sur le nœud
2. BUne rotation simple à gauche sur le nœud
3. CUne rotation à gauche sur l'enfant gauche, puis une rotation à droite sur le nœud
4. DUne rotation simple à droite sur le nœud