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

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

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

Quelle structure est généralement utilisée pour implémenter une file de priorité ?

1. AUne pile (stack)
2. BUne chaîne de caractères
3. CUn tas (heap)
4. DUne liste simplement chaînée non ordonnée

Dans un graphe non orienté, qu'est-ce que le degré d'un sommet ?

1. ALa longueur du plus long chemin partant de lui
2. BSa position dans la liste d'adjacence
3. CLe nombre d'arêtes qui lui sont reliées
4. DLe nombre de sommets du graphe

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

1. AUn arbre binaire de recherche
2. BUne pile
3. CUne table de hachage
4. DUne file

Comment insère-t-on un nouvel élément dans un tas binaire ?

1. AOn reconstruit entièrement le tas
2. BOn le place à la fin du tableau et on le fait remonter tant qu'il viole la propriété de tas
3. COn le place à la racine et on le fait descendre
4. DOn l'insère à sa position triée en décalant d'un cran vers la droite tous les éléments plus grands

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

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

Comment détecter si une liste simplement chaînée contient un cycle avec O(1) mémoire supplémentaire ?

1. AAvancer un pointeur d'un pas et un autre de deux pas, et vérifier s'ils se rencontrent
2. BStocker chaque nœud visité dans un ensemble haché
3. CTrier la liste et chercher des doublons
4. DCompter les nœuds jusqu'à dépasser le champ de longueur de la liste

Dans l'algorithme de Kruskal pour l'arbre couvrant de poids minimal, à quoi sert la structure union-find ?

1. AÀ vérifier si les deux extrémités d'une arête sont déjà reliées
2. BÀ stocker la distance actuelle de chaque sommet depuis la source pendant le parcours
3. CÀ choisir le sommet de départ
4. DÀ trier les arêtes par poids