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

Dans un arbre, qu'est-ce qu'une feuille ?

1. AUn nœud ayant exactement un enfant
2. BUn nœud sans enfant
3. CLe nœud de plus grande valeur
4. DUn nœud sans parent

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

1. AArbre binaire
2. BFile (queue)
3. CTas (heap)
4. DPile (stack)

Une table de hachage stocke les données sous forme de :

1. APaires clé–valeur localisées par une fonction de hachage
2. BChaîne de longueur fixe
3. CArbre à clés ordonnées
4. DListe triée uniquement

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

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

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 trié
4. DUn tableau dynamique

Quelle est la valeur de l'expression postfixée 3 4 + 2 * ?

1. A24
2. B10
3. C14
4. D11

Pourquoi un serveur pourrait-il choisir sa fonction de hachage au hasard dans une famille universelle ?

1. APour rendre très improbable qu'un attaquant puisse choisir de nombreuses clés qui entrent toutes en collision
2. BPour que la table de hachage soit triée
3. CPour supprimer le besoin de redimensionner la table
4. DPour garantir que deux clés n'entrent jamais en collision, quelles que soient les clés envoyées par un attaquant

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 tas max de taille k, dont on remplace la racine lorsqu'une valeur plus petite arrive
2. BUne file FIFO des k dernières valeurs
3. CUn tableau trié de toutes les n valeurs
4. DUn tas min contenant les n valeurs, dont on extrait les k plus petites à la fin