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

Que fait l'opération peek (ou top) sur une pile ?

1. AElle retire tous les éléments de la pile
2. BElle retire l'élément du sommet et le renvoie
3. CElle renvoie l'élément du sommet sans le retirer
4. DElle renvoie l'élément du fond de la pile

La profondeur d'un nœud dans un arbre est :

1. ALe nombre d'arêtes de ce nœud jusqu'à la feuille la plus profonde
2. BLe nombre de nœuds de son sous-arbre
3. CLe nombre d'enfants de ce nœud
4. DLe nombre d'arêtes de la racine jusqu'à ce nœud

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

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

Combien de temps faut-il pour vérifier si l'arête (u, v) existe avec une matrice d'adjacence ?

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

Vous avez une référence vers un nœud au milieu d'une liste. Dans quelle liste pouvez-vous le supprimer en O(1) ?

1. AUn tableau dynamique
2. BUn tableau trié
3. CUne liste simplement chaînée
4. DUne liste doublement chaînée

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

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

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 pile qui conserve les éléments en attente de leur réponse
2. BUne table de hachage de tous les éléments
3. CUne file contenant toutes les paires d'éléments
4. DUn arbre binaire de recherche reconstruit pour chaque élément

La complexité temporelle de decrease-key dans un tas binaire (la position de l'élément étant connue) est :

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