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

Que stocke un dictionnaire (map) ?

1. AUniquement des valeurs dans l'ordre d'insertion
2. BDes valeurs triées par taille
3. CDes paires de clés égales
4. DDes paires clé–valeur à clés uniques

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 ayant exactement un enfant
4. DUn nœud sans enfant

Dans une table de hachage, qu'est-ce qu'une collision ?

1. ADeux clés égales sont stockées deux fois
2. BDeux clés différentes sont associées au même indice
3. CLa table manque de mémoire
4. DUne clé ne peut pas du tout être hachée

Quelle structure de données utilise-t-on pour vérifier si les parenthèses de "{[()]}" sont équilibrées ?

1. AUn arbre binaire de recherche
2. BUne table de hachage
3. CUne pile
4. DUne file

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

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

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

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

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

Sans union par rang ni compression de chemin, quel est le coût dans le pire cas d'une seule opération find dans une structure union-find à n éléments ?

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