Exams résumé de langage c PDF

Preview

Summary

langage c ...

Description

Exams langage c Exercice1 Soit la fonction suivante: Void traite(int t[N]) { int min, temp; for (int i =0; i < N-1; i++) {min = i; for (int j = i+1; j < N; j++) if (t[j] < t[min]) min = j; temp = t[i]; t[i] = t[min]; t[min] = temp; } } Donner en fonction de N, le nombre de comparaisons effectuées par cette fonction. Exercice2 Soit la déclaration suivante: typedef struct anneau { int valeur; struct anneau *precedent; struct anneau *suivant; } Anneau ; 1. Ecrire une fonction qui fait l'insertion d'une valeur entière X au début d'une liste doublement chainée. 2. Ecrire une fonction qui supprime l'anneau situé au début d'une liste doublement chainée et renvoie la valeur qui y était contenue. 3. Ecrire la fonction qui effectue l'insertion de X dans la liste supposée triée par ordre croissant de façon à garder l'ordre. (L'insertion n'autorise pas les répétitions)

Bonne chance Problème : lire chaque question attentivement On se propose d'écrire une application qui permet de supprimer toutes les lignes vides d'un fichier texte en utilisant une liste simplement chaînée.

Utilisez les déclarations globales suivantes : typedef struct maillon { char ligne[80]; struct maillon *suivant; }listeligne; FILE *fichier; char nomf[20]; //pour le nom physique du fichier listeligne *tete; 1. Ecrire une fonction void creer_liste() qui permet de créer la liste chaînée tete et d'y mettre les lignes qui ne sont pas vides du fichier texte déjà existant NB. Chaque ligne du fichier se termine par le caractère de fin de ligne "\n". On suppose qu'une ligne du fichier contient moins que 80 caractères en comptant le caractère "\n" Une ligne vide ne contient qu'un seul caractère qui est le caractère de fin de ligne :"\n" rappelons que : fgets(chaine, lgmax, fichier); lit lgmax-1 caractères (ou les caractères du début jusqu'à fin de ligne "\n") à partir du fichier et les range dans chaine en ajoutant le caractère "\0". 2. Ecrire une fonction void supprime (char *s) qui supprime le premier maillon de tete et met dans s la ligne qui y était contenue. 3. Ecrire une fonction void copie () qui écrase tous les éléments du fichier texte et y écrit les lignes initialement mises dans tete. Rappelons que : fputs(chaine, fichier); écrit la chaine de caractères chaine à la position courante du pointeur de fichier.(\0 exclu) 4.

Ecrire la fonction main qui réalise l'objectif souhaité. Bonne chance

Examen de Rattrapage Module I311 Documents non autorisés - Durée : Exercice1: Soient les deux fonctions de tri suivantes: void tri1(int t[], int N) { for(int i =0; i < N-1; i++) { int k = i; for (int j = i+1; j < N; j++) if (t[j] < t[k]) k = j; int temp =t[k] t[k]=t[i]; t[i] = temp; } } void tri2(int t[], int N) { for( int i=1; i < N; i++) { int j = i ; int a = t[i]; while (j > 0 et t[j-1]> a) { t[j] = t[j-1]; j = j-1; } t[j] = a; } } 1. 2. 10

Quelles sont les deux méthodes utilisées? Exécuter chacune des deux fonctions sur le tableau suivant: 5

8

9

-1

2

3. 4.

Pour chaque exécution, donner le nombre de comparaisons effectuées dans le tableau. Comparer les deux nombres. Comment expliquer ce résultat?

Exercice2 Ecrire un programme qui crée une liste simplement chainée de taille n.(n est un entier) Utiliser les déclarations suivantes : typedef struct maillon cellule; struct maillon { int valeur; struct maillon *suivant; }; cellule *L = NULL; Exercice 3 Soit nomfichier une variable désignant le nom physique d'un fichier qui se trouve sur le disque. Ecrire un programme qui crée le fichier en le remplissant de n entiers.( n est un entier) Exercice4 Soit l'arbre suivant :

Livre

C1 C2 S1.1

S1.2

Afficher les mots inscrits aux nœuds de cet arbre en utilisant les parcours: infixe, prefixe, et postfixe.

Bonne chance

Contrôle N°2 Module I311 - Durée : 1h40mn

Question de cours: Donner le principe du tri bulle ainsi que celui du tri par insertion d'un tableau d'entiers. Rappeler le tri par insertion. Exécuter le sur le tableau suivant : 10

-1

20

3

2

Exercice 1 Gestion d’une liste d'étudiants : Nous voulons gérer un groupe d'étudiants, chaque étudiant étant identifié par le prénom, le nom, note1, note2 et moyenne. Pour cela, nous utilisons une liste chainée avec la déclaration suivante : struct maillon { char nom[20], prenom[20] ; float note1, note2, moyenne ; struct maillon *suivant ; }; typedef struct maillon cellule ; 1 Ecrire la fonction : cellule * dernier(cellule *liste); qui permet de retourner le dernier maillon de la liste. 2 Ecrire la fonction : cellule * recherche(char *nomr, char *prenomr, cellule *liste); qui retourne l'adresse du maillon de nom = nomr et de prenom = prenomr. (on suppose que s'il existe un tel maillon, il est unique) 3 Ecrire la fonction : cellule * ajouter(char *nomr, char *prenomr, float note1, float note2, cellule *liste); qui permet d’ajouter un élément à la fin de la liste. (NB. La fonction doit prévoir le calcul de la moyenne de note1 et note2. Les deux notes ont même coefficient) 4 En supposant que la liste est triée par ordre croissant selon la moyenne, écrire la fonction : cellule * ajout(char *nomr, char *prenomr, float note1, float note2, cellule *liste); qui permet d’ajouter un élément dans la liste à

une position de façon à garder l'ordre. (NB. La fonction doit prévoir le calcul de la moyenne) 5 Ecrire la fonction cellule * precedent(cellule *el, cellule *liste); qui renvoie l'adresse du maillon qui précède el dans la liste. 6 Ecrire la fonction (cellule * supprime(char *nomr, char *prenomr, cellule *liste); qui permet de supprimer l’élément en question de la liste. 7 Ecrire la fonction (void afficher(cellule *liste) ) qui permet d'afficher les informations des étudiants ayant plus que 10 en moyenne.

Exercice 2 Dire ce que définissent les fonctions suivantes : int rec1(int n){ if(n == 0) return 1; else return 2*rec1(n-1); } int rec2(int n){ if(n == 0) return 1; else return (rec2(n-1) + rec2(n-1)); } Dire pour chacune, s'agit-il d'une récursivité terminale ou non terminale. Justifier

Bonne chance

Examen Module I311 Documents non autorisés - Durée : Exercice1 Ecrivez à l'aide d'une liste simplement chaînée les fonctions de gestion d'une pile d'entiers permettant : - d'empiler un élément ; - de dépiler un élément. Ecrivez à l'aide d'une liste simplement chaînée les fonctions de gestion d'une file d'entiers permettant : - d'ajouter un élément dans la file ; - d'extraire un élément de la file. Exercice2 Pour la gestion d'une bibliothèque, on dispose de deux fichiers binaires: ouvrages et adhérents. Pour chaque ouvrage, on précise son code (un entier positif unique non nul), le titre de l'ouvrage et le nom de l'auteur. Pour tout adhérent, on précise son matricule (un entier positif unique), son nom et le code de l'ouvrage emprunté. (Un adhérent ne peut emprunter qu'un ouvrage à la fois). Si l'usager n'a emprunté aucun ouvrage, ce code sera égal à 0. Utiliser les structures suivantes : struct ouvrage { int code; char titre_ouvrage[20]; char auteur[20]; }; struct adherent{ int matricule; char nom[20]; int cod_emp; }; Et les déclarations suivantes : FILE *fouvr, *fadh; 1/ Ecrire une fonction en langage C void affiche_adh() qui affiche la liste des adhérents (matricule nom cod_emp). 2/ Ecrire une fonction en langage C void affiche_ouv() qui affiche la liste des ouvrages (code titre auteur).

3/ Ecrire une fonction en langage C qui renvoie une liste simplement chainée constituée des codes des ouvrages empruntés. (Nommez cette fonction codes_empruntés) 4/ Ecrire une fonction en langage C int recherche_adhe (int matricule) qui recherche un matricule donné dans le fichier des adhérents (renvoie 1 en cas d'existence du matricule et 0 sinon). 5/ Ecrire une fonction en langage C char * recherche_ouvrage (int code) qui recherche un code donné dans le fichier des ouvrages. La fonction renvoie le titre de l'ouvrage recherché si la recherche est fructueuse et NULL sinon. 6/ Ecrire une fonction en langage C void emprunt() qui vérifie si un usager de matricule donné peut emprunter un ouvrage. La fonction doit faire le traitement suivant :  Lire le matricule  Si le matricule ne correspond à aucun usager, la fonction doit afficher matricule inexistant.  Sinon, si l'usager n'a pas rendu le dernier ouvrage qu'il a emprunté, la fonction doit afficher emprunt impossible.  Sinon, lire le code de l'ouvrage à emprunter. Si le code introduit ne correspond à aucun ouvrage, la fonction doit afficher code inexistant.  Sinon la fonction doit afficher emprunt possible. 7/ Ecrire une fonction en langage C void affich_emp() qui affiche les codes et les titres des ouvrages empruntés (Utilisez la fonction de 3/). (NB. Les deux fichiers sont déjà créés, dans toutes les fonctions ci-dessus l'ouverture d'un fichier se fait en mode lecture) Exercice3 Calculer la complexité de la fonction : int rec(int n){ if(n == 0) return 1; else return 2*rec(n-1); } Bonne chance

Examen de Rattrapage Module I311 Documents non autorisés - Durée :

Exercice1: Ecrivez un programme qui lit une suite de nombres à la console et crée la liste chaînée correspondante, dans les deux cas suivants : La position des nombres est sans importance dans la liste La liste doit traduire l'ordre de lecture des nombres

Exercice2: Ecrivez une fonction qui, étant donnés un tableau T de N nombres entiers et un nombre entier x, cherche et renvoi le plus petit rang i tel que T[i] = x. (si x ne se trouve pas dans le tableau la fonction doit renvoyer -1) Ecrivez une fonction qui, étant donnée une liste chainée L de nombres entiers et un nombre entier x, cherche et renvoie l'adresse du premier maillon contenant x. (si x ne se trouve pas dans le tableau la fonction doit renvoyer NULL)

Exercice3: On veut représenter un agenda téléphonique: 1) sous forme d’un tableau composé pour chaque enregistrement d’un prénom, nom et numéro de téléphone.  Définir la structure de donnée à employer pour représenter l’agenda.  Ecrire la fonction qui permet la saisie d'un certain nombre de personnes dans l’agenda 2) Sous forme d’une liste chainée: pour chaque maillon, la donnée est composée d'un prénom, nom et numéro de téléphone.  Définir la structure de données employée pour représenter l’agenda.

 Ecrire la fonction qui permet la saisie d'un certain nombre de personnes dans l’agenda 3) Dans un fichier d'enregistrements tel que chaque enregistrement est composé d’un prénom, nom et numéro de téléphone.  Définir la structure de fichier  Ecrire la fonction qui permet de créer le fichier par la saisie d'un certain nombre de personnes (Rq. ce nombre peut être égal à 1)

Bonne chance

Examen de Rattrapage Module I311 Documents non autorisés - Durée :

Exercice1 Donnez la structure employée pour les cinq fonctions ci-dessous. Ecrivez une fonction qui insère en tête d'une liste simplement chaînée l un caractère c. Ecrivez une fonction qui renvoie le nombre de fois qu'apparaît le caractère '2' dans une liste simplement chaînée l. Ecrivez une fonction qui supprime le premier maillon contenant le caractère '2' d'une liste simplement chaînée l. Ecrivez une fonction qui supprime tous les maillons contenant le caractère '2' d'une liste simplement chaînée l. Ecrivez une fonction qui ne garde dans une liste simplement chaînée que les caractères qui sont des alphabets.

Exercice 2 Un polynôme P(x) est représenté par la suite (a0 a1 a2 … an) de ses coefficients. Ecrivez le programme qui calcule la valeur de P(x) pour une valeur donnée de x. Pour cela, définissez dans le programme une fonction qui fait la saisie des coefficients dans une liste simplement chaînée.

Bonne chance

