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

Qu'est-ce que la racine d'un arbre ?

1. AUn nœud sans enfant
2. BLe nœud ayant la plus grande valeur
3. CLe nœud situé tout en haut, sans parent
4. DN'importe quel nœud au milieu

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

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

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

1. ATas (heap)
2. BFile (queue)
3. CPile (stack)
4. DArbre binaire

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 préfixe ?

1. A4 2 5 1 3
2. B1 2 4 5 3
3. C4 5 2 3 1
4. D1 2 3 4 5

Comment fonctionne l'extraction du minimum (extract-min) dans un tas binaire min ?

1. AOn cherche le nouveau minimum parmi toutes les feuilles
2. BOn retire la racine et on décale tous les éléments d'une case vers la gauche
3. COn retire le dernier élément du tableau
4. DOn déplace le dernier élément à la racine et on le fait descendre

Une file est implémentée avec deux piles : on empile sur une pile « in » et on dépile depuis une pile « out », remplie à partir de « in » lorsqu'elle est vide. Quel est le coût amorti par opération ?

1. AO(1)
2. BO(n)
3. CO(log n)
4. DO(n²)

Dans l'algorithme de Kruskal pour l'arbre couvrant de poids minimal, à quoi sert la structure union-find ?

1. AÀ vérifier si les deux extrémités d'une arête sont déjà reliées
2. BÀ stocker la distance actuelle de chaque sommet depuis la source pendant le parcours
3. CÀ trier les arêtes par poids
4. DÀ choisir le sommet de départ

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

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