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

Combien d'arêtes possède un arbre à n nœuds ?

1. An
2. Bn − 1
3. C2n
4. Dn + 1

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

1. AUne file qui ne permet la suppression qu'à l'arrière
2. BUne structure qui permet l'insertion et la suppression aux deux extrémités
3. CUne file triée par priorité
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 statique ne peut stocker que des nombres
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 dynamique stocke ses éléments dans des nœuds chaînés, ce qui lui permet de grandir un élément à la fois

Quel type abstrait de données l'algorithme de Dijkstra utilise-t-il pour choisir le prochain sommet à traiter ?

1. AUne pile
2. BUn ensemble sans ordre
3. CUne file FIFO
4. DUne file de priorité min

Vous avez une référence vers un nœud au milieu d'une liste. Dans quelle liste pouvez-vous le supprimer en O(1) ?

1. AUne liste doublement chaînée
2. BUn tableau dynamique
3. CUne liste simplement chaînée
4. DUn tableau trié

Combien de nœuds possède un arbre binaire parfait de hauteur h, la hauteur étant comptée en arêtes ?

1. A2h + 1
2. Bh²
3. C2^h
4. D2^h+1 − 1

La structure union-find (ensembles disjoints) avec union par rang et compression de chemin a un coût amorti par opération de :

1. AO(α(n)), l'inverse de la fonction d'Ackermann, pratiquement constant
2. BO(n²)
3. CO(n)
4. DExactement O(log n)

Pourquoi les bases de données utilisent-elles souvent des arbres B+ plutôt que de simples B-arbres pour leurs index ?

1. ATous les enregistrements sont dans des feuilles chaînées, ce qui rend les parcours d'intervalle efficaces
2. BLes arbres B+ n'ont pas besoin d'être équilibrés
3. CLes arbres B+ ne stockent les données que dans la racine
4. DLes arbres B+ utilisent des nœuds internes binaires, ce qui réduit le nombre de lectures sur disque