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

Que contient chaque nœud d'une liste doublement chaînée ?

1. ADes données et uniquement un pointeur vers le nœud suivant
2. BDes données et deux pointeurs, l'un vers le nœud suivant et l'autre vers le nœud d'après
3. CDes données, un pointeur vers le nœud suivant et un pointeur vers le nœud précédent
4. DDeux copies des données et un pointeur

Qu'est-ce qui définit un arbre binaire ?

1. AChaque nœud a exactement deux enfants
2. BChaque nœud stocke un nombre binaire
3. CChaque nœud a au plus deux enfants
4. DL'arbre a exactement deux niveaux

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

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

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 préfixe ?

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C4 5 2 3 1
4. D1 2 3 4 5

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

1. AO(E)
2. BO(V + E)
3. CO(log V)
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 4
2. BÀ l'indice 3
3. CÀ l'indice 0
4. DÀ l'indice 6

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

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

Pour qu'une table de hachage fonctionne correctement, quelle règle le hachage et l'égalité doivent-ils respecter ?

1. ADes clés égales doivent avoir des valeurs de hachage égales
2. BDes valeurs de hachage égales impliquent des clés égales
3. CLes valeurs de hachage doivent être des nombres premiers
4. DDes clés différentes doivent avoir des valeurs de hachage différentes