\documentclass[a4paper,11pt]{article}

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

\title{Listes, piles, files}
\date{Numérique et sciences informatiques}

\begin{document}

\noindent\textbf{Listes, piles, files} \hfill \textit{Numérique et sciences informatiques}\\[0.4em]
Nom~: \dotfill\ Prénom~: \dotfill

\bigskip

\element{terminalelistespilesfiles}{
  \begin{question}{q01}
    Quel est le principe d'une \textbf{pile} (\textit{stack}) ?
    \begin{choices}
    \wrongchoice{Premier entré, premier sorti (FIFO)}
    \wrongchoice{Accès aléatoire à n'importe quel élément}
    \wrongchoice{Tri automatique des éléments}
    \correctchoice{Dernier entré, premier sorti (LIFO)}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q02}
    Quel est le principe d'une \textbf{file} (\textit{queue}) ?
    \begin{choices}
    \wrongchoice{Élimination automatique des doublons}
    \correctchoice{Premier entré, premier sorti (FIFO)}
    \wrongchoice{Dernier entré, premier sorti (LIFO)}
    \wrongchoice{Accès direct au milieu de la structure}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q03}
    Quelles sont les \textbf{deux opérations principales} d'une
pile ?
    \begin{choices}
    \wrongchoice{\texttt{get} et \texttt{set}}
    \wrongchoice{\texttt{add} et \texttt{remove}}
    \correctchoice{\texttt{push} (empiler) et \texttt{pop} (dépiler)}
    \wrongchoice{\texttt{enqueue} et \texttt{dequeue}}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q04}
    Quelles sont les opérations principales d'une \textbf{file} ?
    \begin{choices}
    \wrongchoice{\texttt{push} et \texttt{pop}}
    \wrongchoice{\texttt{min} et \texttt{max}}
    \correctchoice{\texttt{enqueue} (enfiler) et \texttt{dequeue} (défiler)}
    \wrongchoice{\texttt{sort} et \texttt{reverse}}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q05}
    Pour vérifier qu'une expression contient des
\textbf{parenthèses bien équilibrées} (par exemple
\texttt{((a + b) * c)}), quelle structure est la plus adaptée ?
    \begin{choices}
    \correctchoice{Une pile (LIFO)}
    \wrongchoice{Un tableau trié}
    \wrongchoice{Une file (FIFO)}
    \wrongchoice{Un dictionnaire}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q06}
    Pour gérer une \textbf{file d'impression} (les documents
arrivés en premier sont imprimés en premier), quelle
structure utiliser ?
    \begin{choices}
    \wrongchoice{Une pile}
    \wrongchoice{Une liste triée par taille}
    \wrongchoice{Un dictionnaire}
    \correctchoice{Une file}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q07}
    En Python, une manière simple d'implémenter une pile
utilise :
    \begin{choices}
    \correctchoice{Une liste avec \texttt{append()} pour empiler et \texttt{pop()} pour dépiler}
    \wrongchoice{Un dictionnaire}
    \wrongchoice{Un simple entier}
    \wrongchoice{Une chaîne de caractères}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q08}
    Pour implémenter une file efficace en Python, quelle
structure de la bibliothèque standard utilise-t-on ?
    \begin{choices}
    \correctchoice{\texttt{collections.deque} (file double-ended) avec \texttt{append()} et \texttt{popleft()}, toutes deux en $O(1)$}
    \wrongchoice{\texttt{tuple}}
    \wrongchoice{\texttt{list}, en utilisant \texttt{append()} et \texttt{pop(0)}}
    \wrongchoice{\texttt{set} (ensemble)}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q09}
    Quel rôle joue la \textbf{pile d'appels} (\textit{call stack}) lors
de l'exécution d'un programme ?
    \begin{choices}
    \wrongchoice{Stocker les fichiers ouverts}
    \wrongchoice{Stocker les données d'une base de données}
    \wrongchoice{Compter les variables globales}
    \correctchoice{Empiler le contexte de chaque appel de fonction (paramètres, variables locales, adresse de retour) et le dépiler à la fin de la fonction}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q10}
    Qu'est-ce qu'une \textbf{liste chaînée} ?
    \begin{choices}
    \wrongchoice{Une liste reliée à une base de données}
    \wrongchoice{Une liste qui ne peut pas être modifiée}
    \wrongchoice{Une liste chiffrée}
    \correctchoice{Une liste où chaque élément contient sa valeur et une référence vers l'élément suivant}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q11}
    Quelle est la complexité des opérations \texttt{push} et \texttt{pop}
sur une pile, pour une bonne implémentation ?
    \begin{choices}
    \wrongchoice{$O(n)$ pour les deux}
    \wrongchoice{$O(\log n)$ pour les deux}
    \correctchoice{$O(1)$ pour les deux}
    \wrongchoice{$O(n^2)$ pour les deux}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q12}
    Quelle est la complexité d'accéder au $k$-ième élément
d'une liste chaînée simplement chaînée ?
    \begin{choices}
    \correctchoice{$O(k)$ (linéaire)}
    \wrongchoice{$O(\log k)$}
    \wrongchoice{$O(1)$}
    \wrongchoice{$O(k^2)$}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q13}
    L'évaluation d'une expression en \textbf{notation postfixée}
