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

Dans quel ordre un parcours préfixe (preorder) d'un arbre binaire visite-t-il les nœuds ?

1. ALe sous-arbre gauche, puis le nœud, puis le sous-arbre droit
2. BLe sous-arbre gauche, puis le sous-arbre droit, puis le nœud
3. CNiveau par niveau en partant du haut
4. DLe nœud, puis le sous-arbre gauche, puis le sous-arbre droit

Quelle opération est en O(1) pour un tableau mais en O(n) pour une liste simplement chaînée ?

1. AL'accès à l'élément d'indice i
2. BLa lecture du premier élément
3. CLa suppression de l'élément de tête
4. DL'insertion en tête

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. CUne clé ne peut pas du tout être hachée
4. DLa table manque de mémoire

Quelle quantité de mémoire une liste d'adjacence utilise-t-elle pour un graphe à V sommets et E arêtes ?

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

Une table de hachage de taille 7 utilise h(k) = k mod 7 et le sondage linéaire. Après l'insertion de 10, où est stocké 17 ?

1. AÀ l'indice 3
2. BÀ l'indice 6
3. CÀ l'indice 0
4. DÀ l'indice 4

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

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

Quelle garantie les règles des arbres rouge-noir donnent-elles sur la hauteur d'un arbre à n clés ?

1. ALa hauteur est au plus 2 log₂(n + 1)
2. BLa hauteur est au plus n / 2
3. CLa hauteur vaut exactement log₂ n
4. DLa hauteur est au plus log₂ n + 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. CO(n²)
4. DExactement O(log n)