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

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

1. A2n
2. Bn − 1
3. Cn + 1
4. Dn

Quelle est la principale différence entre un tableau statique et un tableau dynamique ?

1. AUn tableau dynamique peut grandir en passant à un bloc de mémoire plus grand
2. BUn tableau statique offre un accès par indice plus lent
3. CUn tableau dynamique stocke ses éléments dans des nœuds chaînés, ce qui lui permet de grandir un élément à la fois
4. DUn tableau statique ne peut stocker que des nombres

Dans une table de hachage, qu'est-ce qu'une collision ?

1. AUne clé ne peut pas du tout être hachée
2. BDeux clés égales sont stockées deux fois
3. CDeux clés différentes sont associées au même indice
4. DLa table manque de mémoire

À quoi sert un nœud sentinelle (factice) dans une liste chaînée ?

1. AÀ stocker le nombre d'éléments
2. BÀ empêcher la liste de dépasser un nombre maximal fixe de nœuds
3. CÀ simplifier le code en supprimant les cas particuliers en tête ou en queue
4. DÀ rendre la liste triée

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. B(i − 1) mod n
3. C2i + 1
4. Di + 1

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

Quelle propriété maintient tout B-arbre parfaitement équilibré ?

1. ALes clés ne sont stockées que dans la racine
2. BToutes les feuilles sont à la même profondeur
3. CChaque nœud a exactement deux enfants
4. DChaque nœud stocke une seule clé

Quelle structure permet de calculer le maximum de chaque fenêtre de taille k dans un tableau en O(n) au total ?

1. AUn tableau trié mis à jour par décalage
2. BUn deque contenant des indices par ordre décroissant de valeur
3. CUn tas min reconstruit pour chaque fenêtre
4. DUne liste simplement chaînée des éléments de la fenêtre