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

Que stocke un dictionnaire (map) ?

1. ADes paires clé–valeur à clés uniques
2. BUniquement des valeurs dans l'ordre d'insertion
3. CDes valeurs triées par taille
4. DDes paires de clés égales

Dans un arbre binaire de recherche, les valeurs du sous-arbre gauche d'un nœud sont :

1. ASupérieures à la valeur du nœud
2. BÉgales à la valeur du nœud
3. CInférieures à la valeur du nœud
4. DDans un ordre aléatoire

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

1. AN'importe quel nœud au milieu
2. BLe nœud situé tout en haut, sans parent
3. CLe nœud ayant la plus grande valeur
4. DUn nœud sans enfant

Quelle structure de données est utilisée par le parcours en profondeur (DFS) dans sa version itérative ?

1. AUne file
2. BUn tas
3. CUniquement une table de hachage
4. DUne pile

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

Un arbre binaire a pour racine 1, avec 2 comme enfant gauche et 3 comme enfant droit ; le nœud 2 a pour enfants 4 (gauche) et 5 (droit). Quel est le parcours postfixe ?

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C5 4 3 2 1
4. D4 5 2 3 1

En quoi un arbre radix (trie compressé) améliore-t-il un trie simple ?

1. AIl stocke chaque mot dans une table de hachage à la racine au lieu de nœuds distincts
2. BIl trie les enfants de chaque nœud par fréquence
3. CIl fusionne les chaînes de nœuds à enfant unique en une seule arête étiquetée par une chaîne
4. DIl ne garde que la première lettre de chaque mot

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

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