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

Comment les éléments d'un tableau sont-ils stockés en mémoire ?

1. AÀ des emplacements aléatoires choisis par un hachage
2. BDans un seul bloc contigu, les uns à la suite des autres
3. CDe façon dispersée, reliés par des pointeurs
4. DDans un arbre de pages mémoire

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

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

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

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

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

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

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

Quelle structure de données est utilisée par le parcours en profondeur (DFS) dans sa version itérative ?

1. AUniquement une table de hachage
2. BUne pile
3. CUn tas
4. DUne file

Quelle structure permet de calculer le maximum de chaque fenêtre de taille k dans un tableau en O(n) au total ?

1. AUn tableau trié mis à jour par décalage
2. BUne liste simplement chaînée des éléments de la fenêtre
3. CUn deque contenant des indices par ordre décroissant de valeur
4. DUn tas min reconstruit pour chaque fenêtre

Pour chaque élément d'un tableau, vous voulez le prochain élément plus grand à sa droite, en O(n) au total. Quelle structure aide ?

1. AUn arbre binaire de recherche reconstruit pour chaque élément
2. BUne pile qui conserve les éléments en attente de leur réponse
3. CUne file contenant toutes les paires d'éléments
4. DUne table de hachage de tous les éléments