Structures de données et algorithmes Jeudi le 12 Février 2004 - UQAC
12 févr. 2004 ... Programmation, Structures de Jeudi le 9 Février 2006. ... A. Résoudre les
exercices suivants du chapitre 5 de Shaffer (pages 133, 135, 136 et 137):. exo. ...
deux piles ayant en commun le même tableau, comme illustré par la ...
part of the document
Programmation, Structures de Jeudi le 9 Février 2006.
données et algorithmes
8SIF109 session hiver 2006.
Série 4 : Listes, piles et files
(consultez la correction de certains de ces exercices sur ma page web.)
A. Résoudre les exercices suivants du chapitre 5 de Shaffer (pages 133, 135, 136 et 137):
exo. 1; exo. 3; exo. 5; exo. 7; exo. 12; exo. 14; exo. 15; exo. 18; exo. 20;
Exo1. Soit la liste L ayant la configuration . Écrire une série dinstructions utilisant les opérations de la classe LISTE pour supprimer lélément 15. (voir Shaffer , page 90).
Exo.3 : Créer une liste pouvant contenir 20 éléments à laide des opérations de la classe LISTE.
Exo.5 : Ajouter à la classe LISTE la fonction qui renverse lordre des liste de la liste. Lalgorithme doit sexécuter en O(n).
Exo.7 : À la section 4.1.3. (page : 105) du livre de Shaffer, il est énoncé : « Lespace requis dans limplantation dune liste à laide dun tableau est en ((n), mais peut être plus grand. » Expliquer pourquoi.
Exo. 12. Modifier le code de la Figure 424 (page121) pour implanter deux piles ayant en commun le même tableau, comme illustré par la Figure 4.27 (page 124).
Exo. 14 : Un palindrome est une chaîne de caractères qui se lit de la même manière de gauche à droite e de droite à gauche. En utilisant un nombre fixe de pile et de files, les opérations de la classe PILE et FILE, et un nombre fixe de variables de type INT et CHAR, écrire un algorithme qui détermine si une chaîne de caractère est un palindrome. On suppose que la chaîne de caractère est lue à partir du clavier caractère par caractère. Lalgorithme doit donner en sortie TRUE ou FALSE selon le cas.
Exo. 15. Réimplanter la fonction fibr ci-dessous en utilisant une pile pour remplacer les appels récursifs.
long fibr(int n) {
assert((n>0) && (n 3) && ( a < 9) || !(a >0)
((b * b 4 * a *c) >= 0) && ((a > 0) || (a < 0))
F(28-35). Convertir les expressions suivantes en notations infixes :
a b c + - d *
a b + c d - *
a b c d + - *
a b + c d e *
a b / c / d /
a b / c d / /
a b c / d / /
a b c d / / /
G(1-10). Supposons que a = 7.0, b = 4.0, c = 3. et d = -2.0, évaluez chacune des expressions suivantes :
a b + c / d *
a b c + / d *
a b c d + / *
a b + c + d +
a b + c d + +
a b c + + d +
a b c d + + +
a b c d
a b c d
a b c - - d
a b c d - - -
H(61-68) : Une alternative à la notation postfixe est celle de la notation prefixe. Dans cette dernière, le symbole pour chaque opération précède les opérandes. Par exemple, lexpression 2 * 3 + 4 en prefixe va être + * 2 3 4; et 2 *(3+4) est écrite en prefixe comme * 2 + 3 4. Évaluez les expression prefixes suivantes pour a = 7.0; b = 4.0; c = 3.0 et d = -2.0:
1. * a / + b c d
2. * / + a b c d
3. a b c d
4. - - a b c d
5. a - - b c d
6. - - - a b c d
7. * + a b c d
8. + * a b c d
I(8) Dans lalgorithme donné en cours, convertissant une notation infixe en notation polonaise, il y est supposé une associativité de gauche; cest-à-dire quand deux ou plus opérateurs consécutifs de même priorité, ils sont évalué de gauche à droite. Par exemple 6 3 1 est évalué comme étant (6-3)-3 et non comme 6 (3-1). Lassociativité de droite, en revanche est utilisée pour lexponentiation (en fortran, elle est notée par **). Dans ce cas, lexpression 2 ** 3 ** 4 est évaluée comme 2 ** (3 ** 4), cest-à-dire EMBED Equation.3 et non (2 ** 3)** 4 cest-à-dire EMBED Equation.3 . Changez lalgorithme donné en cours de telle manière à prendre en considération lopérateur ** ayant la plus grande priorité.
Indice : Une approche est dutiliser deux priorités pour cette opérateur : une dans lexpression infixe et lautre quand il est dans la pile.
J(16). Écrire un programme qui convertit une expression en post-fixe en une expression infixe qui lui correspond. Par exemple a b + et a b + c d - * vont donner (a + b) et ((a +b) * (c + d)), respectivement.
PAGE
PAGE 1
