Français
Menu

Structures de données et algorithmes

Les enregistrements (nom, note) (A, 80), (B, 70), (C, 80), (D, 70) sont dans cet ordre. Si on les trie par note croissante avec un tri stable, dans quel ordre les noms apparaissent-ils ?

  1. AB, D, A, C
  2. BD, B, A, C
  3. CB, D, C, A
Afficher la réponse et l'explication

Réponse : A. B, D, A, C

Un tri stable conserve l'ordre relatif d'origine des éléments de même clé (ici, la note). B et D, tous deux à 70, restent dans l'ordre B, D, et A et C, tous deux à 80, restent dans l'ordre A, C, ce qui donne B, D, A, C. Le tri à bulles, le tri par insertion et le tri fusion sont stables, alors que le tri par sélection, le tri rapide et le tri par tas ne le sont généralement pas. Avec un tri stable, on peut trier selon plusieurs clés, par exemple trier d'abord par nom, puis par note.

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

Autres questions sur Structures de données et algorithmes

  1. Quel est le cas typique dans lequel la complexité temporelle du tri rapide devient O(n²) ?
  2. 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 ?
  3. 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] ?
  4. 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 ?
  5. 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.