Contrôle N°2 Module I311 - Durée : 1h50mn Exercice 1 Un polynôme P(x) est représenté par la suite (a0 a1 a2 … an) de ses coefficients. 1. Ecrire une fonction en C void lecturecoef(float a[], int n); qui demande à l'utilisateur de rentrer les valeurs des coefficients du polynôme et qui les lit. 2. Ecrire une fonction en C float poly(float a[],int n, float x); qui calcule la valeur de p(x) en calculant les termes akxk et en les additionnant. Vous devez tenir compte dans la définition de cette fonction du fait que quand on calcule xk, on a déjà calculé xk-1et que xk = x * xk-1. 3. calculer la complexité de la fonction poly en nombre d'additions et de multiplications effectuées. 4. Reprenez les questions: 1 et 2 avec la représentation du polynôme à l'aide d'une liste simplement chainée. Pour cela, utilisez la structure suivante : struct maillon { float c; struct maillon *suivant; }; Utilisez les prototypes de fonctions suivants : struct maillon *lecturecoef(); float poly(struct maillon *a, float x); Exercice 2 Soit la structure suivante : struct ouvrage { char titre[20]; char auteur[20]; struct ouvrage *suivant; }; 1. Ecrire une fonction en C struct ouvrage *insere(char *nom_titre, char *nom_auteur, struct ouvrage * liste); qui insère en tête d'une liste simplement chainée d'ouvrages liste un ouvrage.

Bonne chance

2. Ecrire une fonction en C struct ouvrage *supprime(char *nom_auteur, struct ouvrage * liste); qui supprime de la liste simplement chainée tous les maillons contenant les ouvrages d'un auteur donné. 3. Ecrire une fonction en C struct ouvrage *inserer(char *nom_titre, char *nom_auteur, struct ouvrage * liste); qui insère, dans une liste simplement chainée d'ouvrages supposée ordonnée par ordre croissant selon le nom d'auteur, un ouvrage de façon à garder l'ordre. Exercice 3(non fait) Soit la fonction suivante: fonction recherche(t:tableau d'entiers, i,j,x:entiers):booléen

variables m : entier; Debut si (i > j ) alors retourner faux; sinon{ m ¬ (i + j ) / 2; si t[m] = x alors retourner vrai sinon si t[m] < x alors retourner recherche(t, m+1, j, x) sinon retourner recherche(t, i, m-1, x) } Fin. A l'appel recherche(T, 0, n-1, x) où T est un tableau d'entiers de taille n (supposé trié) et x un entier quelconque: 1. quel est le résultat de l'appel? 2. Calculer sa complexité dans le pire cas (indication : calculer le nombre d'appels récursifs en fonction de n)

Bonne chance

Examen Module I311 - Durée :2heures Documents non autorisés Questions de cours:(5 points) Citez un algorithme en O(n) Citez un algorithme en O(n2) Citez un algorithme en O(n3) Citez un algorithme en O(log(n)) Citez un algorithme en O(2n) Si un algorithme en O(n3) met T secondes pour n données, combien de secondes met-il pour 10n données? Donner la définition d'un arbre binaire de recherche. Donner le principe du tribull Donner le principe du tri rapide Exercice :(4 points) 1. Définissez une file d'enregistrements ayant la structure CD définie ci-

dessous (voir problème). 2. écrivez les fonctions de gestion permettant :  d'ajouter un élément dans la file ;  de supprimer un élément de la file. Les deux questions doivent être traitées en utilisant une représentation à l'aide d'un tableau (configuration circulaire) et une représentation chaînée. Problème :(11 points) On voudrait gérer les albums d'une CD-thèque. Pour cela, on dispose pour chaque CD du nom du groupe, du nom de l'album et de l'année de sortie de l'album (pour ce problème, on considérera qu'aucun groupe n'a sorti plus d'un cd par année). On définit la structure CD: typedef struct { char groupe[20]; char album[50]; int annee; }CD; Bonne chance

Soit la fonction int superieur(CD cd1, CD cd2) qui dit si cd1 est plus grand que cd2 d'après l'ordre alphabétique des groupes puis selon l'année de sortie de l'album. Exemple: cd1 Beatles cd2 Beatles cd3 Dandy Warhols

Sgt Pepper's Lonely heart's Club Band Abbey Road Odditorium or the warlords of Mars

1967 1969 2005

superieur (cd1, cd2) renvoie 0 car le groupe est identique et Sgt… est sorti avant Abbey Road. superieur (cd3, cd2) renvoie 1 car dans l'ordre alphabétique "Dandy Warhols" vient après "Beatles".

