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

Comment s'appelle l'opération de file qui retire l'élément situé à l'avant ?

1. APush (empiler)
2. BInsert (insérer)
3. CDequeue (défiler)
4. DEnqueue (enfiler)

Qu'est-ce que la propriété de tas max ?

1. ALes clés sont triées de gauche à droite
2. BLa clé de chaque enfant gauche est supérieure ou égale à celle de son frère droit
3. CToutes les feuilles contiennent la clé maximale
4. DLa clé de chaque parent est supérieure ou égale aux clés de ses enfants

Quelle opération est en O(1) pour un tableau mais en O(n) pour une liste simplement chaînée ?

1. ALa lecture du premier élément
2. BL'accès à l'élément d'indice i
3. CLa suppression de l'élément de tête
4. DL'insertion en tête

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(E²)
3. CO(V²)
4. DO(V + E)

Les clés 50, 30, 70, 20, 40 sont insérées dans cet ordre dans un arbre binaire de recherche vide. Quel est l'enfant gauche de 30 ?

1. A70
2. B50
3. C20
4. D40

Un arbre binaire a pour racine 1, avec 2 comme enfant gauche et 3 comme enfant droit ; le nœud 2 a pour enfants 4 (gauche) et 5 (droit). Quel est le parcours préfixe ?

1. A1 2 3 4 5
2. B1 2 4 5 3
3. C4 2 5 1 3
4. D4 5 2 3 1

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

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

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

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