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

Dans une liste simplement chaînée, que contient le pointeur next du dernier nœud ?

1. AL'adresse du premier nœud
2. BLe nombre de nœuds de la liste
3. CNull (aucun nœud)
4. DL'adresse du nœud précédent

Dans une liste simplement chaînée, chaque nœud contient :

1. ADes données et des références vers tous les autres nœuds
2. BDes données et un indice
3. CDes données et une référence vers le nœud suivant
4. DUniquement des données

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

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

Une application a besoin de recherches rapides, mais aussi de lister les clés dans l'ordre trié et de répondre à des requêtes par intervalle. Quelle structure convient le mieux ?

1. AUne pile
2. BUne liste chaînée non triée
3. CUne table de hachage
4. DUn arbre binaire de recherche équilibré

Un nœud d'un arbre binaire de recherche possède un sous-arbre droit. Où se trouve son successeur dans l'ordre infixe ?

1. AAu nœud le plus à gauche de son sous-arbre droit
2. BÀ son parent, toujours
3. CAu nœud le plus à droite de son sous-arbre gauche
4. DÀ son enfant droit, toujours

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

1. AUne pile
2. BUne file
3. CUne table de hachage
4. DUn arbre binaire de recherche

Sous l'hypothèse de hachage uniforme simple, quel est le temps attendu d'une recherche dans une table de hachage à chaînage contenant n clés et m compartiments ?

1. AO(n)
2. BO(log n)
3. CO(1 + α), où α = n / m
4. DO(m)

Quelle propriété un arbre rouge-noir doit-il respecter ?

1. ALa racine doit être rouge
2. BTout nœud rouge doit avoir des enfants rouges, si bien que les nœuds rouges forment toujours des chaînes ininterrompues jusqu'aux feuilles
3. CTout chemin d'un nœud vers ses feuilles descendantes contient le même nombre de nœuds noirs
4. DChaque nœud doit être rouge