Français
Menu

Structures de données et algorithmes

Dans le tri fusion, on fusionne les deux séquences triées 1, 4, 7, 9 et 2, 3, 8, 10 en une seule en comparant de façon répétée leurs éléments de tête et en sortant le plus petit. Quand une séquence est vide, le reste de l'autre est sorti sans comparaison. Combien de comparaisons sont effectuées ?

  1. A4
  2. B7
  3. C8
Afficher la réponse et l'explication

Réponse : B. 7

Les comparaisons sont 1 contre 2, 4 contre 2, 4 contre 3, 4 contre 8, 7 contre 8, 9 contre 8 et 9 contre 10 ; à ce stade, la première séquence est vide et le 10 restant est sorti sans comparaison. Cela fait 7 comparaisons, le maximum m + n − 1 = 7 pour la fusion de séquences de longueurs m et n. Une fusion n'examine qu'une fois chaque élément des séquences triées et prend donc un temps en O(m + n) ; comme le tri fusion répète cette opération sur log₂ n niveaux, le tri complet prend un temps en O(n log n).

S'entraîner sur ce thème Retour au thème

Autres questions sur Structures de données et algorithmes

  1. Un tas binaire est stocké dans un tableau a[0], a[1], a[2], … avec la racine en a[0], en remplissant chaque niveau de gauche à droite à partir du haut. Quels sont les enfants et le parent de a[4] ?
  2. Un tas max, dans lequel la valeur de chaque parent est supérieure ou égale à celles de ses enfants, est stocké dans un tableau avec la racine en a[0]. On ajoute 45 au tas 50, 30, 40, 10, 20, 35 en le plaçant à la fin, puis en l'échangeant avec son parent tant qu'il est plus grand que celui-ci. Quel est le tableau obtenu ?
  3. Quand on parcourt un arbre binaire de recherche dans l'ordre infixe (sous-arbre gauche, puis le nœud, puis sous-arbre droit), dans quel ordre se présentent les valeurs des nœuds visités ? On suppose toutes les valeurs distinctes.
  4. On insère dans cet ordre les valeurs 50, 30, 70, 20, 40, 60, 80 dans un arbre binaire de recherche vide. Dans quel ordre les nœuds sont-ils visités quand on parcourt l'arbre dans l'ordre postfixe (sous-arbre gauche, sous-arbre droit, puis le nœud) ?
  5. On insère dans cet ordre les valeurs 1, 2, 3, …, 1000 dans un arbre binaire de recherche vide (sans aucun rééquilibrage). Lors de la recherche de 1000 dans cet arbre, combien de nœuds sont comparés, à partir de la racine, avant de le trouver ?