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

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

1. AFile (queue)
2. BTas (heap)
3. CArbre binaire
4. DPile (stack)

Dans un arbre binaire de recherche, les valeurs du sous-arbre gauche d'un nœud sont :

1. AÉgales à la valeur du nœud
2. BInférieures à la valeur du nœud
3. CDans un ordre aléatoire
4. DSupérieures à la valeur du nœud

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

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

Pourquoi le parcours d'un tableau est-il souvent bien plus rapide en pratique que celui d'une liste chaînée de même longueur ?

1. ALes listes chaînées stockent toujours leurs éléments sur disque
2. BLe parcours d'un tableau est en O(1) au total, alors que celui d'une liste chaînée est en O(n)
3. CLes tableaux utilisent moins d'instructions pour comparer les valeurs
4. DLes éléments d'un tableau sont contigus, ce qui exploite bien le cache du processeur

Un parcours infixe (in-order) d'un arbre binaire de recherche visite les clés dans :

1. AToujours l'ordre décroissant
2. BL'ordre croissant
3. CL'ordre par niveaux
4. DL'ordre d'insertion

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

1. ALe stockage de matrices
2. BLa recherche des plus courts chemins
3. CLe tri de nombres
4. DLes recherches par préfixe, comme l'autocomplétion

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[1, 3, 8, 5]
2. B[3, 1, 8, 5]
3. C[1, 3, 5, 8]
4. D[1, 5, 8, 3]

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

1. AUne recherche en O(log n) en moyenne grâce à plusieurs niveaux de pointeurs avant
2. BElle stocke les clés sans ordre
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