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. APeek (consulter)
2. BPop (dépiler)
3. CEnqueue (enfiler)
4. DPush (empiler)

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

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

Dans un arbre binaire de recherche, les valeurs du sous-arbre gauche d'un nœud sont :

1. ADans un ordre aléatoire
2. BÉgales à la valeur du nœud
3. CInférieures à la valeur du nœud
4. DSupérieures à la valeur du nœud

Combien de nœuds possède un arbre binaire parfait de hauteur h, la hauteur étant comptée en arêtes ?

1. A2^h
2. B2h + 1
3. Ch²
4. D2^h+1 − 1

Un parcours infixe (in-order) d'un arbre binaire de recherche visite les clés dans :

1. AL'ordre croissant
2. BToujours l'ordre décroissant
3. CL'ordre par niveaux
4. DL'ordre d'insertion

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

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

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

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

Quel est le temps d'exécution d'un parcours en largeur sur un graphe à V sommets stocké sous forme de matrice d'adjacence ?

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