Durée conseillée : 90 minutes. Réussite à 60 %. Les ressources du cours sont autorisées ; l'IA peut aider à comprendre, mais tu dois savoir expliquer chaque réponse.
Partie 1 — Questions (40 points)
1. Un ADT décrit une structure par :
- A. ses opérations
- B. son code interne
- C. sa couleur
2. Insérer au début d'un grand tableau est :
- A. gratuit
- B. impossible
- C. coûteux (décalage)
3. Une file suit :
- A. dernier arrivé, premier sorti
- B. premier arrivé, premier sorti
- C. aucun ordre
4. Une collision de hachage est :
- A. deux clés dans la même case
- B. une erreur de syntaxe
- C. une panne
5. Dans un BST, le parcours en ordre donne :
- A. les valeurs inversées
- B. les feuilles
- C. les valeurs triées
6. Dans un tas-min, la racine est :
- A. le plus grand
- B. le plus petit élément
- C. au hasard
7. BFS utilise :
- A. une file
- B. un tri
- C. un arbre de recherche
8. Pour choisir une structure, on commence par :
- A. choisir la plus récente
- B. utiliser une liste
- C. lister les opérations
✅ Réponses de la partie 1
- A
- C
- B
- A
- C
- B
- A
- C
Partie 2 — Problème pratique (40 points)
Écris une classe JournalRecent qui garde les n derniers événements (chaque événement est un texte) et permet :
ajouter(texte);contient(texte): le texte est-il dans lesnderniers ? (doit être rapide) ;liste(): les événements du plus ancien au plus récent.
Contraintes : mémoire bornée à n événements ; plusieurs occurrences du même texte possibles. Écris le contrat, le code, 6 tests dont un test aléatoire comparé à une version naïve.
Partie 3 — Justification (20 points)
Explique en 10 lignes maximum quelles structures tu as combinées, pourquoi, quel invariant relie leurs contenus, et le coût de chaque opération.
Barème
| Partie | Points |
|---|---|
| 1 — Questions | 40 |
| 2 — Problème pratique | 40 |
| 3 — Justification | 20 |
HEF-020 — Structures de données

