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

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 est la principale différence entre un tableau statique et un tableau dynamique ?

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

Quelle structure de données convient le mieux à la fonction « annuler » (undo) d'un éditeur de texte ?

1. AFile (queue)
2. BPile (stack)
3. CEnsemble haché (hash set)
4. DGraphe

Une file est implémentée avec deux piles : on empile sur une pile « in » et on dépile depuis une pile « out », remplie à partir de « in » lorsqu'elle est vide. Quel est le coût amorti par opération ?

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

Comment trouve-t-on la clé minimale dans un arbre binaire de recherche ?

1. AOn suit les enfants gauches depuis la racine jusqu'à ce qu'il n'y en ait plus
2. BOn visite toutes les feuilles et on les compare
3. COn regarde uniquement la racine
4. DOn suit les enfants droits depuis la racine jusqu'à ce qu'il n'y en ait plus

Quelle quantité de mémoire une matrice d'adjacence utilise-t-elle pour un graphe à V sommets ?

1. AO(V²)
2. BO(E)
3. CO(log V)
4. DO(V + E)

Quel est le principal avantage d'une liste à enjambements (skip list) par rapport à une liste chaînée triée ?

1. AElle stocke les clés sans ordre
2. BUne recherche en O(log n) en moyenne grâce à plusieurs niveaux de pointeurs avant
3. CUne recherche en O(1) garantie, car chaque nœud stocke un pointeur vers tous les autres nœuds
4. DElle n'utilise aucune mémoire supplémentaire

Un tableau dynamique double de taille lorsqu'il est plein. Pourquoi de nombreuses implémentations ne le réduisent-elles que lorsqu'il est rempli au quart, et non à moitié ?

1. AParce que diviser par deux à la moitié ferait perdre des éléments
2. BParce que l'allocateur de mémoire ne peut libérer la mémoire que par quarts de bloc
3. CPour éviter des redimensionnements répétés lorsque des push et des pop alternent près de la limite
4. DPour garder le tableau trié