QCM : Arbres binaires en algorithmique (18 questions)

Questions et réponses du QCM

1. Un système de fichiers doit représenter les dossiers et sous-dossiers à plusieurs niveaux de profondeur. Quelle propriété distingue le mieux une structure adaptée à cette organisation d’une liste simple ?

Elle range les éléments les uns à la suite des autres.
Elle rassemble les éléments sans relation entre eux.
Elle traite les éléments selon leur ordre d’arrivée.
Elle représente des relations hiérarchiques entre les éléments.

Elle représente des relations hiérarchiques entre les éléments.

Explication

Un arbre permet de représenter des données organisées en niveaux et liées hiérarchiquement. Un ordre séquentiel ou d’arrivée caractérise plutôt une structure linéaire, tandis qu’une collection sans relations ne représente pas les niveaux.

2. Dans un modèle de données, des éléments sont reliés de sorte que certains peuvent en contenir ou en désigner d’autres comme enfants. Quelle structure correspond à cette description ?

Un arbre composé de nœuds pouvant avoir des enfants.
Un ensemble composé d’éléments sans relation parent-enfant.
Une pile composée d’éléments empilés les uns sur les autres.
Une liste composée d’éléments placés successivement.

Un arbre composé de nœuds pouvant avoir des enfants.

Explication

Un arbre est constitué de nœuds qui peuvent avoir des enfants, eux-mêmes des nœuds. Une liste ou une pile organise les éléments de façon linéaire, et un simple ensemble ne décrit pas de relation parent-enfant.

3. Dans un arbre de données, un nœud possède trois enfants distincts. Cette structure respecte-t-elle la définition d’un arbre binaire ?

Oui, car un nœud binaire doit avoir au moins deux fils.
Oui, car les fils peuvent être en nombre quelconque.
Non, car un nœud binaire ne peut avoir aucun fils.
Non, car un nœud binaire peut avoir au plus deux fils.

Non, car un nœud binaire peut avoir au plus deux fils.

Explication

Dans un arbre binaire, chaque nœud possède au plus deux fils, distingués comme gauche et droit. « Au moins deux » inverse la limite, l’absence de fils n’est pas obligatoire, et un nombre quelconque de fils dépasse la définition.

4. Dans un arbre, le chemin de la racine au nœud M comprend cinq nœuds, racine et M comprises. Quelle est la profondeur de M ?

Une profondeur de cinq.
Une profondeur de trois.
Une profondeur de six.
Une profondeur de quatre.

Une profondeur de cinq.

Explication

La profondeur correspond au nombre de nœuds du chemin entre la racine et le nœud, et la racine compte comme profondeur 1 : M est donc à la profondeur cinq. Compter les arêtes ou omettre un nœud conduit à un résultat inférieur.

5. Les nœuds les plus profonds d’un arbre se trouvent à la profondeur 6, tandis que les autres atteignent au maximum la profondeur 4. Quelle est la hauteur de l’arbre ?

Une hauteur de cinq.
Une hauteur de six.
Une hauteur de quatre.
Une hauteur de trois.

Une hauteur de six.

Explication

La hauteur d’un arbre est la profondeur maximale de ses nœuds ; ici, elle vaut donc six. La profondeur la plus faible, le nombre de niveaux intermédiaires ou une différence de profondeurs ne définissent pas la hauteur.

6. Une structure d’arbre binaire doit représenter une racine de type E ainsi que ses deux branches, chacune pouvant elle-même être un arbre binaire. Quels attributs récursifs convient-il de définir ?

racine de type E, gauche et droit de type arbre_binaire
racine de type E et gauche de type arbre_binaire
racine, gauche et droit tous de type E
racine de type arbre_binaire et gauche et droit de type E

racine de type E, gauche et droit de type arbre_binaire

Explication

L’interface récursive comprend une racine de type E et deux attributs, gauche et droit, de type arbre_binaire. Déclarer les branches comme des clés confond sous-arbre et étiquette, tandis que l’option à une seule branche omet un attribut récursif.

7. Dans une représentation d’arbre binaire, le sous-arbre droit d’un nœud ne contient qu’un seul nœud. Comment faut-il considérer ce sous-arbre dans la structure ?

Comme un arbre à part entière
Comme une branche qui n’est pas un arbre
Comme une simple clé sans structure d’arbre
Comme un arbre seulement s’il possède deux nœuds

Comme un arbre à part entière

Explication

