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

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

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

Que fait l'opération peek (ou top) sur une pile ?

1. AElle renvoie l'élément du sommet sans le retirer
2. BElle retire tous les éléments de la pile
3. CElle renvoie l'élément du fond de la pile
4. DElle retire l'élément du sommet et le renvoie

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

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

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 unique tableau trié de sommets
4. DUn tas binaire d'arêtes

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

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

Un tableau dynamique double de taille lorsqu'il est plein. Pourquoi de nombreuses implémentations ne le réduisent-elles que lorsqu'il est rempli au quart, et non à moitié ?

1. AParce que l'allocateur de mémoire ne peut libérer la mémoire que par quarts de bloc
2. BPour garder le tableau trié
3. CParce que diviser par deux à la moitié ferait perdre des éléments
4. DPour éviter des redimensionnements répétés lorsque des push et des pop alternent près de la limite

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 stocke chaque mot dans une table de hachage à la racine au lieu de nœuds distincts
3. CIl trie les enfants de chaque nœud par fréquence
4. DIl ne garde que la première lettre de chaque mot