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

Dans une table de hachage, qu'est-ce qu'une collision ?

1. AUne clé ne peut pas du tout être hachée
2. BDeux clés égales sont stockées deux fois
3. CDeux clés différentes sont associées au même indice
4. DLa table manque de mémoire

Qu'est-ce que le facteur de charge d'une table de hachage ?

1. ALe nombre d'éléments stockés divisé par le nombre de compartiments
2. BLe temps nécessaire pour charger la table depuis le disque
3. CLe nombre de collisions survenues jusqu'ici
4. DLe nombre de compartiments divisé par la longueur moyenne des clés stockées

Que contient chaque nœud d'une liste doublement chaînée ?

1. ADes données et uniquement un pointeur vers le nœud suivant
2. BDeux copies des données et un pointeur
3. CDes données, un pointeur vers le nœud suivant et un pointeur vers le nœud précédent
4. DDes données et deux pointeurs, l'un vers le nœud suivant et l'autre vers le nœud d'après

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. A4 2 5 1 3
2. B1 2 3 4 5
3. C1 2 4 5 3
4. D4 5 2 3 1

Quel est le coût de l'insertion d'un élément au milieu d'un tableau de n éléments ?

1. AO(1), car l'indice est connu
2. BO(n²), car chaque élément se déplace n fois
3. CO(n), car les éléments suivants doivent être décalés
4. DO(log n), grâce à la recherche dichotomique

Quelle condition d'équilibre un arbre AVL maintient-il en chaque nœud ?

1. ALes deux sous-arbres de chaque nœud contiennent exactement le même nombre de nœuds
2. BToutes les feuilles sont exactement à la même profondeur
3. CChaque nœud est colorié en rouge ou en noir
4. DLes hauteurs des sous-arbres gauche et droit diffèrent d'au plus 1

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 déplace automatiquement la clé dans son nouveau compartiment
4. DLa table lève une erreur au moment où le champ change

Sans union par rang ni compression de chemin, quel est le coût dans le pire cas d'une seule opération find dans une structure union-find à n éléments ?

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