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

Dans un graphe, qu'est-ce qu'un cycle ?

1. AUn chemin qui commence et se termine au même sommet
2. BUn chemin qui passe par tous les sommets
3. CUne arête de poids nul
4. DUn sommet sans arête

Quelle opération est lente dans un tableau mais rapide en tête d'une liste chaînée ?

1. ALe calcul de la longueur d'un tableau de taille fixe
2. BLa lecture du dernier élément par son indice
3. CL'insertion au début
4. DL'accès au 5e élément

Dans un arbre, qu'est-ce qu'une feuille ?

1. AUn nœud sans parent
2. BLe nœud de plus grande valeur
3. CUn nœud sans enfant
4. DUn nœud ayant exactement un enfant

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. BUn tas
3. CUne pile
4. DUne file

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

Quelle est la hauteur, dans le pire des cas, d'un arbre binaire de recherche à n nœuds si les clés sont insérées dans l'ordre trié ?

1. An (il devient une liste chaînée)
2. B1
3. C√n
4. Dlog₂ n

Un arbre de segments (segment tree) est généralement utilisé pour :

1. AImplémenter une pile
2. BTrier des chaînes par ordre alphabétique en stockant chaque préfixe dans un nœud distinct de l'arbre
3. CStocker les arêtes d'un graphe
4. DRépondre à des requêtes sur intervalles (comme des sommes d'intervalles) et à des mises à jour en O(log n)

Sous l'hypothèse de hachage uniforme simple, quel est le temps attendu d'une recherche dans une table de hachage à chaînage contenant n clés et m compartiments ?

1. AO(1 + α), où α = n / m
2. BO(n)
3. CO(log n)
4. DO(m)