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

Quelle structure est généralement utilisée pour implémenter une file de priorité ?

1. AUne liste simplement chaînée non ordonnée
2. BUne chaîne de caractères
3. CUne pile (stack)
4. DUn tas (heap)

Combien d'arêtes possède un arbre à n nœuds ?

1. An + 1
2. Bn − 1
3. C2n
4. Dn

Quelle est la principale différence entre un tableau statique et un tableau dynamique ?

1. AUn tableau dynamique stocke ses éléments dans des nœuds chaînés, ce qui lui permet de grandir un élément à la fois
2. BUn tableau dynamique peut grandir en passant à un bloc de mémoire plus grand
3. CUn tableau statique offre un accès par indice plus lent
4. DUn tableau statique ne peut stocker que des nombres

Un tampon circulaire (ring buffer) est couramment utilisé pour implémenter :

1. AUn parcours de graphe
2. BUne file de taille fixe
3. CUne fonction de hachage
4. DUn arbre binaire de recherche

Quelle est la hauteur, dans le pire des cas, d'un arbre binaire de recherche à n nœuds si les clés sont insérées dans l'ordre trié ?

1. An (il devient une liste chaînée)
2. B1
3. C√n
4. Dlog₂ n

Un nœud d'un arbre binaire de recherche possède un sous-arbre droit. Où se trouve son successeur dans l'ordre infixe ?

1. AÀ son parent, toujours
2. BÀ son enfant droit, toujours
3. CAu nœud le plus à gauche de son sous-arbre droit
4. DAu nœud le plus à droite de son sous-arbre gauche

Sans union par rang ni compression de chemin, quel est le coût dans le pire cas d'une seule opération find dans une structure union-find à n éléments ?

1. AO(α(n))
2. BO(1)
3. CO(log n)
4. DO(n)

Vous devez conserver les k plus petites valeurs d'un flux de n nombres en utilisant O(k) mémoire. Quelle approche fonctionne en O(n log k) ?

1. AUn tas max de taille k, dont on remplace la racine lorsqu'une valeur plus petite arrive
2. BUne file FIFO des k dernières valeurs
3. CUn tas min contenant les n valeurs, dont on extrait les k plus petites à la fin
4. DUn tableau trié de toutes les n valeurs