Scribd Logo
Importer

Bienvenue sur Scribd !

  • 26 vues

    Serie TD 2

    Transféré par

    Mounir Ad'n
    Ce document contient des exercices sur les files et les piles. Les exercices portent sur l'implémentation et l'utilisation de ces structures de données abstraites, ainsi que sur l'évaluation d'expressions arithmétiques préfixées.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    Serie TD 2

    Transféré par

    Mounir Ad'n
    26 vues2 pages
    Ce document contient des exercices sur les files et les piles. Les exercices portent sur l'implémentation et l'utilisation de ces structures de données abstraites, ainsi que sur l'évaluation d'expressions arithmétiques préfixées.

    Description originale:

    analyse 4

    Titre original

    serie td 2

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Ce document contient des exercices sur les files et les piles. Les exercices portent sur l'implémentation et l'utilisation de ces structures de données abstraites, ainsi que sur l'évaluation d'expressions arithmétiques préfixées.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    26 vues2 pages

    Serie TD 2

    Transféré par

    Mounir Ad'n
    Ce document contient des exercices sur les files et les piles. Les exercices portent sur l'implémentation et l'utilisation de ces structures de données abstraites, ainsi que sur l'évaluation d'expressions arithmétiques préfixées.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    Vous êtes sur la page 1sur 2

    Ecole Supérieure en Sciences et Technologies de l’Informatique et du Numérique 2021/2022

    Algorithmique 1 1ère année Classe Préparatoire

    Série de TD n° 2
    1. Files
    1

    Exercice 1.1
    Evaluer à l’aide des primitives de type abstrait ‘FileDeCaractères’ la fonction suivante et donner
    le contenu de la file après exécution. Considérer les deux cas d’implémentation (Tableau circulaire et
    LLC).

    Fonction My_File() : FileDeCaractères


    Var F : FileDeCaractères
    C, C1 : Caractère
    Début
    CreerFile(F)
    Enfiler(F, ‘A’)
    Enfiler(F,’B’)
    Enfiler(F,’C’)
    Defiler(F, C1)
    C  C1
    Enfiler(F,’a’)
    Defiler(F, C1)
    Enfiler(F, ‘b’)
    Enfiler(F,C)
    My_File  F
    Fin

    Exercice 1.2
    Ecrire une procédure qui permet d’inverser les éléments d’une liste linéaire chaînée dans une
    file.

    Exercice 1.3
    Considérons une file d’attente devant la caisse d’un magasin. La file initialement vide se remplit
    au fur et à mesure que les clients arrivent.
    — Proposer une structure de données permettant de gérer cette file.
    — Ecrire le sous-programme permettant d’ajouter un nouveau client dans la file.
    — Ecrire le sous-programme permettant de retirer le premier client de la file.
    — Ecrire le sous-programme permettant de calculer le nombre de clients de dans la file.

    Exercice 1.4

    Une file d'attente avec priorité est une collection dans laquelle tout nouvel élément est inséré‚
    selon sa priorité‚ et tout retrait se fait de la tête.

    — Implémenter le modèle correspondant au moyen des listes linéaires chaînées.


    — Ecrire un algorithme qui vérifie si les opérations écrites sont bien valides.

    1/2
    2. Piles
    Exercice 2.1
    Evaluer à l’aide des primitives de type abstrait ‘PileDeCaractères’ la fonction suivante et donner
    le contenu de la pile après exécution. Considérer les deux cas d’implémentation (Tableau circulaire
    et LLC).
    Fonction My_Pile() : PileDeCaractères
    Var P : PileDeCaractères
    C, C1 : Caractère
    Début
    CreerPile(P)
    Empiler(P, ‘A’)
    Empiler(P,’B’)
    Empiler(P,’C’)
    Depiler(P, C1)
    C  C1
    Empiler(P,’a’)
    Depiler(P, C1)
    Empiler(P, ‘b’)
    Empiler(P,C)
    My_Pile  P
    Fin

    Exercice 2.2
    Considérons une pile d’historique des liens visités sur le web. La pile initialement vide se
    remplit au fur et à mesure que l’utilisateur consulte des sites.

    — Proposer une structure de données permettant de gérer cette pile.


    — Ecrire le sous-programme permettant d’ajouter un nouveau lien dans la pile.
    — Ecrire le sous-programme permettant de retirer le premier lien de la pile.
    — Ecrire le sous-programme permettant de calculer le nombre de liens consultés.

    Exercice 2.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 en notation
    préfixée comme suit : /*++abc / *abcc
     Donner l'algorithme qui évalue une expression arithmétique préfixée. On suppose que
    chaque ordre de lecture délivre un caractère ‘c’ qui est soit un opérateur, soit un
    opérande. Les opérateurs sont binaires et limités à +, -, *, et /,

    Exercice 2.4

    Soit P1 une pile contenant des entiers positifs.


    — Ecrire un Sous-Programme pour déplacer les entiers de P1 dans une pile P2 de façon à
    avoir dans P2 tous les nombres pairs en dessous des nombres impairs.
    — Ecrire un Sous-programme pour copier dans P2 les nombres pairs contenus dans P1. Le
    contenu de P1 après exécution de l’algorithme doit être identique à celui avant
    exécution. Les nombres pairs dans P2 doivent être dans l’ordre où ils apparaissent dans
    P1.
    2/2

    Vous aimerez peut-être aussi