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

Que fait une fonction de hachage dans une table de hachage ?

1. AElle trie les clés de la table
2. BElle compte le nombre de clés stockées
3. CElle associe une clé à un indice de la table
4. DElle chiffre les valeurs de la table

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

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

Qu'est-ce que la racine d'un arbre ?

1. ALe nœud ayant la plus grande valeur
2. BUn nœud sans enfant
3. CN'importe quel nœud au milieu
4. DLe nœud situé tout en haut, sans parent

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

1. A11
2. B14
3. C10
4. D24

À quoi sert un nœud sentinelle (factice) dans une liste chaînée ?

1. AÀ stocker le nombre d'éléments
2. BÀ empêcher la liste de dépasser un nombre maximal fixe de nœuds
3. CÀ simplifier le code en supprimant les cas particuliers en tête ou en queue
4. DÀ rendre la liste triée

Quelle quantité de mémoire une matrice d'adjacence utilise-t-elle pour un graphe à V sommets ?

1. AO(V²)
2. BO(V + E)
3. CO(E)
4. DO(log V)

Un filtre de Bloom peut répondre à la question « cet élément appartient-il à l'ensemble ? » avec :

1. ADes faux positifs possibles mais aucun faux négatif
2. BDes faux négatifs possibles mais aucun faux positif
3. CDes réponses uniquement pour des nombres
4. DDes réponses toujours exactes

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