\documentclass[a4paper,11pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais,bloc,completemulti]{automultiplechoice}
\usepackage[french]{babel}
\usepackage{amsmath, amssymb}

\title{Arbres binaires}
\date{Numérique et sciences informatiques}

\begin{document}

\noindent\textbf{Arbres binaires} \hfill \textit{Numérique et sciences informatiques}\\[0.4em]
Nom~: \dotfill\ Prénom~: \dotfill

\bigskip

\element{terminalearbresbinaires}{
  \begin{question}{q01}
    Qu'est-ce qu'un \textbf{arbre binaire} ?
    \begin{choices}
    \wrongchoice{Un arbre dont les nœuds contiennent uniquement deux valeurs}
    \wrongchoice{Une structure linéaire avec deux pointeurs par élément}
    \wrongchoice{Un arbre généalogique}
    \correctchoice{Une structure hiérarchique où chaque nœud a au plus deux enfants (gauche et droit)}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q02}
    Combien de \textbf{racines} un arbre binaire possède-t-il ?
    \begin{choices}
    \wrongchoice{Aucune}
    \correctchoice{Exactement une}
    \wrongchoice{Cela dépend de la profondeur}
    \wrongchoice{Plusieurs, autant que de feuilles}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q03}
    Qu'est-ce qu'une \textbf{feuille} dans un arbre binaire ?
    \begin{choices}
    \wrongchoice{La racine de l'arbre}
    \wrongchoice{Un nœud à mi-hauteur de l'arbre}
    \wrongchoice{Un nœud qui a exactement deux enfants}
    \correctchoice{Un nœud qui n'a aucun enfant}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q04}
    Qu'appelle-t-on \textbf{hauteur} d'un arbre binaire ?
    \begin{choices}
    \wrongchoice{La distance entre deux feuilles}
    \wrongchoice{Le nombre de feuilles}
    \correctchoice{La longueur du plus long chemin de la racine à une feuille (compté en nombre d'arêtes)}
    \wrongchoice{Le nombre total de nœuds}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q05}
    La \textbf{profondeur} d'un nœud dans un arbre est :
    \begin{choices}
    \wrongchoice{Le nombre de feuilles sous ce nœud}
    \correctchoice{La longueur du chemin de la racine jusqu'à ce nœud}
    \wrongchoice{Le nombre de ses descendants}
    \wrongchoice{La distance jusqu'à sa feuille la plus proche}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q06}
    Dans un parcours \textbf{préfixe} (ou \textit{pre-order}), dans
quel ordre visite-t-on les nœuds ?
    \begin{choices}
    \correctchoice{Nœud, sous-arbre gauche, sous-arbre droit}
    \wrongchoice{Sous-arbre droit, nœud, sous-arbre gauche}
    \wrongchoice{Sous-arbre gauche, nœud, sous-arbre droit}
    \wrongchoice{Sous-arbre gauche, sous-arbre droit, nœud}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q07}
    Dans quel ordre s'effectue un parcours \textbf{infixe} d'un
arbre binaire ?
    \begin{choices}
    \wrongchoice{Nœud, sous-arbre gauche, sous-arbre droit}
    \wrongchoice{Sous-arbre gauche, sous-arbre droit, nœud}
    \correctchoice{Sous-arbre gauche, nœud, sous-arbre droit}
    \wrongchoice{Toutes les feuilles d'abord, puis tous les nœuds internes}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q08}
    Le parcours \textbf{postfixe} visite :
    \begin{choices}
    \correctchoice{D'abord le sous-arbre gauche, puis le sous-arbre droit, et enfin le nœud}
    \wrongchoice{Uniquement les feuilles}
    \wrongchoice{Les nœuds dans un ordre aléatoire}
    \wrongchoice{D'abord le nœud, puis les enfants}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q09}
    Le parcours en \textbf{largeur} d'un arbre :
    \begin{choices}
    \wrongchoice{Visite la branche gauche en entier avant la droite}
    \correctchoice{Visite tous les nœuds à profondeur $0$, puis $1$, puis $2$, etc.}
    \wrongchoice{Visite uniquement les nœuds internes}
    \wrongchoice{Évalue une expression arithmétique}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q10}
    La \textbf{taille} d'un arbre binaire est :
    \begin{choices}
    \wrongchoice{Le nombre d'arêtes}
    \wrongchoice{La hauteur du plus long chemin}
    \correctchoice{Le nombre total de nœuds}
    \wrongchoice{Le nombre de feuilles}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q11}
    Une implémentation simple d'un nœud d'arbre binaire en
Python utilise :
    \begin{choices}
    \wrongchoice{Une chaîne de caractères}
    \wrongchoice{Un dictionnaire avec une clé entière}
    \wrongchoice{Une liste de longueur fixe \texttt{[valeur, gauche, droite]}}
    \correctchoice{Une classe avec trois attributs (\texttt{valeur}, \texttt{gauche}, \texttt{droit}), où \texttt{gauche} et \texttt{droit} sont soit \texttt{None} soit un autre nœud}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q12}
    Quelle fonction Python calcule correctement la hauteur
d'un arbre binaire (en nombre d'arêtes, $-1$ pour l'arbre
vide) ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
def h(n):
    return n.gauche + n.droit
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def h(n):
    if n is None: return 0
    return 1 + h(n.gauche) + h(n.droit)
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def h(n):
    return len(n)
\end{lstlisting}
}
    \correctchoice{\begin{lstlisting}
def h(n):
    if n is None: return -1
    return 1 + max(h(n.gauche), h(n.droit))
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q13}
    Qu'est-ce qu'un arbre binaire \textbf{équilibré} ?
    \begin{choices}
    \wrongchoice{Un arbre où tous les nœuds ont exactement deux enfants}
    \wrongchoice{Un arbre symétrique (gauche et droite identiques)}
    \correctchoice{Un arbre où, pour chaque nœud, les hauteurs des sous-arbres gauche et droit diffèrent au plus de $1$}
    \wrongchoice{Un arbre où la racine est au centre}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q14}
    Quelle fonction Python affiche les valeurs d'un arbre
binaire en parcours \textbf{préfixe} ?
    \begin{choices}
    \correctchoice{\begin{lstlisting}
def parcours(n):
    if n is None: return
    print(n.valeur)
    parcours(n.gauche)
    parcours(n.droit)
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def parcours(n):
    print(n.valeur)
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def parcours(n):
    if n is None: return
    parcours(n.gauche)
    parcours(n.droit)
    print(n.valeur)
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def parcours(n):
    if n is None: return
    parcours(n.gauche)
    print(n.valeur)
    parcours(n.droit)
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q15}
    Un arbre binaire est dit \textbf{complet} quand :
    \begin{choices}
    \wrongchoice{Il contient au moins une feuille}
    \wrongchoice{Toutes les feuilles sont à la même profondeur}
    \correctchoice{Tous les niveaux sont entièrement remplis, sauf éventuellement le dernier qui est rempli de gauche à droite}
    \wrongchoice{La racine a un enfant gauche et un enfant droit}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q16}
    Pour un arbre binaire \textbf{plein} (chaque nœud interne a
exactement deux enfants), si $f$ est le nombre de
feuilles et $i$ le nombre de nœuds internes, quelle
relation a-t-on ?
    \begin{choices}
    \wrongchoice{Aucune relation déterministe}
    \correctchoice{$f = i + 1$}
    \wrongchoice{$f = i$}
    \wrongchoice{$f = 2 \cdot i$}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q17}
    Pour implémenter un parcours en largeur d'un arbre
binaire en Python, on utilise généralement :
    \begin{choices}
    \correctchoice{Une file (\texttt{collections.deque} avec \texttt{append} et \texttt{popleft})}
    \wrongchoice{Une variable simple}
    \wrongchoice{Une pile (\texttt{list} avec \texttt{append} et \texttt{pop})}
    \wrongchoice{Un dictionnaire trié}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q18}
    Quel est le nombre \textbf{maximum} de nœuds d'un arbre
