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

Dans une liste simplement chaînée, chaque nœud contient :

1. ADes données et des références vers tous les autres nœuds
2. BDes données et un indice
3. CUniquement des données
4. DDes données et une référence vers le nœud suivant

Quelle structure de données convient le mieux à la fonction « annuler » (undo) d'un éditeur de texte ?

1. AEnsemble haché (hash set)
2. BFile (queue)
3. CPile (stack)
4. DGraphe

Que stocke un dictionnaire (map) ?

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

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. B5 4 3 2 1
3. C1 2 4 5 3
4. D4 5 2 3 1

Que se passe-t-il lorsqu'une table de hachage est rehachée après que son facteur de charge a dépassé un seuil ?

1. ALes clés existantes sont triées sur place
2. BSeules les clés en collision sont déplacées dans une nouvelle liste de débordement à la fin de la table
3. CUne table plus grande est allouée et chaque clé y est réinsérée
4. DLes clés les plus anciennes sont supprimées pour faire de la place

Quelle est la valeur de l'expression postfixée 3 4 + 2 * ?

1. A24
2. B14
3. C10
4. D11

Quel est le temps d'exécution d'un parcours en largeur sur un graphe à V sommets stocké sous forme de matrice d'adjacence ?

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

Dans le BST de racine 50, avec le sous-arbre gauche 30 (enfants 20, 40) et le sous-arbre droit 70 (enfants 60, 80), on supprime la racine en utilisant le successeur infixe. Quelle clé devient la nouvelle racine ?

1. A40
2. B60
3. C70
4. D80