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

Quelle structure de données fonctionne selon le principe « premier entré, premier sorti » (FIFO) ?

1. ATas (heap)
2. BPile (stack)
3. CFile (queue)
4. DArbre binaire

Qu'est-ce qui définit un arbre binaire ?

1. AL'arbre a exactement deux niveaux
2. BChaque nœud a exactement deux enfants
3. CChaque nœud stocke un nombre binaire
4. DChaque nœud a au plus deux enfants

Dans quel ordre un parcours postfixe (postorder) d'un arbre binaire visite-t-il les nœuds ?

1. ALe nœud, puis le sous-arbre gauche, puis le sous-arbre droit
2. BLe sous-arbre gauche, puis le sous-arbre droit, puis le nœud
3. CLe sous-arbre gauche, puis le nœud, puis le sous-arbre droit
4. DLe sous-arbre droit, puis le nœud, puis le sous-arbre gauche

Les arbres AVL et les arbres rouge-noir garantissent :

1. AUne recherche en temps constant dans tous les cas
2. BQue les clés sont stockées dans l'ordre d'insertion
3. CQu'aucun nœud n'a deux enfants
4. DUne hauteur en O(log n) grâce au rééquilibrage

À quoi sert un nœud sentinelle (factice) dans une liste chaînée ?

1. AÀ stocker le nombre d'éléments
2. BÀ simplifier le code en supprimant les cas particuliers en tête ou en queue
3. CÀ empêcher la liste de dépasser un nombre maximal fixe de nœuds
4. DÀ rendre la liste triée

Quel est le coût de l'insertion d'un élément au milieu d'un tableau de n éléments ?

1. AO(1), car l'indice est connu
2. BO(n²), car chaque élément se déplace n fois
3. CO(n), car les éléments suivants doivent être décalés
4. DO(log n), grâce à la recherche dichotomique

L'insertion d'une clé dans un arbre AVL rend le sous-arbre gauche d'un nœud trop haut, et la nouvelle clé est allée dans le sous-arbre gauche de son enfant gauche (cas gauche-gauche). Quelle correction applique-t-on ?

1. AUne rotation simple à gauche sur le nœud déséquilibré
2. BUn recoloriage du nœud et de son enfant
3. CUne rotation simple à droite sur le nœud déséquilibré
4. DUne rotation à gauche sur l'enfant, puis une rotation à droite sur le nœud

Dans un tampon circulaire, front == rear peut signifier vide ou plein. Quelle est une manière courante de les distinguer ?

1. ATenir un compteur d'éléments séparé, ou toujours laisser une case inutilisée
2. BStocker front et rear dans la même variable
3. CToujours vider le tampon dès que front est égal à rear, si bien que l'état est vide
4. DChoisir une taille de tampon égale à une puissance de deux