1. Ecrivez la fonction int superieur(CD cd1, CD cd2); 2. Ecrivez une fonction void echange(CD *A, CD *B); qui échange les valeurs de deux variables de type CD. 3. Ecrivez une fonction void trie(CD *t , int n); qui trie en utilisant le principe du tri par insertion un tableau de n CDs par ordre croissant d'après l'ordre alphabétique des groupes puis selon l'année de sortie de l'album. (il n'est pas demandé ici de créer le tableau) 4. Ecrivez une fonction void cree(); qui stocke une liste de CDs dans un fichier binaire nommé "CDtheque". 5. Ecrivez une fonction void trie(); qui trie par ordre croissant le fichier "CDtheque". 6. Supposons que le fichier "CDtheque" est assez gros pour être copié dans un tableau, proposez une méthode pour le trier.

Bonne chance

Examen de Rattrapage Module I311 Documents non autorisés - Durée :

Exercice1 1/Ecrire l'algorithme du tri par insertion. 2/Exécuter le sur le tableau suivant : 7

-3

12

5

1

3/Calculer le nombre d'échanges effectués dans ce cas. 4/Calculer le nombre d'échanges effectués dans le pire cas en fonction de n : taille du tableau Exercice2 On voudrait gérer l'ensemble de microordinateurs d'un centre de calcul. Pour chaque micro-ordinateur, on précise: Sa marque (chaîne de 30 caractères) Son numéro de série (un nombre entier strictement positif). Ce numéro est unique pour chaque marque. Le numéro de salle où se trouve l'ordinateur (un nombre strictement positif compris entre 1 et 10). Pour cela déclarons la structure suivante: typedef struct { char marque[30]; int serie; int numero; }MICRO;

1. Ecrire une fonction en C cree(MICRO *T, int n) qui fait la saisie de n

micro-ordinateurs dans un tableau T. Bonne chance

2. Ecrire une fonction en C qui fait la saisie d'un certain nombre de micro-

ordinateurs dans un fichier binaire nommé "centre". 3. Ecrire une fonction en C qui affiche toutes les informations contenues

dans le fichier "centre".

4. Ecrire une fonction en C : cellule* copie () qui copie les informations

contenues dans le fichier "centre" dans une liste simplement chainée. (la structure cellule doit être définie au préalable) 5. Ecrire une fonction en C : cellule* recherche (int ns, cellule *l) qui

renvoie l'adresse du maillon, relatif au micro-ordinateur de numéro de série ns, d'une liste simplement chainée l.

6. Ecrire une fonction en C : void affiche_serie (char * marque, int

numsalle, cellule *l) qui affiche les numéros de série des microordinateurs, d'une liste simplement chainée l, ayant une marque donnée et se trouvant dans une salle donnée.

Bonne chance

Bonne chance

EXAMEN de TUTORAT - Module I311 Documents non autorisés - Durée :1h10mn Exercice1 float calcul (float a[], int n, float x){ int i; p = a[n]; for (i = n-1; i>=0; i--) p = p * x + a[i]; return p; } 1/ que fait la fonction ci-dessus? On suppose que le tableau a représente un polynôme. 2/ analyser sa complexité Exercice2 On voudrait gérer l'ensemble de microordinateurs d'un centre de calcul. Pour chaque micro-ordinateur, on précise: Sa marque (chaîne de 30 caractères) Son numéro de série (un entier >0 unique pour chaque marque). Le numéro de salle où se trouve l'ordinateur (un entier compris entre 1 et 10). Pour cela déclarons la structure suivante: typedef struct { char marque[30]; int serie; int numero; }MICRO; 1. Ecrire une fonction en C void cree(MICRO *T, int n) ; qui fait la saisie de n microordinateurs dans un tableau T. 2. Ecrire une fonction en C void saisie (char *nomfich) ; qui fait la saisie d'un certain nombre de micro-ordinateurs dans un fichier binaire portant le nom nomfich. 3. Ecrire une fonction en C void affiche (int ns, char *nomfich) ; qui affiche la marque ainsi que le numéro de salle où se trouve les micro, enregistrés dans le fichier nomfich, de numéro de série ns. 4. Ecrire une fonction en C cellule* copie (...