Arbres et graphes

Exercices corrigés

1. Dans un arbre, qu'est-ce que la racine ?

   • A.Le nœud le plus profond de l'arbre
   • B.N'importe quel nœud sans enfant
   • C.L'unique nœud qui n'a pas de parentBonne réponse
   • D.Le nœud portant la plus petite valeur

   Réponse : C — L'unique nœud qui n'a pas de parent

   La racine est le point d'entrée de l'arbre : c'est le seul nœud dont aucun autre n'est le parent. Un nœud sans enfant, c'est une feuille — l'exact opposé, et la confusion la plus fréquente au début du chapitre. Le nœud le plus profond est justement le plus éloigné de la racine, et la valeur portée n'entre pas dans la définition (sauf propriété supplémentaire, comme dans un tas).

2. Que produit le parcours infixe d'un arbre binaire de recherche ?

   • A.Les clés dans l'ordre croissantBonne réponse
   • B.Les clés dans leur ordre d'insertion
   • C.Les feuilles d'abord, puis les nœuds internes
   • D.Les clés dans l'ordre décroissant

   Réponse : A — Les clés dans l'ordre croissant

   Le parcours infixe visite le sous-arbre gauche, puis la racine, puis le sous-arbre droit. Comme dans un ABR tout le sous-arbre gauche est plus petit que la racine et tout le sous-arbre droit plus grand, la suite obtenue est nécessairement croissante. C'est d'ailleurs un excellent test : si le parcours infixe n'est pas trié, l'arbre n'est PAS un ABR. Pour l'obtenir décroissant, il suffirait d'inverser l'ordre en visitant la droite d'abord.

3. Quel est le coût de l'insertion d'une clé dans un arbre binaire de recherche de hauteur h ?

   • A.O(1), comme un accès direct par indice dans un tableau
   • B.O(n) dans tous les cas, même si l'arbre est équilibré
   • C.O(log n) dans tous les cas, même pour un arbre dégénéré
   • D.O(h) : on descend d'un niveau à chaque comparaisonBonne réponse

   Réponse : D — O(h) : on descend d'un niveau à chaque comparaison

   L'insertion consiste à descendre depuis la racine en comparant la clé à chaque nœud rencontré, jusqu'à trouver un emplacement libre. On effectue donc au plus une comparaison par NIVEAU, d'où un coût en O(h). C'est la formulation exacte à connaître. Le O(log n) n'est vrai que si l'arbre est équilibré, et le O(n) seulement dans le pire cas du peigne : les deux sont des cas particuliers de O(h).

4. Combien d'arêtes au maximum peut contenir un graphe simple non orienté à 5 sommets ?

   • A.10Bonne réponse
   • B.20
   • C.25
   • D.15

   Réponse : A — 10

   Dans un graphe simple, chaque PAIRE de sommets distincts peut porter au plus une arête. Le maximum est donc le nombre de paires : n(n − 1)/2 = 5 × 4 / 2 = 10. Vérification directe : le sommet 0 se relie à 4 autres, le sommet 1 à 3 nouveaux, puis 2, puis 1, soit 4 + 3 + 2 + 1 = 10. Répondre 20 revient à oublier de diviser par 2, ce qui compterait chaque arête deux fois ; répondre 25 utiliserait n², qui inclut à tort les boucles et les doublons.

5. Soit l'arbre binaire : racine A ; enfant gauche B, dont les enfants sont D à gauche et E à droite ; enfant droit C, sans enfant. Quel est le parcours PRÉFIXE ?

   • A.D, B, E, A, C
   • B.D, E, B, C, A
   • C.A, B, D, E, CBonne réponse
   • D.A, B, C, D, E

   Réponse : C — A, B, D, E, C

   Le parcours préfixe traite la racine AVANT ses sous-arbres : racine, gauche, droite. On écrit donc A, puis on parcourt entièrement le sous-arbre de B (B, puis D, puis E), puis celui de C (C seul). Résultat : A, B, D, E, C. L'option 1 est le parcours infixe (gauche, racine, droite), l'option 2 le parcours suffixe (gauche, droite, racine), et l'option 4 le parcours en LARGEUR, qui traite les nœuds niveau par niveau. Retiens le repère : le préfixe commence toujours par la racine, le suffixe finit toujours par elle.

6. Qu'appelle-t-on une feuille dans un arbre ?

   • A.Un nœud sans enfantBonne réponse
   • B.Le nœud de départ du parcours
   • C.Un nœud ayant exactement deux enfants
   • D.La racine de l'arbre

   Réponse : A — Un nœud sans enfant

   Une feuille est un nœud qui ne possède aucun enfant : c'est un point terminal de l'arbre, le bout d'une branche. Les autres nœuds sont dits internes. Le nœud de départ d'un parcours, c'est la racine — qui n'est une feuille que dans le cas très particulier d'un arbre réduit à un seul nœud.

