Fiche de révision :
Les Structures de Données

Q: Qu'est-ce qu'une liste chaînée ? Quels sont ses avantages et inconvénients par rapport à un tableau ?

Une liste chaînée est composée de nœuds : `class Noeud: def __init__(self, val, suivant=None): self.val = val; self.suivant = suivant`. Avantages : insertion/suppression en tête en O(1), taille dynamique. Inconvénients : accès au i-ème élément en O(n) (pas d'accès direct), mémoire supplémentaire pour les pointeurs. Un tableau offre l'accès direct O(1) mais insertion/suppression coûtent O(n). Choix selon l'usage : liste chaînée pour insertions fréquentes, tableau pour accès direct.

Q: Décrivez le fonctionnement d'une pile et donnez un exemple d'utilisation.

Une pile est LIFO. En Python : `pile = []; pile.append(x)` (push) et `pile.pop()` (pop). Exemple : évaluation d'une expression parenthésée — on empile les opérandes, on dépile quand on rencontre un opérateur. Autre exemple : la pile d'appels du système (call stack) lors d'une récursion empile les appels et les dépile au retour. Complexité push/pop : O(1). Débordement (stack overflow) si la pile est trop profonde.

Q: Qu'est-ce qu'une file ? En quoi diffère-t-elle d'une pile ?

Une file est FIFO : on ajoute en queue et on retire en tête. En Python : `from collections import deque; f = deque(); f.append(x)` (enqueue) et `f.popleft()` (dequeue). Différence avec pile : dans une pile on retire le dernier arrivé (LIFO) ; dans une file on retire le premier arrivé (FIFO). Exemple : file d'attente à la caisse. Application clé : algorithme BFS (parcours en largeur) pour trouver le plus court chemin dans un graphe non pondéré.

Q: Définissez un arbre binaire et décrivez ses différents types de parcours.

Un arbre binaire est recursif : chaque nœud est la racine d'un sous-arbre gauche et droit. Parcours préfixe : traiter racine, puis sous-arbre gauche, puis droite — utile pour copier l'arbre. Parcours infixe : gauche, racine, droite — donne les éléments dans l'ordre croissant pour un arbre binaire de recherche (ABR). Parcours postfixe : gauche, droite, racine — utile pour supprimer l'arbre. La hauteur d'un arbre équilibré à n nœuds est O(log n).

Q: Comparez les deux représentations d'un graphe et décrivez un algorithme de parcours.

Matrice d'adjacence : tableau n×n où M[i][j]=1 si arête de i vers j. Vérification d'arête en O(1) mais O(n²) mémoire. Liste d'adjacence : dictionnaire associant à chaque sommet la liste de ses voisins. O(n+m) mémoire, efficace pour les graphes creux. Parcours BFS : utilise une file, marque les sommets visités, explore niveau par niveau — donne le plus court chemin. DFS : utilise une pile (ou récursion), explore le plus loin possible avant de revenir en arrière.

Les structures de données sont fondamentales en NSI Terminale. Comprendre listes chaînées, piles, files, arbres et graphes est indispensable pour le bac.

Génère tes propres fiches de NSI en 10 secondes →

Essayer

NSI

Liste chaînée

Définition

Structure linéaire composée de nœuds. Chaque nœud contient une valeur et un pointeur vers le nœud suivant (None pour le dernier). Contrairement aux tableaux, les éléments ne sont pas contigus en mémoire. Insertion/suppression en tête en O(1), accès au i-ème élément en O(n).

Question probable

Qu'est-ce qu'une liste chaînée ? Quels sont ses avantages et inconvénients par rapport à un tableau ?

Mnémotechnique

Nœud = valeur + pointeur suivant. Chaîne = nœuds liés. O(1) en tête, O(n) pour accès. "Maillon d'une chaîne."

1 / 5

NSI

Pile (LIFO)

Définition

Structure de données LIFO (Last In, First Out) : le dernier élément ajouté est le premier retiré. Opérations : push (empiler), pop (dépiler), peek (sommet sans retirer), is_empty. Implémentable avec une liste Python. Utilisée pour les appels de fonctions, l'évaluation d'expressions, le parcours de graphe.

Question probable

Décrivez le fonctionnement d'une pile et donnez un exemple d'utilisation.

Mnémotechnique

LIFO = Last In, First Out. Assiettes empilées. Push = add, Pop = remove top. "Dernier arrivé, premier parti."

2 / 5

NSI

File (FIFO)

Définition

Structure de données FIFO (First In, First Out) : le premier élément ajouté est le premier retiré. Opérations : enqueue (enfiler), dequeue (défiler). Implémentable avec `collections.deque` en Python. Utilisée pour les files d'attente, le parcours en largeur (BFS) de graphes.

Question probable

Qu'est-ce qu'une file ? En quoi diffère-t-elle d'une pile ?

Mnémotechnique

FIFO = First In, First Out. File d'attente au cinéma. Enqueue = add end, Dequeue = remove front. "Premier arrivé, premier servi."

3 / 5

NSI

Arbre binaire

Définition

Structure hiérarchique composée de nœuds. Chaque nœud a au plus deux enfants (gauche et droit). La racine est le nœud sans parent. Les feuilles sont les nœuds sans enfants. La hauteur est la longueur du plus long chemin de la racine à une feuille. Parcours : préfixe (racine-gauche-droite), infixe (gauche-racine-droite), postfixe (gauche-droite-racine).

Question probable

Définissez un arbre binaire et décrivez ses différents types de parcours.

Mnémotechnique

Préfixe = Racine-Gauche-Droite. Infixe = Gauche-Racine-Droite (ordre trié pour ABR). Postfixe = Gauche-Droite-Racine. "PRé = Racine en PRemier."

4 / 5

NSI

Graphe

Définition

Structure composée de sommets (nœuds) reliés par des arêtes. Un graphe orienté (digraphe) a des arêtes avec un sens. Un graphe non orienté a des arêtes symétriques. Représentations : matrice d'adjacence

(O (n^{2})

mémoire) ou liste d'adjacence (O(n+m) mémoire). Algorithmes : BFS (parcours en largeur), DFS (parcours en profondeur).

Question probable

Comparez les deux représentations d'un graphe et décrivez un algorithme de parcours.

Mnémotechnique

Graphe = sommets + arêtes. Matrice =

O (n^{2})

, rapide à vérifier. Liste = O(n+m), économique. BFS = file + niveaux. DFS = pile + profondeur.

5 / 5

Génère tes fiches NSI
en 10 secondes

Colle ton cours de NSI. FicheIA génère tes fiches structurées instantanément.

Générer mes fiches →

3 générations gratuites · Sans inscription

Fiche de révision :Les Structures de Données

Génère tes fiches NSIen 10 secondes

À lire aussi — NSI

Fiche de révision :
Les Structures de Données

Génère tes fiches NSI
en 10 secondes