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 pile
2. BUne file de priorité
3. CUne file
4. DUne table de hachage

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

1. APile (stack)
2. BFile (queue)
3. CEnsemble haché (hash set)
4. DGraphe

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 statique ne peut stocker que des nombres
3. CUn tableau dynamique peut grandir en passant à un bloc de mémoire plus grand
4. DUn tableau statique offre un accès par indice plus lent

Quelle est la complexité temporelle de la recherche d'une clé dans un arbre binaire de recherche équilibré ?

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

Quelle structure de données est utilisée par le parcours en profondeur (DFS) dans sa version itérative ?

1. AUn tas
2. BUne pile
3. CUniquement une table de hachage
4. DUne file

Quelle structure de données utilise-t-on pour vérifier si les parenthèses de "{[()]}" sont équilibrées ?

1. AUne file
2. BUn arbre binaire de recherche
3. CUne table de hachage
4. DUne pile

Pour chaque élément d'un tableau, vous voulez le prochain élément plus grand à sa droite, en O(n) au total. Quelle structure aide ?

1. AUne table de hachage de tous les éléments
2. BUn arbre binaire de recherche reconstruit pour chaque élément
3. CUne file contenant toutes les paires d'éléments
4. DUne pile qui conserve les éléments en attente de leur réponse

Dans l'algorithme de Kruskal pour l'arbre couvrant de poids minimal, à quoi sert la structure union-find ?

1. AÀ stocker la distance actuelle de chaque sommet depuis la source pendant le parcours
2. BÀ choisir le sommet de départ
3. CÀ vérifier si les deux extrémités d'une arête sont déjà reliées
4. DÀ trier les arêtes par poids