Examen Algorithme | Algorithme de tri – Algorithme récursif

Thèmes :

Exercice 1: Codage de Huffman / Arbre de Huffman / Algorithme de Huffman statique
Exercice 2: Arbres binaires de recherche / AVL / Arbre binaire / Clé minimale / Clé maximale / Complexité / Algorithme de tri / Scission / Algorithme récursif / Noeud
Exercice 3: Tas / Liste / Tableaux / Algorithme de tri
Exercice 4: Tris / Ordre lexicographique / Complexité linéaire /
Exercice 5: Tris lexicographique par bacs /

Extrait :

Cours d’algorithmique

Exercice 1 – Codage de Huffman
Calculer l’arbre de Huffmann associé au message A B A C F CA E D B A A E D A F
Quelle est la longueur du texte compressé par l’algorithme de Huffman statique ?

Exercice 2 – Arbres binaires de recherche et AVL
Construire tout les arbres binaires de recherche sur E={1,2,3,4} et indiquer lesquels sont des AVL.
Écrire une fonction permettant de trouver le sommet de clé minimale (respectivement maximale) d’un arbre binaire de recherche. Donner sa complexité.
Appliquer l’algorithme du tri par AVL à la suite {4,2,8,3,9,1,5,7,6}
Soit A un arbre binaire de recherche et s l’un de ces sommets. Une scission de A
autour de s est une couple ( ) d’arbres binaires de recherche tels que toutes
les cl´es des sommets de sont inf´erieures `a cl´e(s) et toutes les cl´es des sommets
de sont sup´erieures `a cl´e(s). Trouver un algorithme r´ecursif permettant de
r´ealiser la scission d’un arbre A autour d’un nœuds. Donner sa complexit´e.
Exercice 3 – Tas (4 points)
Les listes (1, 6, 1, 6, 7, 9, 1, 10, 6) et (1, 3, 1, 4, 3, 2, 1, 4, 2) peuvent elles
repr´esenter un tableau associ´e `a un tas ? Si non, quels ´echanges faut-il effectuer pour obtenir un tas ?
Une liste tri´ee repr´esente-t-elle un tas ?
Appliquer l’algorithme du tri par tas `a la suite (4, 2, 8, 3, 9, 1, 5, 7, 6).
Exercice 4 – Tris (6 points)
Soit T un tableau de n caract`eres entre A et Z. Donnez un algorithme pour trier
le tableau selon l’ordre lexicographique dont la complexit´e en temps soit lin´eaire.
Quelle est la complexit´e en espace de cet algorithme ? Peut-il ˆetre utilis´e quel que
soit le type des donn´ees ?
Soit T un tableau de n entiers. On suppose que chaque ´el´ement dans T vaut
0, 1 ou 2. Ecrire un algorithme pour trier le tableau T en utilisant la m´ethode
suivante : on d´ecompose le tableau en 4 zones, la premi`ere ne contient que des
0, la deuxi`eme que des 1, la quatri`eme que des 2. La troisi`eme zone contient des
el´ements non tri´es :
Trier le tableau T revient donc `a trier cette troisi`eme zone (d´elimit´ee par les indices j et k). Pour cela, on parcourt s´equentiellement de gauche `a droite cette troisi`eme
zone. Pour l’´el´ement courant de cette zone, trois cas se pr´esentent :
– c’est un 1 : il suffit d’accroˆıtre la zone des 1
– c’est un 2 : le permuter avec l’´el´ement le plus `a droite de la zone non tri´ee et
accroˆıtre la zone des 2
– c’est un 0 : le permuter avec l’´el´ement le plus `a gauche de la zone des 1,
– accroˆıtre la zone des 0 et “d´ecaler” la zone des 1
Initialement les deux premi`eres zones ainsi que la quatri`eme sont vides. Quelle est
la complexit´e de cet algorithme ?
Exercice 5 – Tri lexicographique par bacs (2 points)
Trier suivant l’ordre lexicographique les mots
maison
fleur
coussin
fable
cerise
eau
Pour cela on ´ecrira la colonne, ordonn´ee de haut en bas, obtenue apr`es chaque tri parbacs correspondant `a un indice des lettres. La derni`ere colonne doit contenir la suitetri´ee.

Aperçu :

Téléchargement: