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

Quelle structure de données utilise-t-on pour effectuer un parcours en largeur (par niveaux) d'un arbre ?

1. AUne pile
2. BUne table de hachage
3. CUne file de priorité
4. DUne file

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. BL'insertion au début
3. CLa lecture du dernier élément par son indice
4. DL'accès au 5e élément

Un graphe est constitué de :

1. AUniquement des clés et des hachages
2. BUniquement une racine et des feuilles
3. CLignes et colonnes
4. DSommets (nœuds) reliés par des arêtes

Quelle condition d'équilibre un arbre AVL maintient-il en chaque nœud ?

1. ALes hauteurs des sous-arbres gauche et droit diffèrent d'au plus 1
2. BChaque nœud est colorié en rouge ou en noir
3. CToutes les feuilles sont exactement à la même profondeur
4. DLes deux sous-arbres de chaque nœud contiennent exactement le même nombre de nœuds

Un arbre binaire a pour racine 1, avec 2 comme enfant gauche et 3 comme enfant droit ; le nœud 2 a pour enfants 4 (gauche) et 5 (droit). Quel est le parcours postfixe ?

1. A4 2 5 1 3
2. B4 5 2 3 1
3. C5 4 3 2 1
4. D1 2 4 5 3

Quelle méthode de résolution des collisions stocke les clés en collision dans une liste au sein du même compartiment ?

1. ALe double hachage (double hashing)
2. BLe sondage linéaire (linear probing)
3. CLe chaînage séparé (separate chaining)
4. DLe sondage quadratique (quadratic probing)

Un nœud AVL est déséquilibré parce que le sous-arbre droit de son enfant gauche est devenu trop haut (cas gauche-droite). Quelle correction applique-t-on ?

1. AUne rotation simple à gauche sur le nœud
2. BUne rotation à droite sur l'enfant gauche, puis une rotation à gauche sur le nœud
3. CUne rotation simple à droite sur le nœud
4. DUne rotation à gauche sur l'enfant gauche, puis une rotation à droite sur le nœud

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. BExactement O(log n)
3. CO(n)
4. DO(α(n)), l'inverse de la fonction d'Ackermann, pratiquement constant