Annales sur Structures de données, tas, files de priorité
Tous les sujets de concours scientifiques qui couvrent ce chapitre, corrigés par d'anciens taupins admis à Polytechnique, Centrale et Mines. Filtre par filière pour cibler ta préparation.
Variant de chapitre · catégorie Informatique
Cette page liste les annales qui mentionnent le sous-thème « Structures de données, tas, files de priorité » du chapitre Structures de données. Pour la vue large, va sur la page canonique du chapitre.
Structures de données
Au programme
Les structures de données en spé couvrent les listes (chaînées, doublement chaînées), piles, files, files à priorité, arbres (binaires, équilibrés AVL), tables de hachage, graphes. Programme MPI (algorithmique et structures de données est un bloc dédié) et MP option info ; PSI option info en aborde une partie.
Pourquoi c'est testé
12 sujets de concours dans notre base touchent aux structures de données, entre 2015 et 2025, chez Centrale-Supélec, Mines-Ponts et X-ENS. Pièges récurrents :
- Récursivité inadaptée ou complexité imposée non respectée (jury Mines-Ponts MP 2018 : « De nombreux codes très compliqués ont pu être lus. La récursivité n'est pas bien adaptée ici. Bien souvent, la complexité imposée n'est pas respectée. Les candidats ne semblent pas s'en apercevoir »)
- Complexité linéaire en la taille du texte au lieu du motif dans la recherche (jury Mines-Ponts MP 2018 : « L'usage de la fonction longueur (pour le texte) est inutile et à déconseiller : elle induit une complexité linéaire en la taille du texte alors que l'on peut obtenir une complexité linéaire en la taille du motif »)
- Fonction préfixe mal terminée : cas d'arrêt non gérés (jury Mines-Ponts MP 2018 : « La fonction préfixe pose parfois des difficultés cependant (mauvaise gestion des cas d'arrêt) »)
Comment réviser
Trois axes :
1. Complexités amorties par cœur pour chaque structure : pile/file O(1) amorti, hachage O(1) moyen, AVL O(log n). 2. Choix de la structure adaptée au problème : file pour BFS, pile pour DFS itératif, file à priorité pour Dijkstra et Prim. 3. Travailler les sujets : Info Mines-Ponts MP 2018 (recherche de motif, KMP), Info A X-ENS MP 2024 (AVL).
Sujets disponibles
Tous les sujets qui couvrent Structures de données, tas, files de priorité
Filière MP1 sujet
Voir aussi
Sujets similaires et chapitres liés
Sujets similaires3
Autres sous-thèmes de Structures de données rencontrés dans les annales.
Catégorie Informatique3
Autres chapitres canoniques de la catégorie Informatique qui apparaissent dans les annales.
Préparation Structures de données, tas, files de priorité
Bossez Structures de données, tas, files de priorité avec un ancien admis
Cours particuliers et stages intensifs encadrés par d'anciens taupins admis à Polytechnique, Centrale et Mines.