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

Dans un arbre binaire de recherche, les valeurs du sous-arbre gauche d'un nœud sont :

1. AÉgales à la valeur du nœud
2. BSupérieures à la valeur du nœud
3. CDans un ordre aléatoire
4. DInférieures à la valeur du nœud

Qu'est-ce qu'un graphe orienté ?

1. AUn graphe dont les arêtes ont une direction d'un sommet vers un autre
2. BUn graphe dont toutes les arêtes ont un poids
3. CUn graphe qui n'a pas de cycle
4. DUn graphe dans lequel chaque paire de sommets distincts est reliée par une arête

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

1. An + 1
2. Bn − 1
3. C2n
4. Dn

Pourquoi le parcours d'un tableau est-il souvent bien plus rapide en pratique que celui d'une liste chaînée de même longueur ?

1. ALes listes chaînées stockent toujours leurs éléments sur disque
2. BLes éléments d'un tableau sont contigus, ce qui exploite bien le cache du processeur
3. CLe parcours d'un tableau est en O(1) au total, alors que celui d'une liste chaînée est en O(n)
4. DLes tableaux utilisent moins d'instructions pour comparer les valeurs

Quelle quantité de mémoire une liste d'adjacence utilise-t-elle pour un graphe à V sommets et E arêtes ?

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

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 5 2 3 1
3. C4 2 5 1 3
4. D1 2 4 5 3

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

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

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