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

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

1. AChaîne de longueur fixe
2. BListe triée uniquement
3. CPaires clé–valeur localisées par une fonction de hachage
4. DArbre à clés ordonnées

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

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

Où se trouve le plus petit élément d'un tas binaire min ?

1. ADans la feuille la plus à gauche
2. BÀ la dernière position du tableau
3. CDans une feuille quelconque, qu'il faut chercher
4. DÀ la racine

Quelle est la valeur de l'expression postfixée 3 4 + 2 * ?

1. A11
2. B24
3. C14
4. D10

Vous avez une référence vers un nœud au milieu d'une liste. Dans quelle liste pouvez-vous le supprimer en O(1) ?

1. AUne liste simplement chaînée
2. BUn tableau trié
3. CUn tableau dynamique
4. DUne liste doublement chaînée

Quelle est la complexité temporelle de la recherche d'une clé dans un arbre binaire de recherche équilibré ?

1. AO(n)
2. BO(log n)
3. CO(n log n)
4. DO(1)

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

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

Un objet est stocké comme clé dans une table de hachage (hash map), puis un champ utilisé par sa fonction de hachage est modifié. Quel est le résultat probable ?

1. ARien ne change, car le hachage d'une clé n'est calculé qu'une seule fois au démarrage du programme
2. BLa recherche de l'objet peut échouer car il se trouve dans le compartiment de son ancien hachage
3. CLa table lève une erreur au moment où le champ change
4. DLa table déplace automatiquement la clé dans son nouveau compartiment