\documentclass[10pt,aspectratio=169]{beamer}

% --- Thème ---
\usetheme[language=french]{Celestia}

% Avec [allowframebreaks] sur les frames de questions, Beamer ajoute
% par défaut « (1) », « (2) », « (3) »... sur chaque sous-slide. On
% supprime entièrement cette annotation : un template vide pour
% « frametitle continuation ». L'enseignant identifie visuellement la
% continuation par le contenu de la slide. (Les variantes [from second]
% et [roman] interagissent mal avec un titre contenant \textemdash{}
% sous Celestia : elles déclenchent une erreur « Missing $ inserted ».)
\setbeamertemplate{frametitle continuation}{}

\subject{Numérique et sciences informatiques}
\title{Listes, piles, files}
\subtitle{QCM}
\author{Terminale}
\date{\today}

\begin{document}

\begin{frame}
    \titlepage
\end{frame}

% Q1 - Réponse en D
\begin{frame}[fragile]{Question 1 \textemdash{} Définition d'une pile}
    Quel est le principe d'une \textbf{pile} (\textit{stack}) ?\medskip
    \begin{itemize}
        \item[A.] Premier entré, premier sorti (FIFO)
        \item[B.] Accès aléatoire à n'importe quel élément
        \item[C.] Tri automatique des éléments
        \item[\alert<2>{D.}] \alert<2>{Dernier entré, premier sorti (LIFO)}
    \end{itemize}
\end{frame}

% Q2 - Réponse en B
\begin{frame}[fragile]{Question 2 \textemdash{} Définition d'une file}
    Quel est le principe d'une \textbf{file} (\textit{queue}) ?\medskip
    \begin{itemize}
        \item[A.] Élimination automatique des doublons
        \item[\alert<2>{B.}] \alert<2>{Premier entré, premier sorti (FIFO)}
        \item[C.] Dernier entré, premier sorti (LIFO)
        \item[D.] Accès direct au milieu de la structure
    \end{itemize}
\end{frame}

% Q3 - Réponse en C
\begin{frame}[fragile]{Question 3 \textemdash{} Opérations sur une pile}
    Quelles sont les \textbf{deux opérations principales} d'une
pile ?\medskip
    \begin{itemize}
        \item[A.] \texttt{get} et \texttt{set}
        \item[B.] \texttt{add} et \texttt{remove}
        \item[\alert<2>{C.}] \alert<2>{\texttt{push} (empiler) et \texttt{pop} (dépiler)}
        \item[D.] \texttt{enqueue} et \texttt{dequeue}
    \end{itemize}
\end{frame}

% Q4 - Réponse en C
\begin{frame}[fragile]{Question 4 \textemdash{} Opérations sur une file}
    Quelles sont les opérations principales d'une \textbf{file} ?\medskip
    \begin{itemize}
        \item[A.] \texttt{push} et \texttt{pop}
        \item[B.] \texttt{min} et \texttt{max}
        \item[\alert<2>{C.}] \alert<2>{\texttt{enqueue} (enfiler) et \texttt{dequeue} (défiler)}
        \item[D.] \texttt{sort} et \texttt{reverse}
    \end{itemize}
\end{frame}

% Q5 - Réponse en A
\begin{frame}[fragile]{Question 5 \textemdash{} Application classique des piles}
    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 ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Une pile (LIFO)}
        \item[B.] Un tableau trié
        \item[C.] Une file (FIFO)
        \item[D.] Un dictionnaire
    \end{itemize}
\end{frame}

% Q6 - Réponse en D
\begin{frame}[fragile]{Question 6 \textemdash{} Application classique des files}
    Pour gérer une \textbf{file d'impression} (les documents
arrivés en premier sont imprimés en premier), quelle
structure utiliser ?\medskip
    \begin{itemize}
        \item[A.] Une pile
        \item[B.] Une liste triée par taille
        \item[C.] Un dictionnaire
        \item[\alert<2>{D.}] \alert<2>{Une file}
    \end{itemize}
\end{frame}

% Q7 - Réponse en A
\begin{frame}[fragile]{Question 7 \textemdash{} Pile en Python}
    En Python, une manière simple d'implémenter une pile
utilise :\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Une liste avec \texttt{append()} pour empiler et \texttt{pop()} pour dépiler}
        \item[B.] Un dictionnaire
        \item[C.] Un simple entier
        \item[D.] Une chaîne de caractères
    \end{itemize}
