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

Quelle structure de données fonctionne selon le principe « dernier entré, premier sorti » (LIFO) ?

1. AListe chaînée
2. BTable de hachage
3. CPile (stack)
4. DFile (queue)

Qu'est-ce qu'un deque (file à double extrémité) ?

1. AUne file qui ne permet la suppression qu'à l'arrière
2. BUne file triée par priorité
3. CUne structure qui permet l'insertion et la suppression aux deux extrémités
4. DDeux files distinctes partageant un même tableau

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

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

Comment insère-t-on un nouvel élément dans un tas binaire ?

1. AOn le place à la racine et on le fait descendre
2. BOn reconstruit entièrement le tas
3. COn l'insère à sa position triée en décalant d'un cran vers la droite tous les éléments plus grands
4. DOn le place à la fin du tableau et on le fait remonter tant qu'il viole la propriété de tas

Un trie (arbre de préfixes) est particulièrement efficace pour :

1. ALa recherche des plus courts chemins
2. BLe tri de nombres
3. CLes recherches par préfixe, comme l'autocomplétion
4. DLe stockage de matrices

Vous devez conserver les k plus petites valeurs d'un flux de n nombres en utilisant O(k) mémoire. Quelle approche fonctionne en O(n log k) ?

1. AUn tas max de taille k, dont on remplace la racine lorsqu'une valeur plus petite arrive
2. BUn tableau trié de toutes les n valeurs
3. CUn tas min contenant les n valeurs, dont on extrait les k plus petites à la fin
4. DUne file FIFO des k dernières valeurs

Quelle affirmation sur le tri par tas (heapsort) est correcte ?

1. AIl s'exécute en O(n) sur toute entrée
2. BIl est stable et nécessite O(n) mémoire supplémentaire
3. CIl nécessite un arbre binaire de recherche comme stockage supplémentaire, donc il utilise O(n) de mémoire en plus
4. DIl trie sur place en O(n log n) dans le pire cas, mais n'est pas stable