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

Dans un arbre, que sont des nœuds frères ?

1. ADes nœuds de même profondeur dans des sous-arbres différents
2. BDes nœuds qui ont le même parent
3. CDes nœuds qui n'ont pas d'enfant
4. DUn nœud et son parent

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

1. AÀ la racine
2. BDans la feuille la plus à gauche
3. CÀ la dernière position du tableau
4. DDans une feuille quelconque, qu'il faut chercher

Qu'est-ce qu'un graphe orienté ?

1. AUn graphe dont les arêtes ont une direction d'un sommet vers un autre
2. BUn graphe qui n'a pas de cycle
3. CUn graphe dont toutes les arêtes ont un poids
4. DUn graphe dans lequel chaque paire de sommets distincts est reliée par une arête

Dans un tas binaire stocké dans un tableau commençant à l'indice 0, où se trouve le parent du nœud d'indice i ?

1. AÀ l'indice ⌊(i − 1) / 2⌋
2. BÀ l'indice 2i + 1
3. CÀ l'indice ⌊i / 2⌋ + 1
4. DÀ l'indice i − 1

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

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

Comment trouve-t-on la clé minimale dans un arbre binaire de recherche ?

1. AOn regarde uniquement la racine
2. BOn suit les enfants gauches depuis la racine jusqu'à ce qu'il n'y en ait plus
3. COn suit les enfants droits depuis la racine jusqu'à ce qu'il n'y en ait plus
4. DOn visite toutes les feuilles et on les compare

Vous devez conserver les k plus petites valeurs d'un flux de n nombres en utilisant O(k) mémoire. Quelle approche fonctionne en O(n log k) ?

1. AUn tas max de taille k, dont on remplace la racine lorsqu'une valeur plus petite arrive
2. BUn tas min contenant les n valeurs, dont on extrait les k plus petites à la fin
3. CUn tableau trié de toutes les n valeurs
4. DUne file FIFO des k dernières valeurs

Un nœud AVL est déséquilibré parce que le sous-arbre droit de son enfant gauche est devenu trop haut (cas gauche-droite). Quelle correction applique-t-on ?

1. AUne rotation à gauche sur l'enfant gauche, puis une rotation à droite sur le nœud
2. BUne rotation à droite sur l'enfant gauche, puis une rotation à gauche sur le nœud
3. CUne rotation simple à gauche sur le nœud
4. DUne rotation simple à droite sur le nœud