binaire de hauteur $h$ ?
    \begin{choices}
    \wrongchoice{$h + 1$}
    \wrongchoice{$h^2$}
    \wrongchoice{$h$}
    \correctchoice{$2^{h+1} - 1$}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q19}
    Pour évaluer une expression arithmétique représentée
par un arbre (les feuilles sont des nombres, les nœuds
internes des opérateurs), on utilise un parcours :
    \begin{choices}
    \correctchoice{Postfixe}
    \wrongchoice{Infixe}
    \wrongchoice{Aléatoire}
    \wrongchoice{Préfixe}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q20}
    Pour calculer le \textbf{miroir} d'un arbre binaire
(échanger gauche et droite à chaque nœud), une approche
récursive est :
    \begin{choices}
    \wrongchoice{Échanger uniquement la racine avec la dernière feuille}
    \correctchoice{Pour chaque nœud, échanger ses deux sous-arbres puis appliquer récursivement le miroir aux sous-arbres}
    \wrongchoice{Ne rien faire}
    \wrongchoice{Trier les éléments par ordre décroissant}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q21}
    Dans un arbre binaire \textbf{non ordonné} de $n$ nœuds, la
recherche d'une valeur a une complexité au pire de :
    \begin{choices}
    \wrongchoice{$O(\log n)$}
    \correctchoice{$O(n)$}
    \wrongchoice{$O(n^2)$}
    \wrongchoice{$O(\sqrt{n})$}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q22}
    Connaissant à la fois le parcours \textbf{préfixe} et le
