\documentclass[a4paper,11pt]{article}

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

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

\begin{document}

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

\bigskip

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q01}
    Quelle est la \textbf{propriété fondamentale} d'un
arbre binaire de recherche ?
    \begin{choices}
    \wrongchoice{Toutes les feuilles se trouvent au même niveau}
    \wrongchoice{Chaque nœud possède exactement deux enfants}
    \correctchoice{Pour chaque nœud, toutes les valeurs du sous-arbre gauche sont strictement inférieures à la valeur du nœud, et toutes celles du sous-arbre droit lui sont strictement supérieures}
    \wrongchoice{La racine contient la plus grande valeur de l'arbre}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q02}
    Dans un arbre binaire de recherche \textbf{équilibré}
contenant $n$ éléments, quelle est la complexité
de la recherche d'une valeur ?
    \begin{choices}
    \wrongchoice{$O(n^2)$}
    \wrongchoice{$O(1)$}
    \wrongchoice{$O(n)$}
    \correctchoice{$O(\log n)$}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q03}
    Quelle est la complexité de la recherche dans
un arbre binaire de recherche dans le \textbf{pire
cas}, sans contrainte d'équilibrage ?
    \begin{choices}
    \wrongchoice{$O(\sqrt{n})$}
    \wrongchoice{$O(\log n)$ dans tous les cas}
    \wrongchoice{$O(n^2)$}
    \correctchoice{$O(n)$, lorsque l'arbre a dégénéré en peigne et que chaque nœud n'a qu'un enfant}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q04}
    Que donne un parcours \textbf{infixe} sur un arbre
binaire de recherche ?
    \begin{choices}
    \wrongchoice{Les valeurs dans un ordre aléatoire}
    \correctchoice{Les valeurs dans l'ordre croissant}
    \wrongchoice{Les valeurs dans l'ordre décroissant}
    \wrongchoice{Aucune valeur particulière n'est visitée}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q05}
    Pour insérer une valeur $v$ dans un arbre
binaire de recherche, on procède de la manière
suivante :
    \begin{choices}
    \correctchoice{On descend dans l'arbre en comparant la valeur avec chaque nœud rencontré, puis on l'insère comme nouvelle feuille à la place vide trouvée}
    \wrongchoice{On trie les valeurs, puis on la place}
    \wrongchoice{On la place toujours à la racine}
    \wrongchoice{On la place dans la première feuille rencontrée, sans comparaison}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q06}
    La \textbf{suppression} d'un nœud dans un arbre
binaire de recherche est plus délicate que
l'insertion. Pourquoi ?
    \begin{choices}
    \wrongchoice{Parce qu'il faut détruire l'arbre puis le reconstruire entièrement}
    \correctchoice{Parce que selon que le nœud à supprimer a $0$, $1$ ou $2$ enfants, le traitement est différent, et le cas à deux enfants demande de remplacer le nœud par son successeur (ou son prédécesseur)}
    \wrongchoice{Parce qu'il faut entièrement re-trier l'arbre après chaque suppression}
    \wrongchoice{Parce qu'il est impossible de supprimer un nœud dans un arbre binaire de recherche}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q07}
    Quel est l'\textbf{avantage} d'un arbre binaire de
recherche équilibré par rapport à un tableau
trié ?
    \begin{choices}
    \wrongchoice{La recherche y est plus rapide}
    \wrongchoice{Aucune différence n'existe entre les deux structures}
    \correctchoice{L'insertion et la suppression y sont en $O(\log n)$, alors qu'elles coûtent $O(n)$ dans un tableau trié, à cause du décalage des éléments}
    \wrongchoice{Il consomme moins de mémoire qu'un tableau}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q08}
    On insère successivement les valeurs $5$, $3$,
$7$, $1$, $4$ dans un arbre binaire de
recherche initialement vide. Que devient la
racine ?
    \begin{choices}
    \correctchoice{$5$}
    \wrongchoice{$7$}
    \wrongchoice{$1$}
    \wrongchoice{$4$}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q09}
    Lequel des cas suivants est un usage typique
d'un arbre binaire de recherche ?
    \begin{choices}
    \correctchoice{Maintenir dynamiquement un ensemble trié de valeurs avec des ajouts, des suppressions et des recherches fréquentes}
    \wrongchoice{Compter le nombre de mots dans un texte}
    \wrongchoice{Afficher une image}
    \wrongchoice{Calculer la somme des éléments d'une liste}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q10}
    Quelle fonction Python recherche correctement
la valeur \texttt{v} dans un arbre binaire de
recherche ?
    \begin{choices}
    \correctchoice{\begin{lstlisting}
def chercher(n, v):
    if n is None: return False
    if v == n.valeur: return True
    if v < n.valeur:
        return chercher(n.gauche, v)
    return chercher(n.droit, v)
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def chercher(n, v):
    return v == n.valeur
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def chercher(n, v):
    return True
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def chercher(n, v):
    if n is None: return False
    if n.valeur == v: return True
    return chercher(n.gauche, v) or chercher(n.droit, v)
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q11}
    Un arbre AVL est un arbre binaire de
recherche auto-équilibré. Quelle contrainte
maintient-il pour rester équilibré ?
    \begin{choices}
    \correctchoice{Pour chaque nœud, les hauteurs des sous-arbres gauche et droit ne diffèrent jamais de plus de $1$}
    \wrongchoice{Tous les chemins de la racine aux feuilles ont la même longueur}
    \wrongchoice{Tous les sous-arbres doivent avoir la même taille}
    \wrongchoice{La racine doit toujours être la valeur médiane des valeurs présentes}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q12}
    Les arbres rouge-noir sont une autre famille
d'arbres binaires de recherche
auto-équilibrés. Quelle est leur particularité
par rapport aux arbres AVL ?
    \begin{choices}
    \wrongchoice{Ils n'autorisent que les insertions, et pas les suppressions}
    \wrongchoice{Ils sont parfaitement équilibrés}
    \wrongchoice{Ils utilisent un tri par tas en interne}
    \correctchoice{Ils tolèrent un déséquilibre légèrement supérieur (la hauteur reste majorée par $2 \log n$), en échange d'opérations d'équilibrage moins fréquentes}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q13}
    Dans un arbre binaire de recherche \textbf{non
équilibré}, quelle séquence d'insertions
conduit au pire cas (forme dégénérée) ?
    \begin{choices}
    \wrongchoice{Insérer les valeurs en commençant par la médiane}
    \wrongchoice{Insérer une seule valeur}
    \wrongchoice{Insérer les valeurs dans un ordre aléatoire}
    \correctchoice{Insérer les valeurs déjà triées, par ordre croissant ou décroissant}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q14}
    Comment obtenir efficacement les valeurs
\textbf{triées} d'un arbre binaire de recherche ?
    \begin{choices}
    \wrongchoice{Trier les valeurs à chaque opération}
    \wrongchoice{Ne renvoyer que les feuilles de l'arbre}
    \wrongchoice{Effectuer un parcours préfixe}
    \correctchoice{Effectuer un parcours infixe, qui visite naturellement les valeurs en ordre croissant}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q15}
    Quelle fonction Python insère correctement la
valeur \texttt{v} dans un arbre binaire de
recherche, en renvoyant la nouvelle racine ?
    \begin{choices}
    \correctchoice{\begin{lstlisting}
def inserer(n, v):
    if n is None: return Noeud(v)
    if v < n.valeur:
        n.gauche = inserer(n.gauche, v)
    else:
        n.droit = inserer(n.droit, v)
    return n
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def inserer(n, v):
    return Noeud(v)
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def inserer(n, v):
    n.valeur = v
    return n
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def inserer(n, v):
    n.gauche = Noeud(v)
    return n
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q16}
    Pour construire un arbre binaire de recherche
équilibré à partir d'un tableau trié, quelle
stratégie est la plus simple ?
    \begin{choices}
    \wrongchoice{Insérer les éléments dans un ordre aléatoire}
    \wrongchoice{Insérer les éléments dans l'ordre du tableau}
    \correctchoice{Prendre l'élément du milieu comme racine, puis construire récursivement le sous-arbre gauche à partir de la moitié inférieure et le sous-arbre droit à partir de la moitié supérieure}
    \wrongchoice{Insérer les éléments du dernier au premier}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q17}
    Lorsque la recherche d'une valeur \textbf{absente}
se termine dans un arbre binaire de recherche,
à quel endroit s'arrête-t-on ?
    \begin{choices}
    \wrongchoice{À la racine de l'arbre}
    \wrongchoice{La fonction lève une exception}
    \correctchoice{À un sous-arbre vide (\texttt{None}), preuve que la valeur n'est pas présente dans l'arbre}
    \wrongchoice{À une feuille, peu importe sa valeur}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q18}
    Pour vérifier qu'un arbre binaire respecte la
propriété d'arbre binaire de recherche, il
\textbf{ne suffit pas} de vérifier localement à
chaque nœud que :
    \begin{choices}
    \wrongchoice{Les feuilles se trouvent toutes au même niveau}
    \wrongchoice{La hauteur des sous-arbres est équilibrée}
    \correctchoice{L'enfant gauche est plus petit et l'enfant droit est plus grand. Il faut aussi vérifier que toutes les valeurs du sous-arbre gauche sont inférieures (et symétriquement pour le sous-arbre droit)}
    \wrongchoice{La valeur du nœud est la moyenne de celles de ses enfants}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q19}
    Comparé à une \textbf{table de hachage}, quel est
l'\textbf{avantage} d'un arbre binaire de
recherche ?
    \begin{choices}
    \correctchoice{Il maintient les éléments dans l'ordre, ce qui permet de répondre à des requêtes par intervalle ou de retrouver le voisin le plus proche}
    \wrongchoice{Il consomme moins de mémoire}
    \wrongchoice{Il est plus simple à implémenter}
    \wrongchoice{La recherche y est plus rapide}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q20}
    On insère successivement les valeurs $5$,
$2$, $8$, $1$, $3$ dans un arbre binaire de
recherche initialement vide. Quel est le
résultat de son parcours infixe ?
    \begin{choices}
    \wrongchoice{$8, 5, 3, 2, 1$ (ordre décroissant)}
    \correctchoice{$1, 2, 3, 5, 8$ (ordre croissant)}
    \wrongchoice{$5, 2, 1, 3, 8$ (parcours préfixe)}
    \wrongchoice{$5, 2, 8, 1, 3$ (ordre d'insertion)}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q21}
    Pour supprimer un nœud à \textbf{deux enfants} dans
un arbre binaire de recherche, par quoi le
remplace-t-on ?
    \begin{choices}
    \wrongchoice{Par le sous-arbre gauche complet}
    \wrongchoice{Par la racine de l'arbre}
    \wrongchoice{Par une feuille choisie au hasard}
    \correctchoice{Par son successeur infixe (le plus petit nœud du sous-arbre droit) ou par son prédécesseur infixe (le plus grand du sous-arbre gauche)}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q22}
    Pour un arbre binaire de recherche construit
en insérant $n$ valeurs \textbf{dans un ordre
aléatoire}, quelle est la hauteur attendue ?
    \begin{choices}
    \wrongchoice{$\Theta(\sqrt{n})$}
    \wrongchoice{$\Theta(n)$}
    \correctchoice{$\Theta(\log n)$}
    \wrongchoice{$\Theta(1)$}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q23}
    Le tri par arbre binaire de recherche, qui
consiste à insérer $n$ valeurs dans un arbre
puis à effectuer un parcours infixe, a une
complexité de :
    \begin{choices}
    \wrongchoice{$O(n!)$}
    \correctchoice{$O(n \log n)$ en moyenne (avec un ordre aléatoire), mais $O(n^2)$ dans le pire cas (ordre déjà trié)}
    \wrongchoice{$O(n)$}
    \wrongchoice{$O(2^n)$}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q24}
    Étant donné un nœud $n$ dans un arbre binaire
de recherche, comment trouver son
\textbf{successeur infixe}, c'est-à-dire la valeur
immédiatement supérieure ?
    \begin{choices}
    \wrongchoice{La racine de l'arbre est toujours le successeur}
    \wrongchoice{En descendant toujours à gauche}
    \wrongchoice{Le successeur est choisi au hasard parmi les autres nœuds}
    \correctchoice{Si le nœud $n$ a un sous-arbre droit, son successeur est le nœud le plus à gauche de ce sous-arbre. Sinon, c'est le premier ancêtre dont $n$ se trouve dans le sous-arbre gauche}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q25}
    Lequel des cas suivants justifie l'usage
d'un arbre binaire de recherche
auto-équilibré plutôt qu'une autre structure
?
    \begin{choices}
    \correctchoice{Implémenter un dictionnaire dont les clés sont triées dynamiquement, avec des recherches par intervalle fréquentes}
    \wrongchoice{Calculer la somme des éléments d'une grande liste}
    \wrongchoice{Stocker une liste fixe de noms à afficher}
    \wrongchoice{Trier $1\,000$ entiers une seule fois}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q26}
    On part d'un arbre binaire de recherche
vide. On y insère successivement les valeurs
$10, 5, 15, 3, 7, 12$. À quoi ressemble la
structure obtenue ?
    \begin{choices}
    \wrongchoice{Tous les nœuds sont des feuilles d'une
racine vide
}
    \wrongchoice{Tous les nœuds sur une branche droite,
formant un peigne
}
    \wrongchoice{Racine $5$ ; tous les autres nœuds
répartis selon leur valeur
}
    \correctchoice{Racine $10$ ; sous-arbre gauche : $5$ avec
$3$ à gauche et $7$ à droite ; sous-arbre
droit : $15$ avec $12$ à gauche
}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q27}
    Quelle fonction Python vérifie correctement
qu'un arbre binaire respecte la propriété
d'arbre binaire de recherche (en utilisant
des bornes minimum et maximum) ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
def est_abr(n):
    if n is None:
        return True
    if n.gauche and n.gauche.valeur >= n.valeur:
        return False
    if n.droit and n.droit.valeur <= n.valeur:
        return False
    return est_abr(n.gauche) and est_abr(n.droit)
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def est_abr(n):
    return n is None
\end{lstlisting}
}
    \correctchoice{\begin{lstlisting}
def est_abr(n, mini=float('-inf'), maxi=float('inf')):
    if n is None:
        return True
    if not (mini < n.valeur < maxi):
        return False
    return est_abr(n.gauche, mini, n.valeur) and est_abr(n.droit, n.valeur, maxi)
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def est_abr(n):
    if n is None:
        return True
    return parcours_infixe(n) == sorted(parcours_infixe(n))
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{terminalearbresbinairesderecherche}{
  \begin{question}{q28}
    Comment trouver respectivement le \textbf{minimum}
et le \textbf{maximum} d'un arbre binaire de
recherche non vide ?
    \begin{choices}
    \wrongchoice{Le minimum est toujours la racine, le
maximum est toujours une feuille
}
    \wrongchoice{On parcourt tout l'arbre et on retient les
valeurs minimale et maximale au fur et à
mesure
}
    \correctchoice{Le minimum se trouve en descendant toujours
à gauche depuis la racine ; le maximum
en descendant toujours à droite. Les
deux opérations sont en $O(h)$ où $h$ est
la hauteur
}
    \wrongchoice{Le minimum et le maximum sont les deux
enfants de la racine
}
    \end{choices}
  \end{question}
}


\onecopy{1}{
  \shufflegroup{terminalearbresbinairesderecherche}
  \insertgroup{terminalearbresbinairesderecherche}
}

\end{document}