\end{frame}

% Q8 - Réponse en A
\begin{frame}[fragile]{Question 8 \textemdash{} File en Python efficace}
    Pour implémenter une file efficace en Python, quelle
structure de la bibliothèque standard utilise-t-on ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{\texttt{collections.deque} (file double-ended) avec \texttt{append()} et \texttt{popleft()}, toutes deux en $O(1)$}
        \item[B.] \texttt{tuple}
        \item[C.] \texttt{list}, en utilisant \texttt{append()} et \texttt{pop(0)}
        \item[D.] \texttt{set} (ensemble)
    \end{itemize}
\end{frame}

% Q9 - Réponse en D
\begin{frame}[fragile]{Question 9 \textemdash{} Pile d'appels}
    Quel rôle joue la \textbf{pile d'appels} (\textit{call stack}) lors
de l'exécution d'un programme ?\medskip
    \begin{itemize}
        \item[A.] Stocker les fichiers ouverts
        \item[B.] Stocker les données d'une base de données
        \item[C.] Compter les variables globales
        \item[\alert<2>{D.}] \alert<2>{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{itemize}
\end{frame}

% Q10 - Réponse en D
\begin{frame}[fragile]{Question 10 \textemdash{} Liste chaînée}
    Qu'est-ce qu'une \textbf{liste chaînée} ?\medskip
    \begin{itemize}
        \item[A.] Une liste reliée à une base de données
        \item[B.] Une liste qui ne peut pas être modifiée
        \item[C.] Une liste chiffrée
        \item[\alert<2>{D.}] \alert<2>{Une liste où chaque élément contient sa valeur et une référence vers l'élément suivant}
    \end{itemize}
\end{frame}

% Q11 - Réponse en C
\begin{frame}[fragile]{Question 11 \textemdash{} Complexité des opérations sur une pile}
    Quelle est la complexité des opérations \texttt{push} et \texttt{pop}
sur une pile, pour une bonne implémentation ?\medskip
    \begin{itemize}
        \item[A.] $O(n)$ pour les deux
        \item[B.] $O(\log n)$ pour les deux
        \item[\alert<2>{C.}] \alert<2>{$O(1)$ pour les deux}
        \item[D.] $O(n^2)$ pour les deux
    \end{itemize}
\end{frame}

% Q12 - Réponse en A
\begin{frame}[fragile]{Question 12 \textemdash{} Accès indexé dans une liste chaînée}
    Quelle est la complexité d'accéder au $k$-ième élément
d'une liste chaînée simplement chaînée ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{$O(k)$ (linéaire)}
        \item[B.] $O(\log k)$
        \item[C.] $O(1)$
        \item[D.] $O(k^2)$
    \end{itemize}
\end{frame}

% Q13 - Réponse en D
\begin{frame}[fragile]{Question 13 \textemdash{} Évaluation d'une expression postfixée}
    L'évaluation d'une expression en \textbf{notation postfixée}
(par exemple \texttt{2 3 + 4 *}) utilise :\medskip
    \begin{itemize}
        \item[A.] Une file
        \item[B.] Un dictionnaire
        \item[C.] Un arbre binaire
        \item[\alert<2>{D.}] \alert<2>{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{itemize}
\end{frame}

% Q14 - Réponse en A
\begin{frame}[fragile]{Question 14 \textemdash{} Parcours en largeur et parcours en profondeur}
    Pour un parcours en \textbf{largeur} d'un graphe ou
d'un arbre, quelle structure utilise-t-on ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Une file}
        \item[B.] Un dictionnaire
        \item[C.] Une liste triée
        \item[D.] Une pile
    \end{itemize}
\end{frame}

% Q15 - Réponse en B
\begin{frame}[fragile]{Question 15 \textemdash{} Distinction entre interface et implémentation}
    « Pile » et « file » sont des \textbf{interfaces} abstraites.
Cela signifie que :\medskip
    \begin{itemize}
        \item[A.] Elles sont écrites en assembleur
        \item[\alert<2>{B.}] \alert<2>{Elles définissent un comportement (LIFO ou FIFO) sans imposer la structure interne (tableau, liste chaînée, etc.)}
        \item[C.] Elles sont obsolètes
        \item[D.] Elles ne peuvent pas être implémentées en Python
    \end{itemize}
\end{frame}

% Q16 - Réponse en B
\begin{frame}[fragile]{Question 16 \textemdash{} Pile vide}
    Que faut-il faire avant de tenter un \texttt{pop()} sur une
pile ?\medskip
    \begin{itemize}
        \item[A.] Recalculer la longueur
        \item[\alert<2>{B.}] \alert<2>{Vérifier qu'elle n'est pas vide (par exemple avec \texttt{is\_empty()})}
        \item[C.] Toujours appeler \texttt{peek()} d'abord
        \item[D.] Multiplier la taille par deux
    \end{itemize}
\end{frame}

% Q17 - Réponse en B
\begin{frame}[fragile]{Question 17 \textemdash{} Liste chaînée vs tableau}
    Quel est l'\textbf{avantage principal} d'une liste chaînée
sur un tableau dynamique ?\medskip
    \begin{itemize}
        \item[A.] L'accès indexé est plus rapide
        \item[\alert<2>{B.}] \alert<2>{L'insertion et la suppression en tête se font en temps constant, sans avoir à décaler d'autres éléments}
        \item[C.] Elle utilise moins de mémoire
        \item[D.] Elle est intrinsèquement triée
    \end{itemize}
\end{frame}

% Q18 - Réponse en D
\begin{frame}[fragile]{Question 18 \textemdash{} Implémentation orientée objet d'une pile}
    En Python, dans une classe \texttt{Pile} minimale, quelles
méthodes définit-on typiquement ?\medskip
    \begin{itemize}
        \item[A.] \texttt{get}, \texttt{set} indexés
        \item[B.] \texttt{add}, \texttt{remove}, \texttt{find}, \texttt{sort}
        \item[C.] Une seule méthode \texttt{do()}
        \item[\alert<2>{D.}] \alert<2>{\texttt{empiler(x)}, \texttt{depiler()}, \texttt{sommet()} (ou \texttt{peek}), \texttt{est\_vide()}}
    \end{itemize}
\end{frame}

% Q19 - Réponse en C
\begin{frame}[fragile]{Question 19 \textemdash{} Détection de parenthèses déséquilibrées}
    L'expression \texttt{(())} est-elle bien parenthésée ? Et
\texttt{(()} ?\medskip
    \begin{itemize}
        \item[A.] Toutes deux sont bien parenthésées
        \item[B.] La parité du nombre de caractères suffit à juger
        \item[\alert<2>{C.}] \alert<2>{\texttt{(())} est correcte ; \texttt{(()} est incorrecte (la première parenthèse n'est jamais fermée)}
        \item[D.] Toutes deux sont incorrectes
    \end{itemize}
\end{frame}

% Q20 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 20 \textemdash{} Analyse d'un code de pile}
    Que renvoie le code Python suivant ?

\begin{lstlisting}
pile = []
for x in [1, 2, 3, 4]:
    pile.append(x)
print(pile.pop())
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.] $0$
        \item[B.] La liste entière \texttt{[1, 2, 3]}
        \item[C.] $1$
        \item[D.] $4$
    \end{itemize}
\end{frame}

% Q20 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 20 \textemdash{} Analyse d'un code de pile}
    Que renvoie le code Python suivant ?

\begin{lstlisting}
pile = []
for x in [1, 2, 3, 4]:
    pile.append(x)
print(pile.pop())
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.] $0$
        \item[B.] La liste entière \texttt{[1, 2, 3]}
        \item[C.] $1$
        \item[\alert{D.}] \alert{$4$}
    \end{itemize}
\end{frame}

% Q21 - Réponse en B
\begin{frame}[fragile]{Question 21 \textemdash{} Pourquoi pas list.pop(0) pour une file}
    Pourquoi \texttt{list.pop(0)} est-il \textbf{inefficace} pour
implémenter une file en Python ?\medskip
    \begin{itemize}
        \item[A.] Parce que les listes Python ne sont pas mutables
        \item[\alert<2>{B.}] \alert<2>{Parce qu'il faut décaler tous les autres éléments d'un cran vers la gauche, ce qui est en $O(n)$}
        \item[C.] Parce que ça lève toujours une erreur
        \item[D.] Parce que \texttt{pop} ne peut pas prendre d'argument
    \end{itemize}
\end{frame}

% Q22 - Réponse en C
\begin{frame}[fragile]{Question 22 \textemdash{} Tampon circulaire}
    Un \textbf{tampon circulaire} (\textit{ring buffer}) est :\medskip
    \begin{itemize}
        \item[A.] Un dictionnaire trié
        \item[B.] Une liste chaînée fermée
        \item[\alert<2>{C.}] \alert<2>{Une file implémentée sur un tableau de taille fixe, où l'on revient au début quand on dépasse la fin}
        \item[D.] Une pile de taille variable
    \end{itemize}
\end{frame}

% Q23 - Réponse en C
\begin{frame}[fragile]{Question 23 \textemdash{} Récursivité et pile}
    Toute fonction récursive peut être convertie en une
version itérative utilisant explicitement :\medskip
    \begin{itemize}
        \item[A.] Une file
        \item[B.] Un dictionnaire
        \item[\alert<2>{C.}] \alert<2>{Une pile, qui simule la pile d'appels gérée implicitement par le langage}
        \item[D.] Un arbre
    \end{itemize}
\end{frame}

% Q24 - Réponse en D
\begin{frame}[fragile]{Question 24 \textemdash{} File de priorité}
    Une \textbf{file de priorité} (priority queue) diffère d'une
file FIFO classique en ce que :\medskip
    \begin{itemize}
        \item[A.] Elle ne stocke que les nombres
        \item[B.] Aucune différence
        \item[C.] Elle est plus rapide que la file ordinaire
        \item[\alert<2>{D.}] \alert<2>{L'élément retiré est celui qui a la priorité la plus élevée, pas forcément le plus ancien}
    \end{itemize}
\end{frame}

% Q25 - Réponse en C
\begin{frame}[fragile]{Question 25 \textemdash{} Choisir la bonne structure}
    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 ?\medskip
    \begin{itemize}
        \item[A.] Une liste triée
        \item[B.] Un dictionnaire
        \item[\alert<2>{C.}] \alert<2>{Une pile}
        \item[D.] Une file
    \end{itemize}
\end{frame}

% Q26 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 26 \textemdash{} Maillon d'une liste chaînée}
    On souhaite implémenter une liste simplement chaînée
en Python. Quelle classe représente un \textbf{maillon}
correctement ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
class Maillon:
    def __init__(self, valeur):
        self.valeur = valeur
\end{lstlisting}

        \item[B.]~\\
\begin{lstlisting}
class Maillon:
    def __init__(self, valeur, suivant=None):
        self.valeur = valeur
        self.suivant = suivant
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
def maillon(valeur):
    return [valeur]
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
class Maillon:
    def __init__(self, valeur, precedent, suivant):
        self.valeur = valeur
        self.precedent = precedent
        self.suivant = suivant
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q26 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 26 \textemdash{} Maillon d'une liste chaînée}
    On souhaite implémenter une liste simplement chaînée
en Python. Quelle classe représente un \textbf{maillon}
correctement ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
class Maillon:
    def __init__(self, valeur):
        self.valeur = valeur
\end{lstlisting}

        \item[\alert{B.}]~\\
\begin{lstlisting}
class Maillon:
    def __init__(self, valeur, suivant=None):
        self.valeur = valeur
        self.suivant = suivant
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
def maillon(valeur):
    return [valeur]
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
class Maillon:
    def __init__(self, valeur, precedent, suivant):
        self.valeur = valeur
        self.precedent = precedent
        self.suivant = suivant
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q27 - Réponse en A
\begin{frame}[fragile]{Question 27 \textemdash{} Parcours en profondeur avec pile explicite}
    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 ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{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
}
        \item[B.] On utilise un dictionnaire pour stocker les
sommets visités

        \item[C.] On utilise une file : on enfile le sommet
de départ et on défile à chaque étape

        \item[D.] On trie d'abord les sommets puis on les parcourt
dans l'ordre

    \end{itemize}
\end{frame}

% Q28 - Réponse en C
\begin{frame}[fragile]{Question 28 \textemdash{} Annuler et refaire avec deux piles}
    On veut implémenter une fonctionnalité « annuler »
(Ctrl+Z) et « refaire » (Ctrl+Y) dans un éditeur.
Quelle structure utiliser ?\medskip
    \begin{itemize}
        \item[A.] Un dictionnaire indexé par l'instant de l'action

        \item[B.] Une file pour l'historique, une pile pour le
refaire

        \item[\alert<2>{C.}] \alert<2>{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 »
}
        \item[D.] Une seule pile suffit

    \end{itemize}
\end{frame}

\begin{frame}[standout]{}
    Fin de l'évaluation
\end{frame}

\end{document}
