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

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

1. AFile (queue)
2. BListe chaînée
3. CTable de hachage
4. DPile (stack)

Quelle structure est généralement utilisée pour implémenter une file de priorité ?

1. AUn tas (heap)
2. BUne liste simplement chaînée non ordonnée
3. CUne chaîne de caractères
4. DUne pile (stack)

Dans quel ordre un parcours postfixe (postorder) d'un arbre binaire visite-t-il les nœuds ?

1. ALe nœud, puis le sous-arbre gauche, puis le sous-arbre droit
2. BLe sous-arbre gauche, puis le nœud, puis le sous-arbre droit
3. CLe sous-arbre droit, puis le nœud, puis le sous-arbre gauche
4. DLe sous-arbre gauche, puis le sous-arbre droit, puis le nœud

Quelle structure de données un programme en cours d'exécution utilise-t-il pour suivre les appels de fonction actifs et leurs variables locales ?

1. ALa pile d'appels
2. BUn arbre binaire de recherche de cadres
3. CUne table de hachage des fonctions
4. DLa file de la mémoire du tas

Quelle méthode de résolution des collisions stocke les clés en collision dans une liste au sein du même compartiment ?

1. ALe double hachage (double hashing)
2. BLe sondage linéaire (linear probing)
3. CLe sondage quadratique (quadratic probing)
4. DLe chaînage séparé (separate chaining)

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

1. A24
2. B11
3. C10
4. D14

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

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

Comment détecter si une liste simplement chaînée contient un cycle avec O(1) mémoire supplémentaire ?

1. AAvancer un pointeur d'un pas et un autre de deux pas, et vérifier s'ils se rencontrent
2. BTrier la liste et chercher des doublons
3. CStocker chaque nœud visité dans un ensemble haché
4. DCompter les nœuds jusqu'à dépasser le champ de longueur de la liste