Flashcard: Introduction aux Structures et Algorithmes Essentiels — 20 carte

Interface — définition ?

Contrat décrivant fonctionnalités sans implémentation.

Encapsulation — rôle ?

Protège les données internes via des attributs privés.

Héritage — principe ?

Réutilisation et extension d’une classe par une autre.

Polymorphisme — avantage ?

Utilise une même interface avec des types différents.

Pile — structure ?

LIFO : dernier entré, premier sorti.

File — structure ?

FIFO : premier entré, premier sorti.

Dictionnaire — complexité ?

Recherche, insertion, suppression en 𝑂(1) en moyenne.

Racine — localisation ?

Nœud de départ sans parent.

Feuille — localisation ?

Nœud sans enfant.

Arbre binaire — caractéristique ?

Chaque nœud a au plus deux enfants.

ABR — règle ?

Gauche < nœud < droit.

Recherche ABR — mécanisme ?

Compare puis descend à gauche ou droite.

Taille arbre — définition ?

Nombre total de nœuds.

Hauteur arbre — définition ?

Nombre d’arêtes du racine au plus profond.

Parcours préfixe — ordre ?

Racine, gauche, droit.

Parcours infixe — ordre ?

Gauche, racine, droit.

Parcours suffixe — ordre ?

Gauche, droit, racine.

Parcours largeur — méthode ?

Niveau par niveau, en utilisant une file.

Arbres équilibrés — exemple ?

Arbres AVL, maintiennent hauteur logarithmique.

Graphe — définition ?

Ensemble de sommets reliés par des arêtes.