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

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

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

Dans quel ordre un parcours préfixe (preorder) d'un arbre binaire visite-t-il les nœuds ?

1. ALe sous-arbre gauche, puis le sous-arbre droit, puis le nœud
2. BNiveau par niveau en partant du haut
3. CLe sous-arbre gauche, puis le nœud, puis le sous-arbre droit
4. DLe nœud, puis le sous-arbre gauche, puis le sous-arbre droit

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

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

Un trie (arbre de préfixes) est particulièrement efficace pour :

1. ALes recherches par préfixe, comme l'autocomplétion
2. BLe stockage de matrices
3. CLa recherche des plus courts chemins
4. DLe tri de nombres

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

Les arbres AVL et les arbres rouge-noir garantissent :

1. AQu'aucun nœud n'a deux enfants
2. BUne recherche en temps constant dans tous les cas
3. CQue les clés sont stockées dans l'ordre d'insertion
4. DUne hauteur en O(log n) grâce au rééquilibrage

Quel problème du sondage linéaire le double hachage réduit-il principalement ?

1. ALe regroupement primaire (primary clustering), où se forment de longues suites de cases occupées
2. BLe besoin d'une fonction de hachage
3. CLe coût en O(n) de la lecture de la valeur d'une clé
4. DLe besoin de stocker les clés dans la table

Vous devez conserver les k plus petites valeurs d'un flux de n nombres en utilisant O(k) mémoire. Quelle approche fonctionne en O(n log k) ?

1. AUn tableau trié de toutes les n valeurs
2. BUn tas max de taille k, dont on remplace la racine lorsqu'une valeur plus petite arrive
3. CUne file FIFO des k dernières valeurs
4. DUn tas min contenant les n valeurs, dont on extrait les k plus petites à la fin