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

La profondeur d'un nœud dans un arbre est :

1. ALe nombre d'enfants de ce nœud
2. BLe nombre de nœuds de son sous-arbre
3. CLe nombre d'arêtes de ce nœud jusqu'à la feuille la plus profonde
4. DLe nombre d'arêtes de la racine jusqu'à ce nœud

Quelle structure est généralement utilisée pour implémenter une file de priorité ?

1. AUne liste simplement chaînée non ordonnée
2. BUn tas (heap)
3. CUne chaîne de caractères
4. DUne pile (stack)

Quelle est la caractéristique essentielle d'un ensemble en tant que type abstrait de données ?

1. AIl stocke des éléments dans l'ordre trié
2. BIl stocke des éléments sans doublons
3. CIl ne permet l'accès qu'à une seule extrémité
4. DIl stocke des paires clé–valeur

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 parcours infixe (in-order) d'un arbre binaire de recherche visite les clés dans :

1. AL'ordre d'insertion
2. BToujours l'ordre décroissant
3. CL'ordre par niveaux
4. DL'ordre croissant

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

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

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. BLes filtres de Bloom stockent les éléments complets, qui sont introuvables une fois hachés
3. CLa suppression porterait le taux de faux positifs à 100%
4. DCes bits peuvent aussi appartenir à d'autres éléments, ce qui provoquerait des faux négatifs

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. BStocker les arêtes d'un graphe
3. CRépondre à des requêtes sur intervalles (comme des sommes d'intervalles) et à des mises à jour en O(log n)
4. DImplémenter une pile