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

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

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

Comment les éléments d'un tableau sont-ils stockés en mémoire ?

1. ADans un seul bloc contigu, les uns à la suite des autres
2. BDe façon dispersée, reliés par des pointeurs
3. CDans un arbre de pages mémoire
4. DÀ des emplacements aléatoires choisis par un hachage

Une table de hachage stocke les données sous forme de :

1. AListe triée uniquement
2. BArbre à clés ordonnées
3. CPaires clé–valeur localisées par une fonction de hachage
4. DChaîne de longueur fixe

Quelle structure de données est utilisée par le parcours en profondeur (DFS) dans sa version itérative ?

1. AUn tas
2. BUne pile
3. CUniquement une table de hachage
4. DUne file

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(1)
3. CO(log n)
4. DO(n)

Combien de temps faut-il pour vérifier si l'arête (u, v) existe avec une matrice d'adjacence ?

1. AO(V)
2. BO(log V)
3. CO(E)
4. DO(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)
2. BO(α(n)), l'inverse de la fonction d'Ackermann, pratiquement constant
3. CExactement O(log n)
4. DO(n²)

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

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