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

Dans un arbre, qu'est-ce qu'une feuille ?

1. AUn nœud sans parent
2. BUn nœud sans enfant
3. CLe nœud de plus grande valeur
4. DUn nœud ayant exactement un enfant

Quelle est la caractéristique essentielle d'un ensemble en tant que type abstrait de données ?

1. AIl stocke des éléments dans l'ordre trié
2. BIl ne permet l'accès qu'à une seule extrémité
3. CIl stocke des éléments sans doublons
4. DIl stocke des paires clé–valeur

Combien de nœuds possède un arbre binaire parfait de hauteur h, la hauteur étant comptée en arêtes ?

1. A2h + 1
2. Bh²
3. C2^h+1 − 1
4. D2^h

Quelle structure de données utilise-t-on pour vérifier si les parenthèses de "{[()]}" sont équilibrées ?

1. AUne file
2. BUne pile
3. CUne table de hachage
4. DUn arbre binaire de recherche

Quel type abstrait de données l'algorithme de Dijkstra utilise-t-il pour choisir le prochain sommet à traiter ?

1. AUne file de priorité min
2. BUne pile
3. CUne file FIFO
4. DUn ensemble sans ordre

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

1. APréfixe et infixe
2. BPar niveaux seul
3. CPréfixe seul
4. DPréfixe et postfixe

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

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