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

Quelle structure de données convient le mieux à la fonction « annuler » (undo) d'un éditeur de texte ?

1. AFile (queue)
2. BGraphe
3. CEnsemble haché (hash set)
4. DPile (stack)

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

La hauteur d'un arbre est couramment définie comme :

1. ALe nombre d'enfants de la racine
2. BLe nombre d'arêtes du plus long chemin de la racine à une feuille
3. CLe nombre de feuilles de l'arbre
4. DLe nombre total de nœuds de l'arbre, en comptant la racine et chaque feuille

Quelle condition d'équilibre un arbre AVL maintient-il en chaque nœud ?

1. ALes deux sous-arbres de chaque nœud contiennent exactement le même nombre de nœuds
2. BLes hauteurs des sous-arbres gauche et droit diffèrent d'au plus 1
3. CToutes les feuilles sont exactement à la même profondeur
4. DChaque nœud est colorié en rouge ou en noir

Un réseau routier compte 100,000 carrefours, chacun relié à environ 4 autres. Quelle représentation est la plus adaptée ?

1. AUne matrice d'adjacence
2. BUn tas binaire d'arêtes
3. CUne liste d'adjacence
4. DUn unique tableau trié de sommets

Pourquoi le parcours d'un tableau est-il souvent bien plus rapide en pratique que celui d'une liste chaînée de même longueur ?

1. ALes éléments d'un tableau sont contigus, ce qui exploite bien le cache du processeur
2. BLes listes chaînées stockent toujours leurs éléments sur disque
3. CLe parcours d'un tableau est en O(1) au total, alors que celui d'une liste chaînée est en O(n)
4. DLes tableaux utilisent moins d'instructions pour comparer les valeurs

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

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

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

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