(par exemple \texttt{2 3 + 4 *}) utilise :
    \begin{choices}
    \wrongchoice{Une file}
    \wrongchoice{Un dictionnaire}
    \wrongchoice{Un arbre binaire}
    \correctchoice{Une pile : on empile les nombres et, à chaque opérateur, on dépile les deux derniers, on calcule, et on rempile le résultat}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q14}
    Pour un parcours en \textbf{largeur} d'un graphe ou
d'un arbre, quelle structure utilise-t-on ?
    \begin{choices}
    \correctchoice{Une file}
    \wrongchoice{Un dictionnaire}
    \wrongchoice{Une liste triée}
    \wrongchoice{Une pile}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q15}
    « Pile » et « file » sont des \textbf{interfaces} abstraites.
Cela signifie que :
    \begin{choices}
    \wrongchoice{Elles sont écrites en assembleur}
    \correctchoice{Elles définissent un comportement (LIFO ou FIFO) sans imposer la structure interne (tableau, liste chaînée, etc.)}
    \wrongchoice{Elles sont obsolètes}
    \wrongchoice{Elles ne peuvent pas être implémentées en Python}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q16}
    Que faut-il faire avant de tenter un \texttt{pop()} sur une
pile ?
    \begin{choices}
    \wrongchoice{Recalculer la longueur}
    \correctchoice{Vérifier qu'elle n'est pas vide (par exemple avec \texttt{is\_empty()})}
    \wrongchoice{Toujours appeler \texttt{peek()} d'abord}
    \wrongchoice{Multiplier la taille par deux}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q17}
    Quel est l'\textbf{avantage principal} d'une liste chaînée
sur un tableau dynamique ?
    \begin{choices}
    \wrongchoice{L'accès indexé est plus rapide}
    \correctchoice{L'insertion et la suppression en tête se font en temps constant, sans avoir à décaler d'autres éléments}
    \wrongchoice{Elle utilise moins de mémoire}
    \wrongchoice{Elle est intrinsèquement triée}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q18}
    En Python, dans une classe \texttt{Pile} minimale, quelles
méthodes définit-on typiquement ?
    \begin{choices}
    \wrongchoice{\texttt{get}, \texttt{set} indexés}
    \wrongchoice{\texttt{add}, \texttt{remove}, \texttt{find}, \texttt{sort}}
    \wrongchoice{Une seule méthode \texttt{do()}}
    \correctchoice{\texttt{empiler(x)}, \texttt{depiler()}, \texttt{sommet()} (ou \texttt{peek}), \texttt{est\_vide()}}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q19}
    L'expression \texttt{(())} est-elle bien parenthésée ? Et
