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 chaîne de caractères
2. BUn tas (heap)
3. CUne pile (stack)
4. DUne liste simplement chaînée non ordonnée

La hauteur d'un arbre est couramment définie comme :

1. ALe nombre d'enfants de la racine
2. BLe nombre total de nœuds de l'arbre, en comptant la racine et chaque feuille
3. CLe nombre d'arêtes du plus long chemin de la racine à une feuille
4. DLe nombre de feuilles de l'arbre

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

1. AEnsemble haché (hash set)
2. BFile (queue)
3. CGraphe
4. DPile (stack)

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

Un parcours infixe (in-order) d'un arbre binaire de recherche visite les clés dans :

1. AToujours l'ordre décroissant
2. BL'ordre par niveaux
3. CL'ordre d'insertion
4. DL'ordre croissant

Un arbre binaire a pour racine 1, avec 2 comme enfant gauche et 3 comme enfant droit ; le nœud 2 a pour enfants 4 (gauche) et 5 (droit). Quel est le parcours postfixe ?

1. A4 5 2 3 1
2. B1 2 4 5 3
3. C5 4 3 2 1
4. D4 2 5 1 3

Quels sont les coûts en temps et en espace supplémentaire de l'inversion sur place d'une liste simplement chaînée ?

1. AO(n log n) en temps et O(1) en espace supplémentaire
2. BO(n) en temps et O(n) en espace supplémentaire
3. CO(1) en temps et O(1) en espace supplémentaire
4. DO(n) en temps et O(1) en espace supplémentaire

Les clés 5, 3, 8, 1 sont insérées dans cet ordre dans un tas binaire min vide stocké dans un tableau. Quel est le tableau final ?

1. A[1, 3, 5, 8]
2. B[1, 3, 8, 5]
3. C[1, 5, 8, 3]
4. D[3, 1, 8, 5]