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

Un graphe est constitué de :

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

Dans une représentation d'un graphe par listes d'adjacence, que stocke-t-on pour chaque sommet ?

1. ALa liste de ses sommets voisins
2. BLe nombre total d'arêtes du graphe
3. CLe plus court chemin vers tous les autres sommets
4. DUne ligne de V valeurs booléennes

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

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

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

Quelle structure de données est utilisée par le parcours en profondeur (DFS) dans sa version itérative ?

1. AUn tas
2. BUne file
3. CUne pile
4. DUniquement une table de hachage

Un tampon circulaire (ring buffer) est couramment utilisé pour implémenter :

1. AUn parcours de graphe
2. BUn arbre binaire de recherche
3. CUne file de taille fixe
4. DUne fonction de hachage

Quelle garantie les règles des arbres rouge-noir donnent-elles sur la hauteur d'un arbre à n clés ?

1. ALa hauteur est au plus 2 log₂(n + 1)
2. BLa hauteur est au plus log₂ n + 1
3. CLa hauteur est au plus n / 2
4. DLa hauteur vaut exactement log₂ n

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. BUniquement un arbre binaire de recherche
3. CUn unique tableau trié
4. DUniquement une pile