1. Quelle est la complexité temporelle de l'algorithme de tri par tas (HeapSort) ?
Le tri par tas (HeapSort) a une complexité temporelle de O(n log n) en moyenne et dans le pire des cas.
2. Quel est l'algorithme optimal pour résoudre le problème du sac à dos (Knapsack) ?
Le problème du sac à dos (Knapsack) est résolu de manière optimale par la programmation dynamique, en particulier la variante du sac à dos 0/1.
3. Quelle structure de données est utilisée pour la recherche en profondeur (DFS) dans un graphe ?
La recherche en profondeur (DFS) utilise une pile pour garder une trace des nœuds à explorer.
4. Quelle est la principale différence entre un arbre rouge-noir et un arbre AVL ?
L'arbre AVL est plus strictement équilibré que l'arbre rouge-noir, garantissant un meilleur temps d'accès au prix d'opérations de rééquilibrage plus fréquentes.
5. Quel algorithme est utilisé pour détecter les cycles dans un graphe orienté ?
L'algorithme de Tarjan est utilisé pour détecter les cycles dans un graphe orienté, en trouvant les composantes fortement connexes.
6. Quelle est la complexité spatiale de la recherche en largeur (BFS) dans un graphe ?
La complexité spatiale de la recherche en largeur (BFS) est O(n + e), où n est le nombre de nœuds et e est le nombre d'arêtes.
7. Quelle est la méthode la plus efficace pour trouver le k-ième plus grand élément dans un tableau non trié ?
Le tri rapide (QuickSort) modifié peut être utilisé pour trouver le k-ième plus grand élément en O(n) dans le cas moyen.
8. Quelle est la complexité temporelle de l'algorithme de Kruskal pour trouver l'arbre couvrant minimal ?
L'algorithme de Kruskal a une complexité temporelle de O(e log e), où e est le nombre d'arêtes dans le graphe.
9. Quelle est la principale caractéristique d'une table de hachage bien conçue ?
Une table de hachage bien conçue résout efficacement les collisions, souvent en utilisant des méthodes comme le chaînage ou l'open addressing.
10. Quel algorithme est utilisé pour résoudre le problème du plus court chemin avec des arêtes de poids négatif ?
L'algorithme de Bellman-Ford est capable de gérer les arêtes de poids négatif dans les graphes et peut détecter les cycles de poids négatif.
Ajouter un commentaire
Veuillez vous connecter pour ajouter un commentaire.
Pas encore de commentaires.