Université de Yaoundé I

Faculté des Sciences

Département d’informatique

UE : INFO 112
Introduction aux structures de données

Année académique 2022 – 2023

Semestre 2
FICHE DE TD

Exercice 1: QUESTIONS DE COURS

1°) Définir les concepts suivants : Algorithmique ; Algorithme ; Liste chaînée ; Pile ; File ; Programme ;
Procédure.
2°) Donner la différence fondamentale entre une liste chaînée et un tableau.
3°) Pourquoi dit-on que les listes chaînées, les piles et les files sont des structures de d’ensembles dynamiques ?
4°) On considère une Pile dont les états sont donnés ci-contre :

1
4°) -a. Sachant que la Pile est modélisée à l’aide d’un tableau P de taille n et que l’attribut sommet[P] renvoie à
l’indice de l’élément au sommet de la Pile P. Décrire les différents états (a) ; (b) et (c) en se basant sur les
opérations d’ensembles dynamiques appropriées.
4°) -b. Ecrire une fonction DépilerPPE() qui dépile le plus petit élément d’une Pile P passée en paramètre. Pour
indication, vous pourrez vous servir d’une Pile secondaire. Quelle est la complexité temporelle de votre
algorithme ?
4°) -c. Ecrire les algorithmes qui réalisent les opérations de PILE-VIDE(P) ; PILE-PLEINE(P) ;
DEPILER(P) et EMPILER(P,x) où P est une Pile d’entiers et x est un entier.
5°) On considère une File dont les états sont donnés ci-contre :
5°) -a. Sachant que la File est modélisée à
l’aide d’un tableau F de taille n et que
l’attribut tête[F] renvoie à l’indice de
l’élément en tête de la File F, l’attribut
queue[F] renvoie à l’indice de l’élément
en queue de la File F. Décrire les
différents états (a) ; (b) et (c) en se basant
sur les opérations d’ensembles
dynamiques appropriées.

5°) -b. Ecrire une fonction DéfilerPPE()

qui défile le plus petit élément d’une File
F passée en paramètre. Pour indication,
vous pourrez vous servir d’une File
secondaire. Quelle est la complexité
temporelle de votre algorithme ?

5°) -c. Ecrire les algorithmes qui réalisent

les opérations de FILE-VIDE(F) ; FILE-
PLEINE(F) ; DEFILER(F) et
EMFILER(F,x) où F est une File
d’entiers et x est un entier.

6°) On considère une liste doublement chaînée dont les états sont donnés ci-dessous :
6°) -a. Donner la structure de données qui décrit un élément d’une liste doublement chaînée, puis la structure
de données d’une liste L doublement chaînée.
6°) -b. Décrire les différents états (a) ; (b) et (c) en se basant sur les opérations d’ensembles dynamiques
appropriées.

2
6°) -c. Ecrire les algorithmes qui réalisent les opérations de LISTE-INSERER(L, x) qui insère l’élément x dans
la liste L (comme décrit en (b)) ; RECHERCHER-LISTE (L, k) qui recherche un élément de clé donné k dans
la liste chaînée L ; LISTE-SUPPRIMER(L, k) qui supprime une occurrence d’élément de clé k dans la liste
chaînée L. Donner la complexité de chacun de vos algorithmes.

6°) -d. Donner la structure d’une liste simplement chaînée ainsi que les équivalents d’opérations précédentes sur
cette structure.
7°) Ecrire les opérations d’ensembles dynamiques de Pile implémentée à l’aide d’une liste chaînée.
8°) Ecrire les opérations d’ensembles dynamiques de File implémentée à l’aide d’une liste chaînée.

Exercice 2.
Ecrire un algorithme qui détermine tous les diviseurs positifs d’un nombre entier saisi. Ces diviseurs doivent
être rangés dans une liste chaînée.

Exercice 3.
1.) Ecrire un algorithme qui multiplie deux entiers positifs a et b selon le principe récursif suivant :

2.) Ecrire un algorithme qui lit deux entiers a et b à partir du clavier, et affiche leur produit selon l’algorithme
itératif ci-dessus selon l’exemple associé.

Exercice 4.
Ecrire un algorithme dans lequel vous déclarerez et initialiserez un tableau d’entiers Tab avec des valeurs, dont
certaines seront nulles. L’algorithme devra parcourir le tableau et imprimer les index des éléments nuls du
tableau.

Exercice 5.
1.) Déclarer un tableau iNb_jours qui doit être initialisé de façon à ce que iNb_jours[i] soit égal au nombre de
jours du ième mois de l’année, pour i allant de 1 à 12 ( iNb_jours[0] sera inutilisé).

3
2.) Ecrire une procédure d’initialisation de iNb_jours qui utilisera le principe suivant :
• Si i vaut 2, le nombre de jours est de 28,
• Sinon, si i est pair et i <= 7 ou i est impair et i > 7 alors le nombre de jours est 30,
• Sinon le nombre de jours est de 31.
3.) Ecrire une procédure d’impression des 12 valeurs utiles de iNb_jours.