parcours \textbf{infixe} d'un arbre binaire (sans valeurs
dupliquées), peut-on reconstruire l'arbre de manière
unique ?
    \begin{choices}
    \wrongchoice{Seulement si l'arbre est équilibré}
    \wrongchoice{Non, il y a toujours plusieurs arbres possibles}
    \correctchoice{Oui, c'est un théorème classique}
    \wrongchoice{Cela dépend de la profondeur}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q23}
    Le \textbf{diamètre} d'un arbre binaire est :
    \begin{choices}
    \wrongchoice{La hauteur de l'arbre}
    \wrongchoice{Le nombre total de nœuds}
    \wrongchoice{Le nombre total de feuilles}
    \correctchoice{La longueur du plus long chemin entre deux nœuds (pas forcément passant par la racine)}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q24}
    Quand peut-on représenter efficacement un arbre binaire
dans un \textbf{tableau} (sans pointeurs) ?
    \begin{choices}
    \correctchoice{Quand l'arbre est complet (tous les niveaux remplis sauf éventuellement le dernier rempli de gauche à droite)}
    \wrongchoice{Quand l'arbre a moins de $10$ nœuds}
    \wrongchoice{Toujours, c'est universel}
    \wrongchoice{Jamais, c'est inefficace}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q25}
    Lequel des cas suivants utilise typiquement un arbre
binaire ?
    \begin{choices}
    \wrongchoice{Stocker une liste de courses ordinaire}
    \wrongchoice{Échanger deux variables}
    \wrongchoice{Compter le nombre de mots dans un texte}
    \correctchoice{Représenter un arbre de décision, une expression arithmétique, ou un index ordonné dynamique (arbre binaire de recherche)}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q26}
    Quelle fonction Python calcule correctement la
\textbf{taille} (nombre total de nœuds) d'un arbre
binaire ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
def taille(n):
    if n is None:
        return 0
    return 1 + max(taille(n.gauche), taille(n.droit))
\end{lstlisting}
}
    \correctchoice{\begin{lstlisting}
def taille(n):
    if n is None:
        return 0
    return 1 + taille(n.gauche) + taille(n.droit)
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def taille(n):
    if n is None:
        return 1
    return taille(n.gauche) + taille(n.droit)
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def taille(n):
    return 1
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q27}
    Quelle fonction Python compte correctement le
nombre de \textbf{feuilles} d'un arbre binaire ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
def feuilles(n):
    if n is None:
        return 1
    return feuilles(n.gauche) + feuilles(n.droit)
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def feuilles(n):
    if n is None:
        return 0
    return feuilles(n.gauche) + feuilles(n.droit)
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def feuilles(n):
    if n is None:
        return 0
    return 1 + feuilles(n.gauche) + feuilles(n.droit)
\end{lstlisting}
}
    \correctchoice{\begin{lstlisting}
def feuilles(n):
    if n is None:
        return 0
    if n.gauche is None and n.droit is None:
        return 1
    return feuilles(n.gauche) + feuilles(n.droit)
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinaires}{
  \begin{question}{q28}
    Comment calculer la \textbf{profondeur} d'un nœud
contenant la valeur \texttt{cible} dans un arbre binaire
(ou \texttt{-1} si la valeur n'est pas présente) ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
def profondeur(n, cible):
    return n.valeur - cible
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def profondeur(n, cible):
    if n.valeur == cible:
        return 0
    return 1 + profondeur(n.gauche, cible)
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def profondeur(n, cible):
    if n is None:
        return 0
    if n.valeur == cible:
        return 1
    return profondeur(n.gauche, cible) + profondeur(n.droit, cible)
\end{lstlisting}
}
    \correctchoice{\begin{lstlisting}
def profondeur(n, cible, p=0):
    if n is None:
        return -1
    if n.valeur == cible:
        return p
    g = profondeur(n.gauche, cible, p + 1)
    if g != -1:
        return g
    return profondeur(n.droit, cible, p + 1)
\end{lstlisting}
}
    \end{choices}
  \end{question}
}


\onecopy{1}{
  \shufflegroup{terminalearbresbinaires}
  \insertgroup{terminalearbresbinaires}
}

\end{document}
