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

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

1. AEnsemble haché (hash set)
2. BGraphe
3. CFile (queue)
4. DPile (stack)

Un graphe est constitué de :

1. ASommets (nœuds) reliés par des arêtes
2. BUniquement des clés et des hachages
3. CUniquement une racine et des feuilles
4. DLignes et colonnes

Qu'est-ce que la racine d'un arbre ?

1. ALe nœud ayant la plus grande valeur
2. BN'importe quel nœud au milieu
3. CUn nœud sans enfant
4. DLe nœud situé tout en haut, sans parent

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

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

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. B(i + 1) mod n
3. Ci + 1
4. D2i + 1

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(n²)
2. BO(log n)
3. CO(n)
4. DO(1)

Que fait un arbre splay (splay tree) après chaque accès ?

1. AIl recolorie les nœuds du chemin de recherche
2. BIl fait remonter le nœud accédé jusqu'à la racine par des rotations
3. CIl déplace le nœud accédé vers une feuille
4. DIl reconstruit tout l'arbre sous forme équilibrée

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. BToujours vider le tampon dès que front est égal à rear, si bien que l'état est vide
3. CTenir un compteur d'éléments séparé, ou toujours laisser une case inutilisée
4. DStocker front et rear dans la même variable