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. AGraphe
2. BPile (stack)
3. CFile (queue)
4. DEnsemble haché (hash set)

Dans quel ordre un parcours postfixe (postorder) d'un arbre binaire visite-t-il les nœuds ?

1. ALe nœud, puis le sous-arbre gauche, puis le sous-arbre droit
2. BLe sous-arbre gauche, puis le sous-arbre droit, puis le nœud
3. CLe sous-arbre gauche, puis le nœud, puis le sous-arbre droit
4. DLe sous-arbre droit, puis le nœud, puis le sous-arbre gauche

Quelle structure de données fonctionne selon le principe « dernier entré, premier sorti » (LIFO) ?

1. APile (stack)
2. BFile (queue)
3. CTable de hachage
4. DListe chaîné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. AUne liste simplement chaînée
2. BUne liste doublement chaînée
3. CUn tableau dynamique
4. DUn tableau trié

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

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

Quel est le coût de l'insertion d'un élément au milieu d'un tableau de n éléments ?

1. AO(n²), car chaque élément se déplace n fois
2. BO(log n), grâce à la recherche dichotomique
3. CO(1), car l'indice est connu
4. DO(n), car les éléments suivants doivent être décalés

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

1. ATout chemin d'un nœud vers ses feuilles descendantes contient le même nombre de nœuds noirs
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. CLa racine doit être rouge
4. DChaque nœud doit être rouge

Quelle paire de parcours détermine toujours un arbre binaire unique à clés distinctes ?

1. APréfixe et postfixe
2. BPar niveaux seul
3. CPréfixe seul
4. DPréfixe et infixe