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

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

1. AFile (queue)
2. BGraphe
3. CEnsemble haché (hash set)
4. DPile (stack)

Dans un arbre, qu'est-ce qu'une feuille ?

1. AUn nœud sans enfant
2. BLe nœud de plus grande valeur
3. CUn nœud ayant exactement un enfant
4. DUn nœud sans parent

Dans un graphe non orienté, qu'est-ce que le degré d'un sommet ?

1. ALa longueur du plus long chemin partant de lui
2. BSa position dans la liste d'adjacence
3. CLe nombre de sommets du graphe
4. DLe nombre d'arêtes qui lui sont reliées

Les arbres AVL et les arbres rouge-noir garantissent :

1. AUne recherche en temps constant dans tous les cas
2. BQue les clés sont stockées dans l'ordre d'insertion
3. CUne hauteur en O(log n) grâce au rééquilibrage
4. DQu'aucun nœud n'a deux enfants

Dans une file circulaire stockée dans un tableau de capacité n, comment calcule-t-on la position suivant l'indice i ?

1. Ai + 1
2. B2i + 1
3. C(i − 1) mod n
4. D(i + 1) mod n

Quelle est la complexité temporelle de la recherche d'une clé dans un arbre binaire de recherche équilibré ?

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

Sous l'hypothèse de hachage uniforme simple, quel est le temps attendu d'une recherche dans une table de hachage à chaînage contenant n clés et m compartiments ?

1. AO(m)
2. BO(1 + α), où α = n / m
3. CO(n)
4. DO(log n)

Pour chaque élément d'un tableau, vous voulez le prochain élément plus grand à sa droite, en O(n) au total. Quelle structure aide ?

1. AUn arbre binaire de recherche reconstruit pour chaque élément
2. BUne table de hachage de tous les éléments
3. CUne file contenant toutes les paires d'éléments
4. DUne pile qui conserve les éléments en attente de leur réponse