Flashcards: Structures de données et algorithmes essentiels — 24 cards

Structure de données — définition ?

Organisation logique facilitant traitement, accès et mémoire.

Objectifs des structures — but ?

Optimiser accès, mémoire et temps de traitement.

Structures linéaires — exemples ?

Tableaux, listes chaînées, piles, files.

Structures non linéaires — exemples ?

Arbres, graphes.

Tableau à une dimension — accès ?

Par indice, en temps constant.

Tableau à deux dimensions — organisation ?

Matrice avec lignes et colonnes.

Tableau dynamique — caractéristique ?

Taille modifiable lors de l'exécution.

Liste chaînée simple — composition ?

Nœuds reliés par pointeurs, un seul lien.

Liste double — particularité ?

Pointeurs vers avant et arrière.

Liste circulaire — boucle ?

Dernier nœud pointe vers le premier.

Arbre binaire — relation ?

Chaque nœud a au plus deux fils.

Opération création arbre — primitive ?

Initialiser ou construire à partir de nœuds.

Opération insertion arbre — rôle ?

Ajouter un nœud selon la propriété.

Opération suppression arbre — but ?

Retirer un nœud ou sous-arbre.

Parcours arbre — types ?

Préordre, inordre, postordre.

Complexité algorithmique — mesure ?

Temps et espace selon taille des données.

Complexité en O(1) — exemple ?

Accès direct dans un tableau.

Complexité en O(n) — exemple ?

Recherche linéaire dans un tableau non trié.

Tableau à une dimension — déclaration ?

Nom, taille fixe, indexation.

Tableau à deux dimensions — accès ?

Par deux indices, ligne et colonne.

Tableau dynamique — avantage ?

Taille adaptable, gestion flexible mémoire.

Opérations fondamentales — liste ?

Création, insertion, suppression, recherche, parcours, mise à jour.

Primitives sur arbres — rôle ?

Créer, insérer, supprimer, parcourir.

Complexité recherche dans arbre équilibré ?

O(log n), grâce à l’équilibre.