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

Dans une représentation d'un graphe par listes d'adjacence, que stocke-t-on pour chaque sommet ?

1. ALe plus court chemin vers tous les autres sommets
2. BLa liste de ses sommets voisins
3. CLe nombre total d'arêtes du graphe
4. DUne ligne de V valeurs booléennes

Comment s'appelle l'opération de file qui retire l'élément situé à l'avant ?

1. ADequeue (défiler)
2. BInsert (insérer)
3. CEnqueue (enfiler)
4. DPush (empiler)

Qu'est-ce qu'un deque (file à double extrémité) ?

1. AUne structure qui permet l'insertion et la suppression aux deux extrémités
2. BUne file qui ne permet la suppression qu'à l'arrière
3. CDeux files distinctes partageant un même tableau
4. DUne file triée par priorité

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

1. AUne pile
2. BUne table de hachage
3. CUn arbre binaire de recherche
4. DUne file

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 d'insertion
3. CL'ordre par niveaux
4. DL'ordre croissant

Quelle est la valeur de l'expression postfixée 3 4 + 2 * ?

1. A14
2. B10
3. C24
4. D11

Combien de temps faut-il pour rechercher une clé quelconque dans un tas binaire min de n éléments ?

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

Quel est le principal avantage d'une liste à enjambements (skip list) par rapport à une liste chaînée triée ?

1. AElle stocke les clés sans ordre
2. BElle n'utilise aucune mémoire supplémentaire
3. CUne recherche en O(log n) en moyenne grâce à plusieurs niveaux de pointeurs avant
4. DUne recherche en O(1) garantie, car chaque nœud stocke un pointeur vers tous les autres nœuds