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

Que stocke un dictionnaire (map) ?

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

Combien d'arêtes possède un arbre à n nœuds ?

1. An + 1
2. B2n
3. Cn
4. Dn − 1

La profondeur d'un nœud dans un arbre est :

1. ALe nombre d'arêtes de la racine jusqu'à ce nœud
2. BLe nombre de nœuds de son sous-arbre
3. CLe nombre d'arêtes de ce nœud jusqu'à la feuille la plus profonde
4. DLe nombre d'enfants de ce nœud

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

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

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

1. AUne pile
2. BUn arbre binaire de recherche
3. CUne table de hachage
4. DUne file

Dans un tas binaire min stocké dans un tableau (indices commençant à 0), les enfants du nœud d'indice i se trouvent aux indices :

1. Ai/2 et i/2 + 1
2. Bi + 1 et i + 2
3. C2i + 1 et 2i + 2
4. D2i et 2i + 1

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

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

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