1. Quel est le principal inconvénient d'un arbre binaire de recherche (BST) non équilibré ?
Un arbre binaire de recherche non équilibré peut se dégrader en une liste chaînée, entraînant un temps d'accès linéaire O(n).
2. Quel algorithme utilise la stratégie de programmation dynamique pour résoudre le problème du plus court chemin ?
L'algorithme de Floyd-Warshall utilise la programmation dynamique pour trouver les plus courts chemins entre tous les paires de sommets.
3. Dans quel cas un tri par fusion (Merge Sort) est-il plus efficace qu'un tri rapide (Quick Sort) ?
Le tri par fusion est plus efficace avec de nombreux éléments dupliqués en raison de sa stabilité et de sa complexité temporelle O(n log n) dans tous les cas.
4. Quelle est la complexité de la recherche d'un élément dans un tableau trié en utilisant la recherche binaire ?
La recherche binaire a une complexité de O(log n), car elle divise par deux la taille du tableau à chaque itération.
5. Quelle structure de données est particulièrement utile pour implémenter un algorithme de Dijkstra ?
Un tas (Heap) est utilisé pour améliorer l'efficacité de l'algorithme de Dijkstra en permettant l'accès rapide au nœud ayant le poids minimal.
6. Quelle est la complexité temporelle de l'algorithme de Prim pour trouver un arbre couvrant minimal ?
L'algorithme de Prim a une complexité de O(e + n log n) lorsqu'il est implémenté avec une file de priorité.
7. Quelle méthode est utilisée pour équilibrer un arbre rouge-noir ?
Les rotations sont utilisées pour rééquilibrer un arbre rouge-noir après l'insertion ou la suppression de nœuds.
8. Quel est le principal avantage de l'utilisation d'une table de hachage par rapport à une liste chaînée ?
Les tables de hachage permettent un accès en temps constant O(1) en moyenne, contrairement aux listes chaînées qui nécessitent un temps d'accès linéaire O(n).
9. Quel est l'algorithme de tri stable le plus efficace ?
Le tri par fusion est un algorithme stable avec une complexité de O(n log n), ce qui en fait un choix efficace pour le tri stable.
10. Quelle est la complexité de la fonction de recherche dans un arbre binaire équilibré ?
La recherche dans un arbre binaire équilibré a une complexité de O(log n), car la hauteur de l'arbre est logarithmique par rapport au nombre de nœuds.
Ajouter un commentaire
Veuillez vous connecter pour ajouter un commentaire.
Pas encore de commentaires.