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

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

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

Qu'est-ce qu'un graphe pondéré ?

1. AUn graphe dans lequel chaque arête a une valeur numérique, comme un coût ou une distance
2. BUn graphe dans lequel certains sommets sont plus lourds que d'autres parce qu'ils ont plus d'arêtes
3. CUn graphe stocké sur disque
4. DUn graphe ayant plus d'arêtes que de sommets

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

1. ALe nombre de nœuds de son sous-arbre
2. BLe nombre d'enfants de ce nœud
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

Dans un tas binaire min stocké dans un tableau (indices commençant à 0), les enfants du nœud d'indice i se trouvent aux indices :

1. Ai + 1 et i + 2
2. B2i + 1 et 2i + 2
3. Ci/2 et i/2 + 1
4. D2i et 2i + 1

Que se passe-t-il lorsqu'une table de hachage est rehachée après que son facteur de charge a dépassé un seuil ?

1. ALes clés les plus anciennes sont supprimées pour faire de la place
2. BLes clés existantes sont triées sur place
3. CSeules les clés en collision sont déplacées dans une nouvelle liste de débordement à la fin de la table
4. DUne table plus grande est allouée et chaque clé y est réinsérée

Quelle méthode de résolution des collisions stocke les clés en collision dans une liste au sein du même compartiment ?

1. ALe double hachage (double hashing)
2. BLe sondage quadratique (quadratic probing)
3. CLe sondage linéaire (linear probing)
4. DLe chaînage séparé (separate chaining)

Comment détecter si une liste simplement chaînée contient un cycle avec O(1) mémoire supplémentaire ?

1. ATrier la liste et chercher des doublons
2. BCompter les nœuds jusqu'à dépasser le champ de longueur de la liste
3. CAvancer un pointeur d'un pas et un autre de deux pas, et vérifier s'ils se rencontrent
4. DStocker chaque nœud visité dans un ensemble haché

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

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