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

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

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

Dans un arbre, que sont des nœuds frères ?

1. ADes nœuds de même profondeur dans des sous-arbres différents
2. BDes nœuds qui ont le même parent
3. CUn nœud et son parent
4. DDes nœuds qui n'ont pas d'enfant

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

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

Vous avez une référence vers un nœud au milieu d'une liste. Dans quelle liste pouvez-vous le supprimer en O(1) ?

1. AUn tableau trié
2. BUne liste simplement chaînée
3. CUne liste doublement chaînée
4. DUn tableau dynamique

Un trie (arbre de préfixes) est particulièrement efficace pour :

1. ALa recherche des plus courts chemins
2. BLe stockage de matrices
3. CLe tri de nombres
4. DLes recherches par préfixe, comme l'autocomplétion

Quelle condition d'équilibre un arbre AVL maintient-il en chaque nœud ?

1. AChaque nœud est colorié en rouge ou en noir
2. BToutes les feuilles sont exactement à la même profondeur
3. CLes hauteurs des sous-arbres gauche et droit diffèrent d'au plus 1
4. DLes deux sous-arbres de chaque nœud contiennent exactement le même nombre de nœuds

La structure union-find (ensembles disjoints) avec union par rang et compression de chemin a un coût amorti par opération de :

1. AO(n²)
2. BO(n)
3. CO(α(n)), l'inverse de la fonction d'Ackermann, pratiquement constant
4. DExactement O(log n)

Pourquoi ne peut-on pas simplement supprimer des éléments d'un filtre de Bloom standard en remettant leurs bits à zéro ?

1. ALes bits d'un filtre de Bloom ne peuvent pas être modifiés après sa création
2. BCes bits peuvent aussi appartenir à d'autres éléments, ce qui provoquerait des faux négatifs
3. CLa suppression porterait le taux de faux positifs à 100%
4. DLes filtres de Bloom stockent les éléments complets, qui sont introuvables une fois hachés