IR1 – Cours d’Algorithmique 2Examen 9 janvier 2006 – Duree : 1h45

Notes de cours et tds autorisees.Redigez les algorithmes demandes en C ou en pseudocode, au choix.

Exercice 1 – Codage de Huffman (2 points)Calculez l’arbre de Huffman associe au message

A B A C F C A E D B A A E D A F

Quelle est la longueur du texte compresse par l’algorithme de Huffman statique ?

Exercice 2 – Arbres binaires de recherche et AVL (6 points)

• Contruire tous les arbres binaires de recherche sur E = {1, 2, 3, 4} et indiquerlesquels sont des AVL.

• Ecrire une fonction permettant de trouver le sommet de cle minimale (resp. max-imale) d’un arbre binaire de recherche. Donner sa complexite.

• Appliquer l’algorithme du tri par AVL a 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 (A1, A2) d’arbres binaires de recherche tels que toutesles cles des sommets de A1 sont inferieures a cle(s) et toutes les cles des sommetsde A2 sont superieures a cle(s). Trouver un algorithme recursif permettant derealiser la scission d’un arbre A autour d’un nœud s. Donner sa complexite.

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 ellesrepresenter un tableau associe a un tas ? Si non, quels echanges faut-il effectuerpour obtenir un tas ?

• Une liste triee represente-t-elle un tas ?

• Appliquer l’algorithme du tri par tas a la suite (4, 2, 8, 3, 9, 1, 5, 7, 6).

1

Exercice 4 – Tris (6 points)

• Soit T un tableau de n caracteres entre A et Z. Donnez un algorithme pour trierle tableau selon l’ordre lexicographique dont la complexite en temps soit lineaire.Quelle est la complexite en espace de cet algorithme ? Peut-il etre utilise quel quesoit le type des donnees ?

• Soit T un tableau de n entiers. On suppose que chaque element dans T vaut0, 1 ou 2. Ecrire un algorithme pour trier le tableau T en utilisant la methodesuivante : on decompose le tableau en 4 zones, la premiere ne contient que des0, la deuxieme que des 1, la quatrieme que des 2. La troisieme zone contient deselements non tries :

zone des 0 zone des 1 zone a trier zone des 2

↑ ↑ ↑i j k

Trier le tableau T revient donc a trier cette troisieme zone (delimitee par les indicesj et k). Pour cela, on parcourt sequentiellement de gauche a droite cette troisiemezone. Pour l’element courant de cette zone, trois cas se presentent :

– c’est un 1 : il suffit d’accroıtre la zone des 1

– c’est un 2 : le permuter avec l’element le plus a droite de la zone non triee etaccroıtre la zone des 2

– c’est un 0 : le permuter avec l’element le plus a gauche de la zone des 1,accroıtre la zone des 0 et “decaler” la zone des 1

Initialement les deux premieres zones ainsi que la quatrieme sont vides. Quelle estla complexite 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, ordonnee de haut en bas, obtenue apres chaque tri parbacs correspondant a un indice des lettres. La derniere colonne doit contenir la suitetriee.

2