Quiz : Structures de données et algorithmes

Les piles sont les mieux adaptées aux schémas d’accès LIFO. Les files sont les mieux adaptées aux schémas d’accès FIFO (premier entré, premier sorti).

O(1) représente une complexité temporelle constante. Cela signifie que l’algorithme prend toujours le même temps d’exécution, quelle que soit la taille de l’entrée.

Pour calculer la longueur d’une liste simplement chaînée, vous devez parcourir chaque nœud du début à la fin, ce qui donne une complexité temporelle de O(n).

Dans un BST équilibré, la complexité temporelle moyenne pour une recherche est O(log n) car chaque niveau réduit de moitié l’espace de recherche.

Le tri fusion fonctionne toujours avec une complexité dans le pire cas de O(n log n) car il divise de manière répétée le tableau en deux et fusionne les sous‑tableaux triés.

BFS utilise une file d’attente pour explorer les nœuds niveau par niveau, en traitant les nœuds de largeur (par « ligne »).

La recherche en profondeur (DFS) est généralement utilisée pour détecter les cycles dans un graphe en maintenant une pile de récursion pour suivre les nœuds visités.

Le tri par tas conserve une complexité temporelle de pire cas de O(n log n), car il construit un tas et extrait répétitivement l’élément maximal.

Les tables de hachage ont une complexité temporelle moyenne de O(1) pour accéder aux éléments, en supposant une fonction de hachage efficace qui minimise les collisions.

Les opérations principales d’une pile sont Push (ajouter un élément), Pop (supprimer un élément) et Peek (voir l’élément du sommet sans le supprimer).

L’algorithme de Dijkstra est fréquemment utilisé pour trouver le plus court chemin dans les graphes dont les poids des arêtes sont non négatifs. Il utilise une file de priorité pour déterminer la distance la plus courte de manière efficace.

Les arbres AVL et les arbres rouge-noir sont des types d’arbres auto‑équilibrés, qui garantissent que l’arbre reste équilibré après chaque insertion ou suppression.

Un cas de base est nécessaire dans une fonction récursive pour arrêter les appels récursifs lorsqu’une condition spécifique est remplie, évitant ainsi une récursion infinie.

Les deux opérations principales d’une file sont Enqueue (ajouter un élément à l’arrière) et Dequeue (retirer un élément à l’avant).

Le tri topologique peut être effectué sur un graphe s’il est orienté et acyclique (DAG). Ce type d’ordre est utile dans les problèmes de planification de tâches.

L’implémentation récursive naïve de la suite de Fibonacci a une complexité temporelle de O(2^n) en raison des calculs répétés et intensifs pour chaque nombre de Fibonacci.

Une file de priorité est le plus souvent implémentée à l’aide d’un tas car il permet une extraction efficace de l’élément de priorité la plus haute ou la plus basse.

Les parcours infixe (in-order), préfixe (pre-order) et postfixe (post-order) sont les trois ordres de parcours en profondeur les plus courants pour les arbres binaires, chacun visitant les nœuds dans un ordre différent. Le parcours en largeur est également fréquent, mais il appartient à une catégorie de parcours différente.

Dans un tas minimum, la racine est toujours le plus petit élément, et la hauteur de l’arbre est O(log n), ce qui rend l’insertion et l’extraction efficaces.

Avec cette comparaison stricte, les éléments de clés égales ne se dépassent jamais : le tri à bulles est donc stable. Une implémentation qui échange aussi les clés égales peut perdre cette propriété.