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

Quelle structure de données utilise-t-on pour effectuer un parcours en largeur (par niveaux) d'un arbre ?

1. AUne file
2. BUne pile
3. CUne file de priorité
4. DUne table de hachage

Quelle structure de données convient le mieux à la fonction « annuler » (undo) d'un éditeur de texte ?

1. AGraphe
2. BEnsemble haché (hash set)
3. CFile (queue)
4. DPile (stack)

Dans un graphe non orienté, qu'est-ce que le degré d'un sommet ?

1. ALe nombre d'arêtes qui lui sont reliées
2. BLa longueur du plus long chemin partant de lui
3. CLe nombre de sommets du graphe
4. DSa position dans la liste d'adjacence

Une file est implémentée avec deux piles : on empile sur une pile « in » et on dépile depuis une pile « out », remplie à partir de « in » lorsqu'elle est vide. Quel est le coût amorti par opération ?

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

Les clés 50, 30, 70, 20, 40 sont insérées dans cet ordre dans un arbre binaire de recherche vide. Quel est l'enfant gauche de 30 ?

1. A70
2. B50
3. C40
4. D20

Pourquoi le parcours d'un tableau est-il souvent bien plus rapide en pratique que celui d'une liste chaînée de même longueur ?

1. ALe parcours d'un tableau est en O(1) au total, alors que celui d'une liste chaînée est en O(n)
2. BLes tableaux utilisent moins d'instructions pour comparer les valeurs
3. CLes éléments d'un tableau sont contigus, ce qui exploite bien le cache du processeur
4. DLes listes chaînées stockent toujours leurs éléments sur disque

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

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

Un arbre de Fenwick (binary indexed tree) sur un tableau de n nombres permet quelles opérations en O(log n) ?

1. ALa recherche de la médiane en O(1)
2. BLe tri du tableau et la recherche dichotomique
3. CLes requêtes de sommes préfixes et les mises à jour d'un seul élément
4. DL'insertion d'éléments à n'importe quelle position