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

Où se trouve le plus petit élément d'un tas binaire min ?

1. ADans une feuille quelconque, qu'il faut chercher
2. BÀ la dernière position du tableau
3. CDans la feuille la plus à gauche
4. DÀ la racine

Quelle structure de données convient le mieux à la fonction « annuler » (undo) d'un éditeur de texte ?

1. AEnsemble haché (hash set)
2. BGraphe
3. CFile (queue)
4. DPile (stack)

Dans une représentation d'un graphe par listes d'adjacence, que stocke-t-on pour chaque sommet ?

1. ALe plus court chemin vers tous les autres sommets
2. BLe nombre total d'arêtes du graphe
3. CUne ligne de V valeurs booléennes
4. DLa liste de ses sommets voisins

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

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

Pourquoi un tas binaire peut-il être stocké dans un tableau sans aucun pointeur ?

1. ALes tas ne contiennent jamais plus de 100 éléments
2. BLes tableaux maintiennent automatiquement les clés triées, donc aucun pointeur n'est nécessaire
3. CC'est un arbre binaire complet, donc les positions suivent des formules d'indice simples
4. DToutes les clés d'un tas sont égales

Quelle est la hauteur, dans le pire des cas, d'un arbre binaire de recherche à n nœuds si les clés sont insérées dans l'ordre trié ?

1. A1
2. Blog₂ n
3. C√n
4. Dn (il devient une liste chaînée)

Quelle affirmation sur le tri par tas (heapsort) est correcte ?

1. AIl nécessite un arbre binaire de recherche comme stockage supplémentaire, donc il utilise O(n) de mémoire en plus
2. BIl est stable et nécessite O(n) mémoire supplémentaire
3. CIl s'exécute en O(n) sur toute entrée
4. DIl trie sur place en O(n log n) dans le pire cas, mais n'est pas stable

Quel est le principal avantage d'une liste à enjambements (skip list) par rapport à une liste chaînée triée ?

1. AUne recherche en O(1) garantie, car chaque nœud stocke un pointeur vers tous les autres nœuds
2. BUne recherche en O(log n) en moyenne grâce à plusieurs niveaux de pointeurs avant
3. CElle n'utilise aucune mémoire supplémentaire
4. DElle stocke les clés sans ordre