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

Comment s'appelle l'opération de pile qui ajoute un élément au sommet ?

1. APush (empiler)
2. BEnqueue (enfiler)
3. CPeek (consulter)
4. DPop (dépiler)

Dans un graphe, qu'est-ce qu'un cycle ?

1. AUn chemin qui passe par tous les sommets
2. BUn chemin qui commence et se termine au même sommet
3. CUn sommet sans arête
4. DUne arête de poids nul

Quelle est la caractéristique essentielle d'un ensemble en tant que type abstrait de données ?

1. AIl ne permet l'accès qu'à une seule extrémité
2. BIl stocke des paires clé–valeur
3. CIl stocke des éléments dans l'ordre trié
4. DIl stocke des éléments sans doublons

Un tampon circulaire (ring buffer) est couramment utilisé pour implémenter :

1. AUn arbre binaire de recherche
2. BUne file de taille fixe
3. CUn parcours de graphe
4. DUne fonction de hachage

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

Dans un tas binaire stocké dans un tableau commençant à l'indice 0, où se trouve le parent du nœud d'indice i ?

1. AÀ l'indice i − 1
2. BÀ l'indice ⌊i / 2⌋ + 1
3. CÀ l'indice 2i + 1
4. DÀ l'indice ⌊(i − 1) / 2⌋

Un nœud AVL est déséquilibré parce que le sous-arbre droit de son enfant gauche est devenu trop haut (cas gauche-droite). Quelle correction applique-t-on ?

1. AUne rotation simple à gauche sur le nœud
2. BUne rotation simple à droite sur le nœud
3. CUne rotation à droite sur l'enfant gauche, puis une rotation à gauche sur le nœud
4. DUne rotation à gauche sur l'enfant gauche, puis une rotation à droite sur le nœud

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

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