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. ATable de hachage
2. BPile (stack)
3. CListe chaînée
4. DFile (queue)

Combien d'arêtes possède un arbre à n nœuds ?

1. An + 1
2. B2n
3. Cn
4. Dn − 1

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. BInférieures à la valeur du nœud
3. CDans un ordre aléatoire
4. DÉgales à la valeur du nœud

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

1. AUniquement une table de hachage
2. BUne pile
3. CUn tas
4. DUne file

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 chaînage séparé (separate chaining)
2. BLe sondage quadratique (quadratic probing)
3. CLe double hachage (double hashing)
4. DLe sondage linéaire (linear probing)

Un réseau routier compte 100,000 carrefours, chacun relié à environ 4 autres. Quelle représentation est la plus adaptée ?

1. AUne liste d'adjacence
2. BUne matrice d'adjacence
3. CUn tas binaire d'arêtes
4. DUn unique tableau trié de sommets

Quelle paire de parcours détermine toujours un arbre binaire unique à clés distinctes ?

1. APar niveaux seul
2. BPréfixe seul
3. CPréfixe et postfixe
4. DPréfixe et infixe

L'algorithme de Kahn pour le tri topologique retire répétitivement les sommets de degré entrant 0. Quelle structure contient ces sommets ?

1. AUn tas max ordonné par degré sortant
2. BUne matrice d'adjacence indiquant quels sommets ont déjà été retirés
3. CUne pile de toutes les arêtes visitées
4. DUne file (ou toute collection) des sommets de degré entrant 0