Cuestionario: Structures hiérarchiques et parcours d'arbres — 12 preguntas

1. Selon la définition d’un arbre dans ce contexte, qu’est-ce que la racine ?

A. Le nœud qui possède le plus de fils dans l’arbre

B. Le nœud qui est situé au centre géométrique de l’arbre

C. Le nœud qui n’a pas de parent et qui sert de point de départ à la hiérarchie

D. Le nœud qui possède le plus de descendants dans l’arbre

Answer: (C)

Explicación

La racine d’un arbre est le nœud qui n’a pas de parent, servant de point de départ à la hiérarchie, conformément à la définition formelle d’un arbre dans ce contexte.

2. Quelle est la propriété de la racine dans un arbre selon la définition donnée ?

A. La racine a toujours au moins un fils.

B. L’arbre possède plusieurs racines.

C. La racine est un nœud interne avec plusieurs parents.

D. La racine est l’unique nœud sans parent.

Answer: (D)

Explicación

La propriété fondamentale d’un arbre, selon la définition donnée, est qu’il possède une seule racine, qui est le nœud sans parent. Cette unicité est essentielle pour garantir la structure hiérarchique de l’arbre.

3. Quel est le rôle principal des nœuds internes dans un arbre ?

A. Ils représentent les extrémités sans enfant.

B. Ils permettent de relier différentes parties de l’arbre et de structurer l’information.

C. Ils n’ont aucune fonction particulière dans la structure.

D. Ils stockent uniquement des données terminales.

Answer: (B)

Explicación

Les nœuds internes ont au moins un fils et servent à relier différentes parties de l’arbre, structurant ainsi la hiérarchie et la connectivité de la structure.

4. Quand l’arbre binaire a-t-il été formellement défini ou établi dans l’histoire de l’informatique ?

A. Dans les années 2000

B. Dans les années 1950

C. Dans les années 1960

D. Dans les années 1980

Answer: (C)

Explicación

L’arbre binaire a été formellement étudié et popularisé dans le contexte de l’informatique dès les années 1960 avec la formalisation des structures de données et des algorithmes. Les autres périodes sont incorrectes : avant l’informatique, la notion n’était pas formellement établie, et après les années 1960, la notion s’est simplement développée davantage.

5. En quoi la profondeur d’un nœud et la hauteur d’un arbre diffèrent-elles ou se ressemblent-elles?

A. La profondeur d’un nœud est une propriété locale, spécifique à ce nœud, alors que la hauteur est une propriété globale de l’arbre, correspondant à la profondeur du nœud le plus éloigné de la racine

B. La profondeur d’un nœud et la hauteur d’un arbre désignent la même notion, toutes deux mesurant la distance à la racine

C. La profondeur d’un nœud mesure sa distance à la racine, tandis que la hauteur d’un arbre est la longueur du plus long chemin de la racine à une feuille

D. La profondeur d’un nœud est la moyenne de toutes les distances à la racine pour tous les nœuds, alors que la hauteur est la distance maximale d’un nœud à la racine

Answer: (C)

Explicación

La profondeur d’un nœud indique sa distance à la racine, alors que la hauteur de l’arbre correspond à la profondeur maximale parmi tous ses nœuds, ce qui montre qu’ils sont liés mais distincts, l’un étant spécifique à un nœud, l’autre étant une propriété globale de l’arbre.

6. Qui est crédité de la formulation du concept de 'sous-arbre enraciné' en théorie des arbres en informatique ?

A. Les travaux de Donald Knuth sur l'algorithmique

B. Les articles originaux de Euler sur les arbres

C. La définition standard en théorie des arbres en informatique, souvent dans les manuels classiques

D. Les recherches de Claude Shannon sur la théorie de l'information

Answer: (C)

Explicación