7. Dans un arbre binaire, combien d'enfants un nœud peut-il avoir au maximum ?

   • A.1
   • B.3
   • C.Autant que l'on veut
   • D.2Bonne réponse

   Réponse : D — 2

   C'est le sens même du mot « binaire » : au plus deux enfants par nœud, un à gauche et un à droite. Attention à la nuance « au plus » : un nœud peut parfaitement n'avoir qu'un seul enfant, voire aucun (c'est alors une feuille). Et ces deux enfants sont DISTINGUÉS : n'avoir qu'un enfant gauche n'est pas la même chose que n'avoir qu'un enfant droit.

8. Que désigne la taille d'un arbre ?

   • A.Sa hauteur
   • B.Son nombre de nœudsBonne réponse
   • C.Son nombre de feuilles
   • D.La longueur de sa plus longue branche

   Réponse : B — Son nombre de nœuds

   La taille, c'est le nombre total de nœuds de l'arbre — racine comprise, feuilles comprises. La hauteur est une notion différente : c'est la profondeur maximale, autrement dit la longueur de la plus longue branche (options 1 et 4, qui disent la même chose). Deux arbres de même taille peuvent avoir des hauteurs très différentes : c'est exactement ce qui oppose un arbre équilibré et un peigne.

9. Dans un graphe non orienté, que représente une arête ?

   • A.Une relation entre deux sommets, valable dans les deux sensBonne réponse
   • B.Une relation d'un sommet vers lui-même uniquement
   • C.Une relation entre trois sommets
   • D.Une relation entre un sommet et une autre arête

   Réponse : A — Une relation entre deux sommets, valable dans les deux sens

   Une arête relie deux sommets par une relation SYMÉTRIQUE : si u est relié à v, alors v est relié à u. C'est la différence avec le graphe orienté, où l'arc a un sens et où u vers v n'implique pas v vers u. Une relation d'un sommet vers lui-même s'appelle une boucle, et n'existe pas dans les graphes simples ; quant aux arêtes, elles relient des sommets, jamais d'autres arêtes.

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

    • A.Le nombre total de sommets du graphe
    • B.Sa distance à la racine
    • C.Le nombre d'arêtes qui lui sont incidentes, donc son nombre de voisinsBonne réponse
    • D.Le nombre de chemins qui passent par ce sommet

    Réponse : C — Le nombre d'arêtes qui lui sont incidentes, donc son nombre de voisins

    Le degré compte les arêtes qui touchent le sommet, c'est-à-dire ses voisins directs. Si le sommet 0 est relié à 1 et à 2, son degré vaut 2. La notion de racine n'existe pas dans un graphe quelconque (elle est propre aux arbres), et le nombre de chemins passant par un sommet est une tout autre grandeur, généralement bien plus grande que le degré.

11. Avec la convention « hauteur = nombre d'arêtes du plus long chemin partant de la racine », quelle est la hauteur d'un arbre réduit à sa seule racine ?

    • A.−1
    • B.0Bonne réponse
    • C.1
    • D.2

    Réponse : B — 0

    S'il n'y a qu'un seul nœud, il n'y a aucune arête à parcourir : le plus long chemin depuis la racine a une longueur de 0. La hauteur vaut donc 0. La valeur −1 est réservée à l'arbre VIDE, ce qui rend la formule cohérente : ajouter une racine au-dessus d'un arbre vide fait bien passer la hauteur de −1 à 0. Attention en devoir : certains manuels comptent les nœuds plutôt que les arêtes et trouvent alors 1. Lis toujours la convention de l'énoncé.

12. Quelle propriété caractérise un arbre binaire de recherche (ABR) ?

    • A.Les feuilles sont rangées par ordre croissant de gauche à droite
    • B.Tous les nœuds ont exactement deux enfants
    • C.La racine porte forcément la plus petite clé
    • D.Pour tout nœud, les clés du sous-arbre gauche lui sont inférieures et celles du sous-arbre droit lui sont supérieuresBonne réponse

    Réponse : D — Pour tout nœud, les clés du sous-arbre gauche lui sont inférieures et celles du sous-arbre droit lui sont supérieures

    La propriété d'ABR est locale mais doit être vérifiée en TOUT nœud, pas seulement à la racine : c'est une définition récursive. Comparer uniquement un nœud à ses deux enfants directs ne suffit pas — c'est l'erreur classique. Un ABR n'impose rien sur le nombre d'enfants, et sa racine n'est ni le minimum ni le maximum : le minimum est le nœud le plus à gauche, le maximum le plus à droite.