Structures de données et de fichiers
|
Enoncé 27. Listes linéaires chaînées - Piles - Récursivité Corrigé 27
Exercice 1 : Implémentation d'une liste linéaire chaînée de piles
Donner 4 cas d'implémentation d'une liste linéaire chaînée de piles. Il s'agit de donner les schémas correspondants puis les décrire ( structures de données) .
Exercice 2 : Traduction automatique d'une procédure récursive
Soit la procédure récursive suivante :
REC (X, Y, R) ; VALEUR X, Y : ENTIER ; VAR R : ENTIER
{ X et Y sont des données et R le résultat }
SI Y = 0 :
R<-- 0
SINON
REC( X * 2, Y Div 2, R)
SI NON Pair(Y) :
R <-- R + X
FSI
FSI
N.B : Div désigne la division entière, Pair(a) est un prédicat vrai si a est un entier pair, faux sinon.
- Donner une traduction automatique de la procédure
- Faire une trace pour x = 5 ; y = 5;
- Peut-on éliminer l'adresse de retour de la zone de données ? Si oui, donner l'algorithme résultant.
Exercice 3 : Evaluation d'une expression arithmétique préfixée
Une expression arithmétique préfixée est une expression o� les opérateurs sont placés avant les opérandes.
Exemple : l'expression (( a + b + c ) * ( a * b / c ) ) / c est exprimée comme suit :
/*++abc / *abcc
Donner l'algorithme qui évalue une expression arithmétique préfixée. On suppose que cette dernière se trouve sur le ruban de la machine-caractères. Chaque ordre de lecture délivre un caractère c qui est soit un opérateur, soit un opérande. Si c'est un opérande, Val(c) désigne la valeur associée à l'opérande.
NB. Les opérateurs sont tous binaires.
* * * * *
