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

Quelle opération est lente dans un tableau mais rapide en tête d'une liste chaînée ?

1. AL'accès au 5e élément
2. BLa lecture du dernier élément par son indice
3. CLe calcul de la longueur d'un tableau de taille fixe
4. DL'insertion au début

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

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

Dans une file circulaire stockée dans un tableau de capacité n, comment calcule-t-on la position suivant l'indice i ?

1. A(i + 1) mod n
2. Bi + 1
3. C(i − 1) mod n
4. D2i + 1

Dans un tas binaire stocké dans un tableau commençant à l'indice 0, où se trouve le parent du nœud d'indice i ?

1. AÀ l'indice ⌊i / 2⌋ + 1
2. BÀ l'indice i − 1
3. CÀ l'indice ⌊(i − 1) / 2⌋
4. DÀ l'indice 2i + 1

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

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

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. AUn recoloriage du nœud et de son enfant
2. BUne rotation simple à droite sur le nœud déséquilibré
3. CUne rotation à gauche sur l'enfant, puis une rotation à droite sur le nœud
4. DUne rotation simple à gauche sur le nœud déséquilibré

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

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