Exercice 6.
Dans un supermarché un produit est caractérisé par son code à barre (50 chiffres), son nom (20 caractères) et son
prix. Un caissier caractérisé par son identifiant (30 caractères) son nom (20 caractères) et l’ensemble des produits
vendus pendant la journée (tableau de 100 produits) doit enregistrer les produits achetés par les clients et indiquer
le solde de sa caisse à la fin de la journée.
On vous propose la structure suivante décrivant un Caissier :
Type Caissier = Structure
id : Tableau[1..30] de caractère ;
nom : Tableau[1..20] de caractère ;
produits : Tableau[1..100] de Produit ;
nbProduit : Integer ;
soldeCaisse : Integer ;
FinStructure ;
1. Définir la structure de données « Produit » qui est utilisée dans la définition de la structure d’un
Caissier.
2. Ecrire une fonction SoldeCaisse qui retourne le solde final de la caisse à la fin d’une journée (la somme des
prix des produits vendus par le caissier)
3. Ecrire une fonction PlusChere qui retourne le produit le plus chère vendue par le caissier.
4. Ecrire une fonction ChercherProduit permettant de vérifier est ce qu’un produit a été vendu ou non par le
caissier. (Recherche suivant le code à barre du produit).
5. Dans le supermarché il existe 10 caissiers, écrire une fonction MeilleurCaissier permettant de retourner le
caissier qui a marqué le plus grand montant de la caisse à la fin de la journée.

Exercice 7.
Le problème de la sélection consiste à trouver dans un tableau de nombres l’élément dit de rang i.
Pour cet exercice, du fait que les indices d’un tableau T sont compris entre 0 et longueur(T)-1, nous admettrons
que l’élément de rang 0 est le plus petit l’élément du tableau, et que l’élément de rang longueur(T)-1 est le plus
grand.
Exemple : Soit T = [8, 6, 53, 8, 2, 9, 3, 10], alors :

• Les éléments de rang < 0 sont indéfinis ;

• L’élément de rang 0 est 2 ;
• L’élément de rang 1 est 3 ;
• L’élément de rang 2 est 6 ;
• L’élément de rang 3 est 8 ;
• L’élément de rang 4 est 8 ;

4
• L’élément de rang 5 est 9 ;
• L’élément de rang 6 est 10 ;
• L’élément de rang 7 est 53 ;
• Les éléments de rang > 7 sont indéfinis ;

Remarque 1 : Une solution simple au problème de la sélection consiste à utiliser un algorithme quelconque de
tri, puis de retourner l’élément de rang souhaité.

Remarque 2 : Il est facile de se persuader qu’il n’est pas utile de trier tout le tableau pour avoir une solution au
problème de la sélection. Dans cet exercice, nous allons adapter des algorithmes de tri vus en cours afin
d’obtenir des algorithmes de rang plus efficaces que le précédent.
1./ Ecrire une procédure Echange(T, i, j) qui échange les valeurs du tableau T indicées par i et j.
2./ Le tri par sélection est l’un des algorithmes de tri permettant de réaliser l’opération Trier(T) appelée à
l’avant dernière ligne de l’algorithme précédent. Donner son principe de fonctionnement puis écrire
l’algorithme triSelection(T) correspondant.
3./ Il semble évident qu’une fois la valeur désirée bien placée dans le tableau, il est inutile de continuer le tri.
a. Ecrire un algorithme rangSelection(T, r) en s’inspirant fortement de l’algorithme triSelection(T) qui
résout le problème de la sélection. Ne pas oublier de s’assurer que le rang désiré correspond à un indice
du tableau.
b. Etablir la complexité temporelle dans le pire des cas de chacun des deux algorithmes triSelection(T) et
rangSelection(T, r) que vous venez de proposer. N.B : le paramètre r passé à l’algorithme renvoie au
rang désiré dans le tableau.

4./ Une autre solution pour réaliser l’opération Trier(T) utilise le tri bulle dont l’algorithme est donné ci-
dessous :
Il semble évident aussi qu’une fois la valeur désirée bien
placée dans le tableau, il est inutile de continuer le tri.
a. Ecrire un algorithme rangBulle(T, r) fortement inspiré
de l’algorithme triBulle(T) qui résout le problème de
la sélection. Ne pas oublier de s’assurer que le rang
désiré correspond à un indice du tableau.
b. Quelle est la complexité temporelle de chacun des deux
algorithmes rangBulle(T, r) et triBulle(T) ?
c. Ecrire le programme C correspondant à l’algorithme
rangBulle(T, r) que vous venez de proposer.

5
Exercice 8.
Ecrire un algorithme comportant :
1. La déclaration de trois variables globales entières iHeures, iMinutes, iSecondes.
2. Une procédure afficheHeure qui imprimera le message suivant : Il est … heure(s) … minute(s) …
seconde(s) en respectant l’orthographe du singulier et du pluriel.
3. Une procédure saisirHeure qui admettra trois paramètres entiers iH, iM et iS, dont elle affecte les
valeurs respectivement à iHeures, iMinutes et iSecondes.
4. Une procédure tick qui incrémentera l’heure d’une seconde.
5. La procédure main sera un jeu d’essais des procédure précédentes.

Exercice 9.
Déclarer et initialiser deux tableaux de caractères (cTab1 et cTab2). Puis :
1. Ecrire une fonction longueurChaine1 qui admette en paramètre un tableau de caractères se terminant
par un NIL, et qui rende le nombre de caractères du tableau (NIL exclu).
2. Ecrire une fonction longueurChaine2 qui implant la même interface que longueurChaine1, mais en
donnant à son paramètre le type de pointeur vers un char.
3. La procédure main imprimera le nombre d’éléments de cTab1 et cTab2 par un appel de
longueurChaine1 et longueurChaine2.

Exercice 10.
Ecrire un algorithme qui prend en paramètres deux tableaux A[n] et B[n] et contenant la représentation binaire
sur n bits d’un nombre entier chacun, l’algorithme doit calculer la somme des deux entiers en binaire et ranger
le résultat binaire dans un tableau C[n+1] de taille n+1.
Analyser la complexité de votre algorithme.