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

Une table de hachage stocke les données sous forme de :

1. AListe triée uniquement
2. BChaîne de longueur fixe
3. CArbre à clés ordonnées
4. DPaires clé–valeur localisées par une fonction de hachage

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

1. An + 1
2. Bn
3. C2n
4. Dn − 1

Dans un graphe, qu'est-ce qu'un cycle ?

1. AUn sommet sans arête
2. BUn chemin qui passe par tous les sommets
3. CUne arête de poids nul
4. DUn chemin qui commence et se termine au même sommet

Combien de temps prend la recherche d'un mot de longueur L dans un trie à alphabet fixe ?

1. AO(n), où n est le nombre de mots
2. BO(log n), où n est le nombre de mots
3. CO(L × n)
4. DO(L), quel que soit le nombre de mots stockés

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 sondage linéaire (linear probing)
2. BLe chaînage séparé (separate chaining)
3. CLe sondage quadratique (quadratic probing)
4. DLe double hachage (double hashing)

Qu'est-ce qui est vrai de la matrice d'adjacence d'un graphe non orienté ?

1. AElle est symétrique par rapport à la diagonale principale
2. BElle est toujours triangulaire supérieure
3. CSa diagonale principale contient toujours des 1
4. DChaque ligne contient exactement un 1

Un nœud AVL est déséquilibré parce que le sous-arbre droit de son enfant gauche est devenu trop haut (cas gauche-droite). Quelle correction applique-t-on ?

1. AUne rotation à gauche sur l'enfant gauche, puis une rotation à droite sur le nœud
2. BUne rotation à droite sur l'enfant gauche, puis une rotation à gauche sur le nœud
3. CUne rotation simple à gauche sur le nœud
4. DUne rotation simple à droite sur le nœud

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

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