La définition du 'sous-arbre enraciné' est une notion standard en théorie des arbres en informatique, généralement formulée dans la littérature académique et dans les manuels classiques d'algorithmique et structures de données, sans attribution à un seul auteur. La réponse correcte est donc la référence à la définition standard dans la littérature.

7. Quelle est la cause principale qui explique les inégalités entre la hauteur et le nombre de nœuds dans un arbre ?

A. Le nombre de feuilles dans l’arbre

B. La forme de l’arbre (étoile ou chaîne)

C. La profondeur maximale de l’arbre

D. L’arité maximale du nœud

Answer: (D)

Explicación

La cause principale des inégalités hauteur/nœuds est l’arité maximale du nœud, car elle détermine la croissance maximale ou minimale du nombre de nœuds en fonction de la hauteur.

8. Comment appliquer concrètement la transformation d’un arbre d’arité quelconque en arbre binaire ?

A. En chaînant tous les fils d’un nœud en une seule chaîne, en laissant la racine inchangée.

B. En supprimant tous les nœuds internes et en ne conservant que les feuilles.

C. En déplaçant les frères droits d’un nœud en fils droits, tout en conservant la racine et la hiérarchie.

D. En déplaçant tous les fils gauche de chaque nœud en fils droits, en conservant la racine.

Answer: (C)

Explicación

La transformation en arbre binaire consiste à chaîner tous les frères d’un même nœud en une seule chaîne, en déplaçant les frères droits en fils droits, ce qui permet de respecter la limite de deux fils par nœud tout en conservant la hiérarchie de l’arbre.

9. Quelle est la propriété fondamentale concernant la relation parent-enfant dans un arbre en informatique?

A. Chaque nœud, sauf la racine, possède un seul parent.

B. Il existe plusieurs racines dans un arbre.

C. Chaque nœud a plusieurs parents possibles.

D. Les feuilles ont toujours plusieurs parents.

Answer: (A)

Explicación

La propriété fondamentale d’un arbre est qu’il possède une racine unique, et chaque nœud (sauf la racine) possède un seul parent, ce qui garantit la hiérarchie et l’absence de cycles.

10. Qu'est-ce que le parcours en profondeur dans le contexte des arbres ?

A. Une procédure qui consiste à visiter uniquement les feuilles d’un arbre.

B. Une stratégie qui explore les nœuds en suivant un ordre aléatoire.

C. Une méthode d'exploration qui visite tous les nœuds en largeur, niveau par niveau.

D. Une technique d'exploration qui descend le plus profondément possible dans une branche avant de revenir en arrière.

Answer: (D)

Explicación

Le parcours en profondeur est une méthode d'exploration d’un arbre qui consiste à descendre le plus profondément possible dans une branche avant de revenir en arrière pour explorer les autres.

11. Quelle structure de données est principalement utilisée pour réaliser un parcours en largeur d’un arbre ou d’un graphe ?

A. Une file d’attente

B. Une liste chaînée

C. Un arbre binaire

D. Une pile

Answer: (A)

Explicación

Le parcours en largeur utilise une file d’attente pour explorer tous les nœuds d’un même niveau avant de passer au niveau suivant, ce qui garantit une exploration par niveaux.

12. Quel est le rôle principal de l'arbre de décision dans l'analyse de la complexité du tri par comparaison ?

A. Structurer les données pour optimiser la recherche d’un élément dans un tableau non trié.

B. Visualiser le processus de tri pour améliorer la compréhension pédagogique du tri par insertion.

C. Organiser les opérations d’un algorithme de tri pour réduire la consommation mémoire.

D. Représenter toutes les permutations possibles à trier, afin de déterminer le nombre minimal de comparaisons nécessaires dans le pire cas.

Answer: (D)

Explicación

L’arbre de décision représente toutes les permutations possibles à trier, permettant d’établir une borne inférieure en nombre de comparaisons nécessaires. Sa hauteur correspond au nombre maximal de comparaisons dans le pire cas, ce qui est essentiel pour analyser la complexité du tri par comparaison.