[PDF] Examen dalgorithmique - IRIF PDF partiel-1516.pdf

Exercice 4 : Listes chaˆınées - 6 points On consid`ere des listes chaınées d' entiers Chaque cellule de la liste aura deux champs : un champ val pour stocker

07-**- Procédure de suppression d'un élément d'une liste chaînée à une position DVD-MIAGE Corrigés Algorithmique Exercices ch 9, 10 et 11 Page 5/20

[PDF] Examen dalgorithmique - IRIF

Exercice 4 : Listes chaˆınées - 6 points On consid`ere des listes chaınées d' entiers Chaque cellule de la liste aura deux champs : un champ val pour stocker

[PDF] Algorithmes et structures de données : TD 8 Corrigé - LaBRI

Algorithmes et structures de données : TD 8 Corrigé Tableaux dynamiques - Listes linéaires simplement chaınées - Complexité asymptotique Rappel :

[PDF] Solutionnaire pour les exercices sur les listes chaînées et les files

Voici une méthode pour insérer un élément au début d'une liste simplement chaînée On garde le pointeur de la Tête dans un pointeur temporaire On fait

[PDF] TD n 9 - Correction

TD n◦9 - Correction Listes Une liste est une structure permettant de stocker des éléments, un peu `a la mani`ere d' Exercice 1 Listes simplement chainées

[PDF] Listes chainées 1 Exercice 1

Corrigé type série 4- Listes chainées 1 Exercice 1 : Type P = ^Elem ; Elem = Enregistrement Info : Caractere ; Suiv: P Fin; Ecrire des sous algorithmes

[PDF] Examen - UPMC

I - Première partie : listes chaînées de personnes Nous allons considérer deux structures imbriquées : * une structure de données struct date, de type synonyme

[PDF] TD 3 et 4 Listes - IGM

Dans ce TD, nous manipulerons uniquement des listes d'entiers (V = N) 1 Listes chaînées La liste chaînée est une structure de données que l'on retrouve

Universite Paris Diderot L2 Informatique Annee 2015{2016

Examen d'algorithmique

Samedi 17 octobre 2015 9h{11h / Aucun document autoriseMode d'emploi :Le bareme est donne a titre indicatif.La qualite de la redaction

des algorithmes et des explications sera tres fortement prise en compte pour

la note.On peut toujours supposer une question resolue et passer a la suite.Exercice 1 : Derouler un algorithme iteratif (3 points)

On considere l'algorithme ci-dessous :Def P(entier x) : tant que x != 1 faire:

Afficher x

Si x est pair Alors: x = x/2

Sinon: x = 3*x+11.D ecrirece que fait l'algorithme Pappele avec le parametre 3. 2. D ecrirece que fait l'algorithme Pappele avec le parametre 22. Exercice 2 : Derouler un algorithme recursif (4 points) On considere l'algorithme ci-dessous :Def P(tableau T, entiers: bg , bd) :

Si (bg==bd) Alors :

a1 = T[bg] a2 = T[bg]

Sinon :

m = (bg+bd)/2 (x1,y1) = P(T,bg,m) (x2,y2) = P(T,m+1,bd)

Si x1
Sinon: a1 = x2

Si y1>y2 Alors: a2 = y1

Sinon: a2 = y2
Retourner (a1,a2)1.Appliq uerl'algorithme sur le tableau [3,6,2,10,67,34]avecbg=0etbd=5(on suppose que le premier indice du tableau est 0). On precisera tous les appels recursifs eectues et leurs resultats. 2. Que fait l'algorithme P(T,0,n-1)pour un tableau de taillen? 1/2 Universite Paris Diderot L2 Informatique Annee 2015{2016
Exercice 3 : Recherche dichotomique - 4 points
Ecrire un algorithmeiteratifde recherche dichotomique d'un entierxdans un tableau (d'entiers)Ttrie dans l'ordre croissant. L'algorithme retournera l'indice dexdansTsi il est present, et -1 sinon.
Exercice 4 : Listes cha^nees - 6 points
On considere des listes cha^nees d'entiers. Chaque cellule de la liste aura deux champs : un champvalpour stocker une valeur entiere, et un champsuivpour stocker l'adresse de la cellule suivante. Une liste est alors l'adresse de la premiere cellule (et 0 si c'est la liste vide). On utilisera les primitives classiques :Alloc()pour allouer de la memoire pour y stocker une cellule (cette fonction retourne l'adresse de la zone memoire choisie), etc->valetc->suivpour acceder aux champs a une adressec,... On s'interesse ici aux listes triees dans l'ordre croissant : on sait donc que le premier element de la liste est le plus petit, le second est le deuxieme plus petit,etc.
Par exemple, la liste suivante est correcte :1.Donn erun algorithme Test(entier x, liste L)qui renvoie vrai si il existe une
cellule dansLcontenant la valeurx, et faux sinon. 2. Donn erun algorithme Ajouter(entier x, liste L)qui ajoute une cellule (au bon endroit pour que la liste reste triee) dansL, et qui renvoie la nouvelle liste (c-a-d. l'adresse de la premiere cellule de la liste). 3. Etan tdonn eun tableau d 'entiersTcontenantnvaleurs entieres, donner un algo- rithme qui construit une liste cha^nee triee avec toutes les valeurs deT. 4. P arrapp ortau tri par insertion dans un tableau, quel est l'in ter^etd'utiliser une liste cha^nee?
Exercice (3 points)Vous avez 12 pieces, toutes de m^eme poids exceptee une qui est legerement plus lourde
que les autres. Trouver la piece "lourde" en 3 pesees seulement. M^eme probleme avec 27 pieces. 2/2quotesdbs_dbs2.pdfusesText_2

[PDF] [PDF] Examen dalgorithmique - IRIF

[PDF] Exercices des chapitres 9, 10 et 11 Sommaire - MIAGE de Nantes