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

Quelle est la principale différence entre un tableau statique et un tableau dynamique ?

1. AUn tableau dynamique stocke ses éléments dans des nœuds chaînés, ce qui lui permet de grandir un élément à la fois
2. BUn tableau dynamique peut grandir en passant à un bloc de mémoire plus grand
3. CUn tableau statique offre un accès par indice plus lent
4. DUn tableau statique ne peut stocker que des nombres

Quelle structure est généralement utilisée pour implémenter une file de priorité ?

1. AUne liste simplement chaînée non ordonnée
2. BUne pile (stack)
3. CUn tas (heap)
4. DUne chaîne de caractères

Que stocke un dictionnaire (map) ?

1. ADes paires de clés égales
2. BDes valeurs triées par taille
3. CUniquement des valeurs dans l'ordre d'insertion
4. DDes paires clé–valeur à clés uniques

Quelle structure de données utilise-t-on pour vérifier si les parenthèses de "{[()]}" sont équilibrées ?

1. AUne pile
2. BUn arbre binaire de recherche
3. CUne file
4. DUne table de hachage

Une application a besoin de recherches rapides, mais aussi de lister les clés dans l'ordre trié et de répondre à des requêtes par intervalle. Quelle structure convient le mieux ?

1. AUn arbre binaire de recherche équilibré
2. BUne pile
3. CUne liste chaînée non triée
4. DUne table de hachage

Un réseau routier compte 100,000 carrefours, chacun relié à environ 4 autres. Quelle représentation est la plus adaptée ?

1. AUne liste d'adjacence
2. BUn tas binaire d'arêtes
3. CUne matrice d'adjacence
4. DUn unique tableau trié de sommets

Les clés 5, 3, 8, 1 sont insérées dans cet ordre dans un tas binaire min vide stocké dans un tableau. Quel est le tableau final ?

1. A[3, 1, 8, 5]
2. B[1, 3, 8, 5]
3. C[1, 3, 5, 8]
4. D[1, 5, 8, 3]

Quelle structure de données permet un cache LRU (least recently used) avec get et put en O(1) ?

1. AUniquement un arbre binaire de recherche
2. BUn unique tableau trié
3. CUniquement une pile
4. DUne table de hachage combinée à une liste doublement chaînée