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é.

Category
Computer Science
Level
basic
Languages
fr → fr
Cards
32
Markdown
Structures de Données, Analyse de Complexité (Big-O) et Algorithmes Fondamentaux (.md)

Flashcards (32)

#Front (Term / Question)Back (Definition / Answer)ExampleMultiple-Choice Options
1Comment 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.
2Quels 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.
3Comment 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.
4Quelle 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.
5Quel 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.
6Pourquoi 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.
7Compare 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.
8Comment 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.
9Qu'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).
10Que 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).
11Combien 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.
12Dans 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.
13Classe 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!.
14Qu'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.
15Quelles 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.
16Pour 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₀.
17Quel 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.
18Combien 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).
19Pourquoi 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.
20Avec 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.
21Comment 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).
22Que 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.
23Quel 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).
24Que 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.
25Quels 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).
26Que 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 ».
27Comment 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.
28Quelles 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.
29Quelles 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).
30Comment 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.
31Quelles 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).
32Quelle 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.