Un sous-arbre gauche ou droit est lui-même un arbre, y compris lorsqu’il ne contient qu’un nœud. Le réduire à une clé confond son contenu avec sa structure, et exiger deux nœuds ajoute une condition absente de la définition.

8. Un arbre non vide a un sous-arbre gauche de hauteur 2 et un sous-arbre droit de hauteur 4. Quelle est sa hauteur ?

3
4
6
5

5

Explication

La hauteur d’un arbre non vide vaut un plus le maximum des hauteurs de ses sous-arbres : 1+max⁡(2,4)=51 + \max(2,4)=5. Additionner les hauteurs donne 7, omettre la racine donne 4, et retenir la branche gauche donne 3.

9. Un arbre non vide possède un sous-arbre gauche de taille 3 et un sous-arbre droit de taille 2. Combien de nœuds contient-il ?

7
6
2
5

6

Explication

La taille d’un arbre non vide est un plus la somme des tailles de ses sous-arbres : 1+3+2=61+3+2=6. La valeur 5 oublie la racine, 7 la compte deux fois, et 2 ne correspond pas à la somme des nœuds des branches.

10. Dans un arbre binaire, un nœud possède un fils gauche et un fils droit. Quel ordre de visite respecte le parcours infixe pour ce nœud et ses sous-arbres ?

Sous-arbre gauche, sous-arbre droit, racine
Racine, sous-arbre gauche, sous-arbre droit
Sous-arbre droit, racine, sous-arbre gauche
Sous-arbre gauche, racine, sous-arbre droit

Sous-arbre gauche, racine, sous-arbre droit

Explication

Le parcours infixe traite d’abord le sous-arbre gauche, puis la racine et enfin le sous-arbre droit, soit GRD. L’ordre RGD correspond au préfixe, GDR au suffixe et D-R-G inverse l’ordre des sous-arbres.

11. Un programme visite les nœuds d’un arbre dans l’ordre gauche, racine, droite. Comment ce parcours se distingue-t-il des parcours préfixe et suffixe ?

C’est l’infixe ; le préfixe est GDR et le suffixe RGD
C’est le préfixe ; l’infixe est RGD et le suffixe GDR
C’est l’infixe ; le préfixe est RGD et le suffixe GDR
C’est le suffixe ; le préfixe est RGD et l’infixe GDR

C’est l’infixe ; le préfixe est RGD et le suffixe GDR

Explication

L’infixe suit l’ordre gauche-racine-droite (GRD), tandis que le préfixe suit racine-gauche-droite (RGD) et le suffixe gauche-droite-racine (GDR). Les confusions portent ici sur l’ordre RGD attribué à l’infixe, GDR attribué au préfixe et l’inversion des ordres préfixe et suffixe.

12. Un parcours d’arbre commence par un nœud source, visite ensuite ses successeurs, puis les successeurs non encore explorés de ceux-ci. De quel type de parcours s’agit-il ?

Un parcours en largeur, ou BFS
Un parcours en profondeur, ou DFS
Un parcours infixe, ou GRD
Un parcours suffixe, ou GDR

Un parcours en largeur, ou BFS

Explication

Le parcours en largeur explore la source, puis ses successeurs et les successeurs encore non explorés, ce qui progresse par niveaux. DFS désigne une exploration en profondeur, tandis que GRD et GDR sont des ordres de parcours en profondeur.

13. Dans un parcours en largeur, la file contient d’abord la source. Quelle action faut-il effectuer à chaque étape avant de poursuivre le traitement ?

Retirer et traiter le nœud en tête, puis ajouter au début de la file ses voisins non explorés
Retirer et traiter le dernier nœud ajouté, puis ajouter en fin de file ses voisins non explorés
Retirer et traiter le nœud en tête, puis ajouter en fin de file ses voisins non explorés
Traiter d’abord tous les descendants, puis retirer en tête le prochain nœud de la file

Retirer et traiter le nœud en tête, puis ajouter en fin de file ses voisins non explorés

Explication

Le parcours en largeur retire le nœud en tête pour le traiter, puis place ses voisins non explorés en fin de file avant de recommencer si la file n’est pas vide. Retirer le dernier ajouté inverse le fonctionnement FIFO, et ajouter les voisins au début change l’ordre prévu.

14. Dans un arbre binaire de recherche dont la racine vaut 12, quelle disposition respecte la règle des sous-arbres gauche et droit ?

