# Structures de Données, Analyse de Complexité (Big-O) et Algorithmes Fondamentaux

> Révision de niveau licence nécessitant des bases en programmation : 32 cartes sur tableaux, listes, hachage, arbres, tas, tries, Union–Find, filtres de Bloom et complexité.

- **Canonical URL:** https://flashcards.world/flashcards/sets/834a3679-6076-46e9-a401-3213176fc66d/
- **Markdown URL:** https://flashcards.world/flashcards/sets/834a3679-6076-46e9-a401-3213176fc66d.md
- **Category:** Computer Science
- **Level:** basic
- **Languages:** fr → fr
- **Total Cards:** 32

## Flashcards (32 Cards)

| # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-Choice Options |
| :--- | :--- | :--- | :--- | :--- |
| 1 | Comment recherche, insertion et suppression dans un BST dépendent-elles de sa hauteur h ? | Elles coûtent O(h). Un arbre équilibré a h = O(log n), une chaîne h = O(n). Un coût attendu O(log n) nécessite des hypothèses, comme un ordre d'insertion aléatoire. |  |  |
| 2 | Quels sont les ordres des parcours préfixe, infixe et postfixe d'un arbre binaire ? | Préfixe : nœud → gauche → droite. Infixe : gauche → nœud → droite. Postfixe : gauche → droite → nœud. |  |  |
| 3 | Comment une file dans un tableau circulaire évite-t-elle les décalages après un retrait ? | Les indices avant et arrière bouclent modulo la capacité. Le retrait avance l'indice avant : les cases libérées sont réutilisables sans déplacer les autres éléments. |  |  |
| 4 | Quelle est la condition d'équilibre AVL ? | À chaque nœud, hauteur(gauche) − hauteur(droite) ∈ {−1, 0, 1}. L'arbre respecte aussi l'invariant d'ordre d'un BST. |  |  |
| 5 | Quel est le coût amorti de union/find avec compression de chemins et union par rang ? | O(α(n)) par opération, où α est l'inverse d'Ackermann et n le nombre d'éléments. L'initialisation coûte O(n) ; la borne concerne une séquence, pas un coût constant dans le pire cas pour chaque appel. |  |  |
| 6 | Pourquoi l'accès par indice dans un tableau de taille fixe est-il en O(1) ? | Les cases de même taille sont contiguës : adresse(i) = base + i·taille_case. On suppose que le calcul d'adresse prend un temps constant. |  |  |
| 7 | Compare l'insertion en tête et l'accès par indice dans une liste simplement chaînée et un tableau dynamique. | Liste : insertion en tête O(1), accès par indice O(n). Tableau : insertion en tête O(n), accès par indice O(1) ; insérer en tête décale les éléments. |  |  |
| 8 | Comment un parcours par niveaux visite-t-il un arbre binaire ? | Une file FIFO permet de visiter les niveaux de profondeur successifs. Enfiler l'enfant gauche avant l'enfant droit donne l'ordre de gauche à droite. |  |  |
| 9 | Qu'est-ce qu'un trie et quand la recherche d'une clé de L caractères y coûte-t-elle O(L) ? | Un arbre de préfixes stocke les clés sur des chemins de caractères, avec des marqueurs de clé complète. La recherche coûte O(L) si chaque transition vers le caractère suivant coûte O(1). |  |  |
| 10 | Que produit un parcours infixe d'un BST à clés distinctes ? | Toutes les clés dans l'ordre strictement croissant, en visitant n nœuds en O(n). |  |  |
| 11 | Combien coûte la construction d'un tas de bas en haut à partir de n éléments ? | O(n). La plupart des nœuds sont proches des feuilles et nécessitent peu de descentes ; sommer le travail selon la hauteur des nœuds donne un total linéaire. |  |  |
| 12 | Dans un tableau de tas de longueur n indexé à partir de zéro, où sont le parent et les enfants du nœud i ? | Parent : ⌊(i−1)/2⌋ si i>0. Enfants : 2i+1 et 2i+2, seulement si ces indices sont inférieurs à n. L'indice 0 n'a pas de parent. |  |  |
| 13 | Classe ces croissances de la plus lente à la plus rapide lorsque n → ∞ : n!, n, 1, n², log n, 2ⁿ, n log n. | Asymptotiquement : 1 < log n < n < n log n < n² < 2ⁿ < n!. |  |  |
| 14 | Qu'est-ce que le facteur de charge d'une table de hachage et pourquoi la redimensionner ? | α = n/m : n entrées stockées et m compartiments ou cases. Dépasser le seuil choisi par l'implémentation peut déclencher un agrandissement et un rehachage ; 0,75 n'est pas universel. |  |  |
| 15 | Quelles sont les deux propriétés d'un tas binaire minimum ? | C'est un arbre binaire complet, et la clé de chaque parent ne dépasse pas celles de ses enfants. La racine contient donc un minimum. |  |  |
| 16 | Pour des fonctions f et g non négatives, que signifie f(n) ∈ O(g(n)) ? | Il existe des constantes c > 0 et n₀ ≥ 0 telles que f(n) ≤ c·g(n) pour tout n ≥ n₀. |  |  |
| 17 | Quel invariant d'ordre définit un arbre binaire de recherche (BST) à clés distinctes ? | À chaque nœud, toutes les clés du sous-arbre gauche sont inférieures et toutes celles du sous-arbre droit sont supérieures. La règle s'applique récursivement. |  |  |
| 18 | Combien coûtent l'insertion, le retrait de la racine et sa consultation dans un tas binaire ? | Respectivement O(log n), O(log n) et O(1), sans redimensionnement du tableau. Un redimensionnement peut coûter O(n). |  |  |
| 19 | Pourquoi peut-on supprimer un nœud donné d'une liste doublement chaînée en O(1) ? | Ses liens précédent et suivant permettent de reconnecter directement ses voisins. Il faut actualiser la tête ou la queue si nécessaire, sans rechercher le prédécesseur. |  |  |
| 20 | Avec doublement de capacité, quel est le coût amorti d'un ajout en fin de tableau dynamique ? | O(1) par ajout. Un redimensionnement peut coûter O(n), mais n ajouts depuis un tableau vide coûtent O(n) au total. |  |  |
| 21 | Comment fonctionne une pile et quand ses opérations sont-elles en O(1) ? | LIFO : le dernier élément empilé est dépilé en premier. En tête de liste chaînée, empiler, dépiler et consulter le sommet coûtent O(1) ; redimensionner un tableau peut porter un empilement à O(n). |  |  |
| 22 | Que distinguent compression de chemins, union par rang et union par taille ? | La compression redirige les nœuds visités vers la racine. Le rang place la racine de rang inférieur sous celle de rang supérieur ; la taille place le plus petit ensemble sous le plus grand. Le rang n'est pas nécessairement la hauteur actuelle. |  |  |
| 23 | Quel ordre d'accès suit une file et quels sont les coûts habituels de ses opérations ? | FIFO : ajout à l'arrière, retrait à l'avant. Les deux coûtent O(1) avec des liens de tête et de queue ou un tampon circulaire de capacité fixe ; décaler un tableau rend le retrait O(n). |  |  |
| 24 | Que font find et union dans une structure d'ensembles disjoints ? | find(x) renvoie le représentant de l'ensemble de x. union(x,y) fusionne leurs ensembles s'ils diffèrent ; s'ils sont déjà identiques, la partition reste inchangée. |  |  |
| 25 | Quels sont les coûts attendus et dans le pire cas pour une table de hachage à chaînage séparé ? | Avec charge bornée, hachage bien réparti et opérations sur les clés à coût constant, recherche et suppression coûtent O(1) en espérance. Avec croissance géométrique, l'insertion coûte O(1) amorti en espérance. Une chaîne de n clés en collision peut entraîner O(n). |  |  |
| 26 | Que distinguent les notations O, Ω et Θ ? | Elles donnent respectivement une borne asymptotique supérieure, inférieure et serrée. Elles décrivent une fonction de coût précisée ; O ne signifie pas en soi « pire cas ». |  |  |
| 27 | Comment corriger un déséquilibre gauche-droite après une insertion AVL ? | Tourner d'abord l'enfant gauche vers la gauche, puis le nœud déséquilibré vers la droite. |  |  |
| 28 | Quelles réponses peut donner un filtre de Bloom n'autorisant que les insertions ? | Un résultat négatif signifie que l'élément n'a pas été inséré ; un résultat positif, qu'il a pu l'être. Les hachages activent des bits d'un tableau : des faux positifs sont possibles, mais pas de faux négatifs si l'état est intact. |  |  |
| 29 | Quelles règles de couleur maintiennent un BST rouge-noir équilibré ? | Les nœuds sont rouges ou noirs ; la racine et les feuilles NIL sont noires. Un nœud rouge n'a aucun enfant rouge. Tous les chemins d'un nœud à une feuille NIL descendante contiennent autant de nœuds noirs. Cela borne la hauteur à O(log n). |  |  |
| 30 | Comment le chaînage séparé résout-il les collisions de hachage ? | Chaque compartiment contient une collection d'entrées ayant cet indice, souvent une liste chaînée. Les clés distinctes partageant un compartiment restent des entrées distinctes. |  |  |
| 31 | Quelles propriétés une fonction de hachage doit-elle avoir pour rechercher dans une table ? | Elle doit être déterministe et bien répartir les clés attendues. Hacher une clé de taille fixe peut coûter O(1) ; hacher une nouvelle chaîne de L caractères coûte généralement O(L). |  |  |
| 32 | Quelle différence entre sondage linéaire et quadratique en adressage ouvert ? | Les entrées restent dans le tableau. Pour une taille m et un indice initial h, on sonde respectivement (h+i) mod m et (h+c₁i+c₂i²) mod m. Le sondage quadratique exige des paramètres adaptés. |  |  |

---
Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/834a3679-6076-46e9-a401-3213176fc66d/).
