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.
Combien de fils un nœud d’un arbre binaire possède-t-il au maximum ?
Deux fils.
Comment appelle-t-on les deux fils d’un nœud d’arbre binaire ?
Le fils gauche et le fils droit.
Comment calcule-t-on la profondeur d’un nœud ?
En comptant les nœuds du chemin entre la racine et ce nœud.
À quelle profondeur se trouve la racine selon cette définition ?
À la profondeur 1.
Comment définit-on la hauteur d’un arbre ?
La profondeur maximale de ses nœuds.
Quel est le type de la racine dans le TAD arbre binaire ?
E.
Quels attributs récursifs représentent les enfants dans le TAD arbre binaire ?
gauche et droit, de type arbre_binaire.
Quelle est la hauteur d’un arbre vide ?
0.
Comment calcule-t-on la hauteur d’un arbre non vide ?
1 plus le maximum des hauteurs de ses deux sous-arbres.
Quelle est la taille d’un arbre vide ?
0.
Comment calcule-t-on la taille d’un arbre non vide ?
1 plus les tailles de ses deux sous-arbres.
Dans quel ordre le parcours infixe visite-t-il les nœuds d’un arbre ?
Gauche, racine, droite (GRD).
Quel ordre distingue le parcours infixe du parcours préfixe et du parcours suffixe ?
Le parcours infixe suit l’ordre gauche, racine, droite (GRD).
Dans quel ordre le parcours préfixe visite-t-il les nœuds d’un arbre ?
Racine, gauche, droite (RGD).
Dans quel ordre le parcours suffixe visite-t-il les nœuds d’un arbre ?
Gauche, droite, racine (GDR).
Que signifie BFS dans le parcours en largeur ?
Breadth First Search.
Quel ordre d’exploration caractérise le parcours en largeur ?
Il explore d’abord la source, puis ses successeurs et les successeurs non encore explorés de ceux-ci.
Où le parcours en largeur place-t-il la source au départ ?
Dans une file.
Que fait le parcours en largeur avec le nœud en tête de file ?
Il le retire et le traite.
Quand le parcours en largeur s’arrête-t-il ?
Quand la file est vide.
Quelle relation lie les valeurs du sous-arbre gauche à chaque nœud d’un arbre binaire de recherche ?
Elles sont inférieures ou égales à celles du nœud.
Comment les valeurs du sous-arbre droit se comparent-elles à chaque nœud d’un arbre binaire de recherche ?
Elles sont strictement supérieures.
Quelle est la complexité temporelle moyenne de la plupart des opérations dans un arbre binaire de recherche ?
Que fait la recherche dans un arbre binaire de recherche si la clé égale la racine ?
Elle renvoie vrai.
Comment la recherche dans un arbre binaire de recherche progresse-t-elle selon la comparaison avec la racine ?
Elle va à gauche si la clé est inférieure et à droite si elle est supérieure.
Que renvoie la recherche dans un arbre binaire de recherche lorsqu’elle atteint un arbre vide ?
Faux.
Comment insère-t-on une clé dans un arbre binaire de recherche non vide ?
On la compare aux nœuds en descendant jusqu’à une feuille.
Où insère-t-on une clé inférieure à celle de la feuille atteinte ?
Comme fils gauche de cette feuille.
Où insère-t-on une clé non inférieure à celle de la feuille atteinte ?
Comme fils droit de cette feuille.
Qu’est-ce que la racine d’un arbre ?
Son nœud initial.
Qu’est-ce qu’une feuille dans un arbre ?
Un nœud qui n’a aucun fils.
Quel rôle une clé peut-elle jouer pour chaque nœud d’un arbre binaire ?
Elle sert d’étiquette.
Comment note-t-on un arbre ou un sous-arbre vide ?
NIL.
Un sous-arbre gauche ou droit reste-t-il un arbre lorsqu’il est vide ?
Oui, il reste un arbre.
Quel constructeur l’interface du TAD arbre binaire prévoit-elle ?
créerArbre.
Quels sélecteurs l’interface du TAD arbre binaire prévoit-elle ?
get_cle, get_gauche et get_droite.
Quel prédicat l’interface du TAD arbre binaire prévoit-elle ?
estVide.
Que désigne T.racine dans les algorithmes d’arbres ?
La racine de T.
Que désigne T.gauche dans les algorithmes d’arbres ?
Le sous-arbre gauche de T.
Que désigne T.droit dans les algorithmes d’arbres ?
Le sous-arbre droit de T.
Quelle est la première étape du parcours suffixe récursif d’un arbre ?
Traiter le sous-arbre gauche.
Quelle étape suit le traitement du sous-arbre gauche en parcours suffixe récursif ?
Traiter le sous-arbre droit.
Quelle opération termine le parcours suffixe récursif d’un arbre ?
Afficher la racine.
Quelle structure FIFO le parcours en largeur utilise-t-il ?
Une file FIFO.
À quel type de fonction le parcours en largeur ne fait-il pas appel ?
À une fonction récursive.
Quelle propriété d’ordre les éléments d’un arbre binaire de recherche doivent-ils posséder ?
Une relation d’ordre totale permettant de comparer deux éléments.
Que devient le premier élément inséré dans un arbre binaire de recherche ?
Il devient la racine.
Où place-t-on les éléments plus petits que le nœud dans un arbre binaire de recherche ?
À gauche.
Où place-t-on les éléments plus grands que le nœud dans un arbre binaire de recherche ?
À droite.
Comment la recherche dans un arbre binaire de recherche accède-t-elle aux clés ?
Elle suit les liens de l’arbre en comparant les clés.
Comment la recherche dichotomique accède-t-elle aux éléments d’un tableau ?
Elle y accède directement.
Quel est le mode de fonctionnement de la recherche d’une clé dans un arbre binaire de recherche ?
Elle est récursive.
Teste tes connaissances avec un QCM de 18 questions sur Arbres binaires en algorithmique.
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 ?
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 ?
Révisez le cours complet dans la fiche de révision de Arbres binaires en algorithmique.
Voir la fiche →Importe ton cours et l'IA génère des flashcards en 30 secondes.
Générateur de flashcards