À gauche, des valeurs supérieures à 12 ; à droite, des valeurs inférieures ou égales à 12
À gauche, des valeurs strictement inférieures à 12 ; à droite, des valeurs supérieures ou égales à 12
À gauche, des valeurs inférieures ou égales à 12 ; à droite, des valeurs supérieures à 12
À gauche, des valeurs inférieures ou égales à 12 ; à droite, des valeurs inférieures à 12

À gauche, des valeurs inférieures ou égales à 12 ; à droite, des valeurs supérieures à 12

Explication

Dans un arbre binaire de recherche, les valeurs du sous-arbre gauche sont inférieures ou égales au nœud, tandis que celles du sous-arbre droit lui sont strictement supérieures. Inverser les inégalités, exclure l’égalité à gauche ou l’autoriser à droite contredit cette règle.

15. Une opération courante est effectuée sur un arbre binaire de recherche de taille n, dont la forme est favorable à la navigation fondée sur l’ordre des valeurs. Quelle complexité temporelle moyenne est attendue ?

O(log⁡n)O(\log n)
O(1)O(1)
O(n2)O(n^2)
O(n)O(n)

$$O(\log n)$$

Explication

Dans le cas moyen, la plupart des opérations ont une complexité logarithmique, car l’ordre des valeurs permet de naviguer efficacement dans l’arbre. O(n)O(n) confond ce résultat avec un parcours linéaire, O(1)O(1) néglige la navigation et O(n2)O(n^2) surestime le coût des comparaisons.

16. Dans un arbre binaire de recherche, la racine vaut 18 et la clé recherchée vaut 11. Quelle branche l’algorithme explore-t-il ensuite ?

Aucune branche, car la recherche s’arrête
Les deux sous-arbres
Le sous-arbre gauche
Le sous-arbre droit

Le sous-arbre gauche

Explication

La recherche compare la clé à la racine et poursuit à gauche lorsque la clé est inférieure. Aller à droite inverse la règle de comparaison, s’arrêter conclut trop tôt, et explorer les deux branches ne suit pas le procédé décrit.

17. Un élève compare la recherche d’une clé dans un arbre binaire de recherche à la recherche dichotomique dans un tableau. Quelle différence d’accès doit-il relever ?

Dans l’arbre, elle accède directement aux éléments ; dans le tableau, elle suit des liens
Dans les deux cas, elle examine les éléments l’un après l’autre
Dans l’arbre, elle suit des liens ; dans le tableau, elle accède directement aux éléments
Dans les deux cas, elle suit des liens entre les éléments

Dans l’arbre, elle suit des liens ; dans le tableau, elle accède directement aux éléments

Explication

La recherche dans l’arbre compare les clés et suit les liens entre les nœuds, tandis que la recherche dichotomique accède directement aux éléments du tableau. L’accès direct attribué à l’arbre inverse la distinction, le suivi de liens attribué au tableau la contredit, et l’examen séquentiel ne caractérise pas ces deux méthodes.

18. Dans un arbre binaire de recherche non vide, l’insertion de la clé 18 aboutit à une feuille dont la clé est 21. Où faut-il ajouter le nouveau nœud ?

À la place de la feuille de clé 21
Comme fils gauche de la feuille de clé 21
Comme fils droit de la feuille de clé 21
Comme fils gauche du dernier nœud visité

Comme fils gauche de la feuille de clé 21

Explication

On descend dans l’arbre jusqu’à une feuille, puis une clé inférieure à celle de cette feuille est ajoutée comme fils gauche. Le fils droit inverse la comparaison, l’ajout au dernier nœud visité ignore la recherche jusqu’à une feuille, et le remplacement supprime un nœud existant.

Révisez avec les flashcards

Mémorisez les réponses avec 55 flashcards sur Arbres binaires en algorithmique.

Quelle organisation des données caractérise les tableaux, listes, piles et files ?

Une organisation linéaire.

Quelle organisation des données caractérise un arbre ?

Une organisation hiérarchique.

De quels éléments un arbre est-il composé ?

De nœuds pouvant avoir des enfants qui sont eux-mêmes des nœuds.

Voir les flashcards →

Approfondir avec la fiche

Consultez la fiche de révision complète sur Arbres binaires en algorithmique.

Voir la fiche →

Cours similaires

Crée tes propres QCM

Importe ton cours et l'IA génère des QCM avec corrections en 30 secondes.

Générateur de QCM