\texttt{(()} ?
    \begin{choices}
    \wrongchoice{Toutes deux sont bien parenthésées}
    \wrongchoice{La parité du nombre de caractères suffit à juger}
    \correctchoice{\texttt{(())} est correcte ; \texttt{(()} est incorrecte (la première parenthèse n'est jamais fermée)}
    \wrongchoice{Toutes deux sont incorrectes}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q20}
    Que renvoie le code Python suivant ?

\begin{lstlisting}
pile = []
for x in [1, 2, 3, 4]:
    pile.append(x)
print(pile.pop())
\end{lstlisting}
    \begin{choices}
    \wrongchoice{$0$}
    \wrongchoice{La liste entière \texttt{[1, 2, 3]}}
    \wrongchoice{$1$}
    \correctchoice{$4$}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q21}
    Pourquoi \texttt{list.pop(0)} est-il \textbf{inefficace} pour
implémenter une file en Python ?
    \begin{choices}
    \wrongchoice{Parce que les listes Python ne sont pas mutables}
    \correctchoice{Parce qu'il faut décaler tous les autres éléments d'un cran vers la gauche, ce qui est en $O(n)$}
    \wrongchoice{Parce que ça lève toujours une erreur}
    \wrongchoice{Parce que \texttt{pop} ne peut pas prendre d'argument}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q22}
    Un \textbf{tampon circulaire} (\textit{ring buffer}) est :
    \begin{choices}
    \wrongchoice{Un dictionnaire trié}
    \wrongchoice{Une liste chaînée fermée}
    \correctchoice{Une file implémentée sur un tableau de taille fixe, où l'on revient au début quand on dépasse la fin}
    \wrongchoice{Une pile de taille variable}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q23}
    Toute fonction récursive peut être convertie en une
version itérative utilisant explicitement :
    \begin{choices}
    \wrongchoice{Une file}
    \wrongchoice{Un dictionnaire}
    \correctchoice{Une pile, qui simule la pile d'appels gérée implicitement par le langage}
    \wrongchoice{Un arbre}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q24}
    Une \textbf{file de priorité} (priority queue) diffère d'une
file FIFO classique en ce que :
    \begin{choices}
    \wrongchoice{Elle ne stocke que les nombres}
    \wrongchoice{Aucune différence}
    \wrongchoice{Elle est plus rapide que la file ordinaire}
    \correctchoice{L'élément retiré est celui qui a la priorité la plus élevée, pas forcément le plus ancien}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q25}
    On souhaite gérer l'historique des actions d'un éditeur
de texte, avec une fonction « annuler » (Ctrl+Z). Quelle
structure est la plus adaptée ?
    \begin{choices}
    \wrongchoice{Une liste triée}
    \wrongchoice{Un dictionnaire}
    \correctchoice{Une pile}
    \wrongchoice{Une file}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q26}
    On souhaite implémenter une liste simplement chaînée
en Python. Quelle classe représente un \textbf{maillon}
correctement ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
class Maillon:
    def __init__(self, valeur):
        self.valeur = valeur
\end{lstlisting}
}
    \correctchoice{\begin{lstlisting}
class Maillon:
    def __init__(self, valeur, suivant=None):
        self.valeur = valeur
        self.suivant = suivant
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def maillon(valeur):
    return [valeur]
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
class Maillon:
    def __init__(self, valeur, precedent, suivant):
        self.valeur = valeur
        self.precedent = precedent
        self.suivant = suivant
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q27}
    Pour effectuer un parcours en profondeur d'un arbre
ou d'un graphe \textbf{sans utiliser la récursivité}, quel
algorithme et quelle structure utilise-t-on ?
    \begin{choices}
    \correctchoice{On utilise une pile : on empile le sommet de
départ, puis on répète : dépiler un sommet, le
marquer comme visité, et empiler ses voisins
non visités. La pile reproduit l'ordre LIFO de
la récursion
}
    \wrongchoice{On utilise un dictionnaire pour stocker les
sommets visités
}
    \wrongchoice{On utilise une file : on enfile le sommet
de départ et on défile à chaque étape
}
    \wrongchoice{On trie d'abord les sommets puis on les parcourt
dans l'ordre
}
    \end{choices}
  \end{question}
}

\element{terminalelistespilesfiles}{
  \begin{question}{q28}
    On veut implémenter une fonctionnalité « annuler »
(Ctrl+Z) et « refaire » (Ctrl+Y) dans un éditeur.
Quelle structure utiliser ?
    \begin{choices}
    \wrongchoice{Un dictionnaire indexé par l'instant de l'action
}
    \wrongchoice{Une file pour l'historique, une pile pour le
refaire
}
    \correctchoice{Deux piles : une pile « historique » qui contient
les actions déjà effectuées, et une pile
« refaire » qui contient les actions annulées.
Annuler = dépiler de l'historique, empiler dans
refaire ; refaire = dépiler de refaire,
empiler dans l'historique. Toute nouvelle
action vide la pile « refaire »
}
    \wrongchoice{Une seule pile suffit
}
    \end{choices}
  \end{question}
}


\onecopy{1}{
  \shufflegroup{terminalelistespilesfiles}
  \insertgroup{terminalelistespilesfiles}
}

\end{document}
