Bonjour les développeurs , j’espère que vous allez très bien , aujourd'hui , je vais partager avec vous un tp qu'un ami m'a envoyer dernièrement , apparemment , il est conçu a la faculté des science saad dahleb en Algérie , Bonne lecture
Lien vers la correction de ce tp : par ici
Université Saad
Dahleb Blida
Faculté des Sciences
Département
d’Informatique
1ère Epreuve de
Moyenne Durée
« Structures de
Données et Algorithmes »
Février 2010
Exercice 1 (7 pts):
On se propose d’implémenter les algorithmes de recherche auto-adaptative appliqués à une LLC unidirectionnelle.
1 – Rappeler en deux lignes ce
qu’est la recherche auto-adaptative (1pt)
2 – Rappeler les deux méthodes
permettant d’implémenter une technique de recherche auto-adaptative (1 pt)
3 – Nommer les deux idées
permettant d’implémenter la recherche auto-adaptative (idée1 et idée2).
Rappeler alors le constat de Donald Knuth relatif aux deux idées. (1pt)
4 – Ecrire deux fonctions C
distinctes réalisant chacune une des deux idées (une fonction C pour la
première idée et une seconde pour la seconde) appliquée à une LLC
unidirectionnelle. (2pts pour chaque fonction)
Exercice 2 (4pts):
On voudrait écrire une fonction C
« récursive » qui évalue un nombre écrit en binaire. La fonction aura
en entré une chaîne de caractères représentant un nombre binaire et donnera en
sortie l’équivalent décimal. Exemple : la fonction ayant en entrée la
chaîne « 11011 » donnera la valeur 27.
Ecrire la fonction C
« récursive » effectuant ce travail.
Exercice 3 (6pts) :
1 – rappeler le principe du tri
par insertion (1pt)
2 – ce tri s’applique-t-il aux
LLC unidirectionnelles (0,5
pt)? aux LLC bidirectionnelles ? (0,5 pt)
3 – que faudrait-il faire afin
que la fonction C qui effectue le tri s’applique sans aucune modification aussi
bien aux LLC unidirectionnelles qu’aux LLC bidirectionnelles ? (1 pt)
4 – Ecrire une fonction C qui
effectue ce tri et qui soit utilisable pour les deux types de listes
Exercice 4 (3pts) :
On voudrait transformer un nombre
représenté par une chaîne de caractères en un autre nombre qui sera copié dans
la chaîne d’origine de la façon suivante :
Tous les chiffres pairs
deviennent en tête dans leur ordre d’origine et tous les chiffres impairs
seront copiés à la suite des pairs dans leur ordre inverse.
Exemple : 123456 è 246531
Ecrire une fonction C qui
transforme ainsi les chaînes-nombres en utilisant une file et une pile.
(utiliser les fonctions du modèle Pile et File sans les réécrire)
Enregistrer un commentaire