03/03/2012 Dure : 2 heures
I E. N. I. M.Dpartement Informatique
Examen Structures de Donnes
Documents non autoriss
Remarques :S Prciser, sur les copies, votre option et le nom de
votre professeur :
Mme OUAZZANI Khadija ou M LAZREK Mohamed S La rponse de chaque
question doit tre sur une page de votre copie en respectant lordre
des questions.
Problme ISoit une matrice M(n,m) dentiers positifs.La premire
colonne de cette matrice est trie par ordre croissant, elle sert
dindex pour ] c'est--dire tous les lments de chaque ligne i, sauf
le premier c'est--dire M(i,l) :
sont tris par ordre croissant et
sont suprieurs M (i-l,l) et infrieurs ou gales M(i,l)
,reste de la matrice
premier c'est--dire M (l,l) sont suprieurs 0 etRemarque : tous
les lments de la premire ligne, sauf 1 infrieurs ou gaux M
(l,l).
Exemple :100 0 9 20 40 100200 104 110 150 190 199300 208 230 270
280 290400 350 360 370 390 400500 407 410 420 470 480600 501 510
520 580 585
On suppose que la matrice est dj cre en mmoire.Question 1:Ecrire
lalgorithme qui permet dafficher pour chaque valeur de lindex la
valeur minimale et maximale.
Exemple :Valeur de lindex minimum maximum100 0 100200 104 199300
208 290400 350 400500 407 480600 501 585
,une valeur X dans la matrice.:2 Question
Ecrire lalgorithme qui permet de chercher lexistenceExemple
:
Pour X=360 ======> cette valeur existePour X* 155 =--===>
cette valeur nexiste pas
Structures de Donnes
Problme IIOn suppose que nous avons plusieurs clients et que
chaque client peut commander plusieurs articles.
Chaque client est repr par un matricule.Chaque article est repr
par :
un code darticle la quantit commande le prix unitaire
Ce problme peut tre reprsent dans la mmoire sous forme dune
liste de listes de la faon suivante : dbut
NULL
NULL
j] I -
Code quantit Prixarticle unitaire
NULLCode quantit Prix ............article unitaire
Chaque nud de la liste des clients est constitu de :> Mat :
matricule du client> Tete_commande : dbut de la liste des
commandes> Cli_suiv : le pointeur vers le client suivant
Chaque nud de la liste des articles est constitu de :> code :
code de larticle> quantit : quantit commande> prix : prix
unitaire de larticle command> Arti_suiv : le pointeur vers
larticle suivant
Ecrire lalgorithme, non rcursif, qui permet de calculer le
montant payer pour un client
donne par son matricule.
Montant payer = (quantit * prix)On suppose que la liste de
listes est dj cre en mmoire.
| fonction rcursive qui permet de calculer le nombre dccurrence
de chaque m arbre binaire.
faut crer une liste chane simple o chanque lment est compos
detrois champs :Valeur : valeur dun nud de )arbreCompteur : nombre
doccurrence de cette valeur dans larbreSuivant : pointeur ! llment
suivant de la liste
Cette liste est cre au firr et mesure du parcours de larbre de
la faon suivante :Pour chaque nud de larbre, on teste si la valeur
de ce nud existe dans la liste :
Si oui incrmente le compteurSi non on cre lment dans la liste on
affecte la valeur du nud Valeur et 1 au Compteur.
On suppose larb re b inaire est dj er.
Exemple :A partir de larbre binaire suivant :
: suivante [ obtient
1 ? 1 * 1 *4' Ilot 1 1 213 jNULL}
