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

Quelle opération est en O(1) pour un tableau mais en O(n) pour une liste simplement chaînée ?

1. AL'insertion en tête
2. BLa suppression de l'élément de tête
3. CL'accès à l'élément d'indice i
4. DLa lecture du premier élément

Qu'est-ce qui définit un arbre binaire ?

1. AChaque nœud a exactement deux enfants
2. BL'arbre a exactement deux niveaux
3. CChaque nœud stocke un nombre binaire
4. DChaque nœud a au plus deux enfants

Dans une table de hachage, qu'est-ce qu'une collision ?

1. AUne clé ne peut pas du tout être hachée
2. BDeux clés différentes sont associées au même indice
3. CDeux clés égales sont stockées deux fois
4. DLa table manque de mémoire

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 unique tableau trié de sommets
3. CUne liste d'adjacence
4. DUn tas binaire d'arêtes

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

Un parcours infixe (in-order) d'un arbre binaire de recherche visite les clés dans :

1. AL'ordre d'insertion
2. BL'ordre par niveaux
3. CToujours l'ordre décroissant
4. DL'ordre croissant

Sans union par rang ni compression de chemin, quel est le coût dans le pire cas d'une seule opération find dans une structure union-find à n éléments ?

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

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