Flashcards : Arbres binaires en algorithmique (55 cartes)

Toutes les cartes

1Question

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

Réponse

Une organisation linéaire.

2Question

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

Réponse

Une organisation hiérarchique.

3Question

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

Réponse

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

4Question

Combien de fils un nœud d’un arbre binaire possède-t-il au maximum ?

Réponse

Deux fils.

5Question

Comment appelle-t-on les deux fils d’un nœud d’arbre binaire ?

Réponse

Le fils gauche et le fils droit.

6Question

Comment calcule-t-on la profondeur d’un nœud ?

Réponse

En comptant les nœuds du chemin entre la racine et ce nœud.

7Question

À quelle profondeur se trouve la racine selon cette définition ?

Réponse

À la profondeur 1.

8Question

Comment définit-on la hauteur d’un arbre ?

Réponse

La profondeur maximale de ses nœuds.

9Question

Quel est le type de la racine dans le TAD arbre binaire ?

Réponse

E.

10Question

Quels attributs récursifs représentent les enfants dans le TAD arbre binaire ?

Réponse

gauche et droit, de type arbre_binaire.

11Question

Quelle est la hauteur d’un arbre vide ?

Réponse

0.

12Question

Comment calcule-t-on la hauteur d’un arbre non vide ?

Réponse

1 plus le maximum des hauteurs de ses deux sous-arbres.

13Question

Quelle est la taille d’un arbre vide ?

Réponse

0.

14Question

Comment calcule-t-on la taille d’un arbre non vide ?

Réponse

1 plus les tailles de ses deux sous-arbres.

15Question

Dans quel ordre le parcours infixe visite-t-il les nœuds d’un arbre ?

Réponse

Gauche, racine, droite (GRD).

16Question

Quel ordre distingue le parcours infixe du parcours préfixe et du parcours suffixe ?

Réponse

Le parcours infixe suit l’ordre gauche, racine, droite (GRD).

17Question

Dans quel ordre le parcours préfixe visite-t-il les nœuds d’un arbre ?

Réponse

Racine, gauche, droite (RGD).

18Question

Dans quel ordre le parcours suffixe visite-t-il les nœuds d’un arbre ?

Réponse

Gauche, droite, racine (GDR).

19Question

Que signifie BFS dans le parcours en largeur ?

Réponse

Breadth First Search.

20Question

Quel ordre d’exploration caractérise le parcours en largeur ?

Réponse

Il explore d’abord la source, puis ses successeurs et les successeurs non encore explorés de ceux-ci.

21Question

Où le parcours en largeur place-t-il la source au départ ?

Réponse

Dans une file.

22Question

Que fait le parcours en largeur avec le nœud en tête de file ?

Réponse

Il le retire et le traite.

23Question

Quand le parcours en largeur s’arrête-t-il ?

Réponse

Quand la file est vide.

24Question

Quelle relation lie les valeurs du sous-arbre gauche à chaque nœud d’un arbre binaire de recherche ?

Réponse

Elles sont inférieures ou égales à celles du nœud.

25Question

Comment les valeurs du sous-arbre droit se comparent-elles à chaque nœud d’un arbre binaire de recherche ?

Réponse

Elles sont strictement supérieures.

26Question

Quelle est la complexité temporelle moyenne de la plupart des opérations dans un arbre binaire de recherche ?

Réponse

O(log⁡n)O(\log n)

27Question

Que fait la recherche dans un arbre binaire de recherche si la clé égale la racine ?

Réponse

Elle renvoie vrai.

28Question

Comment la recherche dans un arbre binaire de recherche progresse-t-elle selon la comparaison avec la racine ?

Réponse

Elle va à gauche si la clé est inférieure et à droite si elle est supérieure.

29Question

Que renvoie la recherche dans un arbre binaire de recherche lorsqu’elle atteint un arbre vide ?

Réponse

Faux.

30Question

Comment insère-t-on une clé dans un arbre binaire de recherche non vide ?

Réponse

On la compare aux nœuds en descendant jusqu’à une feuille.

31Question

Où insère-t-on une clé inférieure à celle de la feuille atteinte ?

Réponse

Comme fils gauche de cette feuille.

32Question

Où insère-t-on une clé non inférieure à celle de la feuille atteinte ?

Réponse

Comme fils droit de cette feuille.

33Question

Qu’est-ce que la racine d’un arbre ?

Réponse

Son nœud initial.

34Question

Qu’est-ce qu’une feuille dans un arbre ?

Réponse

Un nœud qui n’a aucun fils.

35Question

Quel rôle une clé peut-elle jouer pour chaque nœud d’un arbre binaire ?

Réponse

Elle sert d’étiquette.

36Question

Comment note-t-on un arbre ou un sous-arbre vide ?

Réponse

NIL.

37Question

Un sous-arbre gauche ou droit reste-t-il un arbre lorsqu’il est vide ?

Réponse

Oui, il reste un arbre.

38Question

Quel constructeur l’interface du TAD arbre binaire prévoit-elle ?

Réponse

créerArbre.

39Question

Quels sélecteurs l’interface du TAD arbre binaire prévoit-elle ?

Réponse

get_cle, get_gauche et get_droite.

40Question

Quel prédicat l’interface du TAD arbre binaire prévoit-elle ?

Réponse

estVide.

41Question

Que désigne T.racine dans les algorithmes d’arbres ?

Réponse

La racine de T.

42Question

Que désigne T.gauche dans les algorithmes d’arbres ?

Réponse

Le sous-arbre gauche de T.

43Question

Que désigne T.droit dans les algorithmes d’arbres ?

Réponse

Le sous-arbre droit de T.

44Question

Quelle est la première étape du parcours suffixe récursif d’un arbre ?

Réponse

Traiter le sous-arbre gauche.

45Question

Quelle étape suit le traitement du sous-arbre gauche en parcours suffixe récursif ?

Réponse

Traiter le sous-arbre droit.

46Question

Quelle opération termine le parcours suffixe récursif d’un arbre ?

Réponse

Afficher la racine.

47Question

Quelle structure FIFO le parcours en largeur utilise-t-il ?

Réponse

Une file FIFO.

48Question

À quel type de fonction le parcours en largeur ne fait-il pas appel ?

Réponse

À une fonction récursive.

49Question

Quelle propriété d’ordre les éléments d’un arbre binaire de recherche doivent-ils posséder ?

Réponse

Une relation d’ordre totale permettant de comparer deux éléments.

50Question

Que devient le premier élément inséré dans un arbre binaire de recherche ?

Réponse

Il devient la racine.

51Question

Où place-t-on les éléments plus petits que le nœud dans un arbre binaire de recherche ?

Réponse

À gauche.

52Question

Où place-t-on les éléments plus grands que le nœud dans un arbre binaire de recherche ?

Réponse

À droite.

53Question

Comment la recherche dans un arbre binaire de recherche accède-t-elle aux clés ?

Réponse

Elle suit les liens de l’arbre en comparant les clés.

54Question

Comment la recherche dichotomique accède-t-elle aux éléments d’un tableau ?

Réponse

Elle y accède directement.

55Question

Quel est le mode de fonctionnement de la recherche d’une clé dans un arbre binaire de recherche ?

Réponse

Elle est récursive.

Teste-toi avec le QCM

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 ?

Faire le QCM →

Consultez la fiche

Révisez le cours complet dans la fiche de révision de Arbres binaires en algorithmique.

Voir la fiche →

Cours similaires

Crée tes propres flashcards

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

Générateur de flashcards