Structures de données avancées : Hashing, Heaps et LLRB

Question 1 sur 10 10:00

[{"id":8363,"question":"Quel est le temps d'exécution moyen d'une insertion dans une table de hachage avec un bon hachage uniforme ?","option_a":"O(1)","option_b":"O(log n)","option_c":"O(n)","option_d":"O(n²)","option_e":"","option_f":"","bonne_reponse":"A","explication":"Avec un hachage uniforme et une bonne gestion des collisions, l'insertion dans une table de hachage s'exécute en temps constant en moyenne.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0},{"id":8364,"question":"Dans un heap max, quel élément est toujours à la racine ?","option_a":"Vrai","option_b":"Faux","option_c":"","option_d":"","option_e":"","option_f":"","bonne_reponse":"A","explication":"Dans un heap max, le plus grand élément est toujours situé à la racine, garantissant une extraction efficace du maximum.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0},{"id":8365,"question":"Quelle propriété n'est PAS garantie par un arbre rouge-noir ?","option_a":"Tous les chemins de la racine aux feuilles ont la même longueur","option_b":"Aucun nœud rouge n'a un enfant rouge","option_c":"La racine est toujours noire","option_d":"Chaque feuille est noire","option_e":"","option_f":"","bonne_reponse":"A","explication":"Les arbres rouge-noir garantissent que tous les chemins de la racine aux feuilles ont une longueur similaire (équilibrage), mais pas nécessairement la même longueur exacte.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0},{"id":8366,"question":"Quelle opération sur un heap a une complexité temporelle de O(log n) ?","option_a":"Insérer un élément","option_b":"Trouver le maximum","option_c":"Extraire le maximum","option_d":"Afficher tous les éléments","option_e":"","option_f":"","bonne_reponse":"C","explication":"Extraire le maximum (ou minimum) dans un heap nécessite une opération de rééquilibrage, ce qui prend O(log n) temps.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0},{"id":8367,"question":"Le hachage parfait élimine totalement les collisions.","option_a":"Vrai","option_b":"Faux","option_c":"","option_d":"","option_e":"","option_f":"","bonne_reponse":"A","explication":"Le hachage parfait utilise des fonctions de hachage spécifiques pour éviter les collisions, mais cela dépend des données et n'est pas toujours réalisable en pratique.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0},{"id":8368,"question":"Quel est le rôle principal d'un arbre rouge-noir dans une base de données ?","option_a":"Stocker des clés de manière non triée","option_b":"Garantir des opérations rapides malgré des insertions\/suppressions fréquentes","option_c":"Optimiser la mémoire utilisée","option_d":"Permettre des recherches en O(1)","option_e":"","option_f":"","bonne_reponse":"B","explication":"Les arbres rouge-noir sont utilisés pour maintenir des structures de données équilibrées, assurant des opérations (recherche, insertion, suppression) en O(log n) même avec des modifications fréquentes.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0},{"id":8369,"question":"Dans une table de hachage avec chaînage, que contient chaque case de la table ?","option_a":"Un seul élément","option_b":"Une liste chaînée d'éléments","option_c":"Un arbre binaire","option_d":"Un tableau de taille fixe","option_e":"","option_f":"","bonne_reponse":"B","explication":"Avec le chaînage, chaque case de la table de hachage contient une liste (ou une autre structure) pour gérer les collisions en stockant plusieurs éléments ayant la même clé de hachage.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0},{"id":8370,"question":"Un heap peut être implémenté avec un tableau.","option_a":"Vrai","option_b":"Faux","option_c":"","option_d":"","option_e":"","option_f":"","bonne_reponse":"A","explication":"Un heap est souvent implémenté avec un tableau car cette structure permet un accès rapide aux éléments enfants (via des indices calculés) et facilite les opérations de rééquilibrage.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0},{"id":8371,"question":"Quelle est la complexité temporelle d'une recherche dans un arbre rouge-noir ?","option_a":"O(1)","option_b":"O(log n)","option_c":"O(n)","option_d":"O(n log n)","option_e":"","option_f":"","bonne_reponse":"B","explication":"Grâce à son équilibrage, la recherche dans un arbre rouge-noir s'effectue en O(log n) dans le pire des cas.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0},{"id":8372,"question":"Quel algorithme utilise une table de hachage pour une recherche efficace ?","option_a":"Tri à bulles","option_b":"Recherche linéaire","option_c":"Recherche dichotomique","option_d":"Table de hachage","option_e":"","option_f":"","bonne_reponse":"D","explication":"Les tables de hachage sont spécifiquement conçues pour permettre des recherches en temps constant (O(1)) en moyenne, grâce à un calcul de clé de hachage.","points":1,"type":"qcm","actif":1,"section_id":null,"ordre":0}]