Fiche d’exercices de Structures de données avec corrigé

Dans un arbre binaire de recherche, les valeurs du sous-arbre gauche d'un nœud sont :

1. ASupérieures à la valeur du nœud
2. BÉgales à la valeur du nœud
3. CDans un ordre aléatoire
4. DInférieures à la valeur du nœud

Que contient chaque nœud d'une liste doublement chaînée ?

1. ADeux copies des données et un pointeur
2. BDes données et uniquement un pointeur vers le nœud suivant
3. CDes données et deux pointeurs, l'un vers le nœud suivant et l'autre vers le nœud d'après
4. DDes données, un pointeur vers le nœud suivant et un pointeur vers le nœud précédent

Qu'est-ce que la racine d'un arbre ?

1. ALe nœud situé tout en haut, sans parent
2. BUn nœud sans enfant
3. CLe nœud ayant la plus grande valeur
4. DN'importe quel nœud au milieu

Un réseau routier compte 100,000 carrefours, chacun relié à environ 4 autres. Quelle représentation est la plus adaptée ?

1. AUne liste d'adjacence
2. BUne matrice d'adjacence
3. CUn unique tableau trié de sommets
4. DUn tas binaire d'arêtes

Quelle quantité de mémoire une matrice d'adjacence utilise-t-elle pour un graphe à V sommets ?

1. AO(V + E)
2. BO(log V)
3. CO(V²)
4. DO(E)

Dans une table de hachage à adressage ouvert, quel est le facteur de charge maximal possible ?

1. A1
2. B2
3. C0,5
4. DIl n'y a pas de maximum

Quelle structure de données permet un cache LRU (least recently used) avec get et put en O(1) ?

1. AUne table de hachage combinée à une liste doublement chaînée
2. BUniquement un arbre binaire de recherche
3. CUn unique tableau trié
4. DUniquement une pile

Quelle structure permet de calculer le maximum de chaque fenêtre de taille k dans un tableau en O(n) au total ?

1. AUn tableau trié mis à jour par décalage
2. BUn tas min reconstruit pour chaque fenêtre
3. CUn deque contenant des indices par ordre décroissant de valeur
4. DUne liste simplement chaînée des éléments de la fenêtre