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

Qu'est-ce qui définit un arbre binaire ?

1. AChaque nœud a exactement deux enfants
2. BL'arbre a exactement deux niveaux
3. CChaque nœud a au plus deux enfants
4. DChaque nœud stocke un nombre binaire

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. BDans un ordre aléatoire
3. CÉgales à la valeur du nœud
4. DInférieures à la valeur du nœud

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

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

Dans une table de hachage à adressage ouvert, quel est le facteur de charge maximal possible ?

1. A1
2. BIl n'y a pas de maximum
3. C2
4. D0,5

Quelle quantité de mémoire une liste d'adjacence utilise-t-elle pour un graphe à V sommets et E arêtes ?

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

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

Dans un tampon circulaire, front == rear peut signifier vide ou plein. Quelle est une manière courante de les distinguer ?

1. AChoisir une taille de tampon égale à une puissance de deux
2. BToujours vider le tampon dès que front est égal à rear, si bien que l'état est vide
3. CStocker front et rear dans la même variable
4. DTenir un compteur d'éléments séparé, ou toujours laisser une case inutilisée

Dans l'algorithme de Kruskal pour l'arbre couvrant de poids minimal, à quoi sert la structure union-find ?

1. AÀ vérifier si les deux extrémités d'une arête sont déjà reliées
2. BÀ choisir le sommet de départ
3. CÀ trier les arêtes par poids
4. DÀ stocker la distance actuelle de chaque sommet depuis la source pendant le parcours