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

Quelle est la principale différence entre un tableau statique et un tableau dynamique ?

1. AUn tableau dynamique stocke ses éléments dans des nœuds chaînés, ce qui lui permet de grandir un élément à la fois
2. BUn tableau statique ne peut stocker que des nombres
3. CUn tableau dynamique peut grandir en passant à un bloc de mémoire plus grand
4. DUn tableau statique offre un accès par indice plus lent

Comment s'appelle l'opération de file qui retire l'élément situé à l'avant ?

1. ADequeue (défiler)
2. BPush (empiler)
3. CEnqueue (enfiler)
4. DInsert (insérer)

La profondeur d'un nœud dans un arbre est :

1. ALe nombre d'enfants de ce nœud
2. BLe nombre d'arêtes de ce nœud jusqu'à la feuille la plus profonde
3. CLe nombre d'arêtes de la racine jusqu'à ce nœud
4. DLe nombre de nœuds de son sous-arbre

Les arbres AVL et les arbres rouge-noir garantissent :

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

Que se passe-t-il lorsqu'une table de hachage est rehachée après que son facteur de charge a dépassé un seuil ?

1. ALes clés existantes sont triées sur place
2. BSeules les clés en collision sont déplacées dans une nouvelle liste de débordement à la fin de la table
3. CLes clés les plus anciennes sont supprimées pour faire de la place
4. DUne table plus grande est allouée et chaque clé y est réinsérée

Dans une table de hachage à adressage ouvert, quel est le facteur de charge maximal possible ?

1. A0,5
2. B1
3. CIl n'y a pas de maximum
4. D2

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

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

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