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

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

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 

[PDF] examen corrigé maintenance des ordinateurs qcm

[PDF] examen corrigé métrologie

[PDF] examen corrigé programmation système

[PDF] examen corrigé rdp

[PDF] examen corrigé rdp pdf

[PDF] examen corrigé système embarqué

[PDF] examen corrigé theorie de graphe

[PDF] examen corrigé thermodynamique 2

[PDF] examen corrigés sur théorème de convergence dominée

[PDF] examen csdm 2017

[PDF] examen culture d'entreprise pdf

[PDF] examen d'adéquation d'un appareil de levage

[PDF] examen d'algebre s1 smpc pdf

[PDF] examen d'aptitude professionnelle echelle 11

[PDF] examen d'informatique 1 année collège

Universit´e Bordeaux 2 Licence MASS/Scico 5`eme semestre (2006/2007) Algorithmes et structures de donn´ees : TD 8 Corrig´e Tableaux dynamiques - Listes lin´eaires simplement chaˆın´ees - Complexit´e asymptotique

Rappel :

SetLength(tableau, n)est de complexit´e O(n)

SetLength(tableau, 1)est de complexit´e O(1)

New(element)est de complexit´e O(1) quandelementest d"un type de taille fixe Exercice 8.1Listes lin´eaire simplement chaˆın´ee Consid´erer l"algorithme suivant qui cr´ee une liste den´el´ements : {Algorithme 2} type p_t_liste_simple = ^t_liste_simple; t_liste_simple = record cle : integer; suivant : p_t_liste_simple; end; var element : p_t_liste_simple; var temp : p_t_liste_simple; var premier : p_t_liste_simple; var i : integer; d´ebut

New(element);

element^.suivant := NIL; element^.cle := 0; premier := element; temp := element; pour i de 1 `a n-1 faire d´ebut

New(element);

element^.cle := i*i; element^.suivant := NIL; temp^.suivant := element; temp := element; fin fin

1. Quelle est la complexit´e de cet algorithme (notation Grand-O) ?

La complexit´e de cet algorithme est O(n).

2. Ebaucher l"occupation de la m´emoire d"une mani`ere compacte.

3. Ecrire un algorithme qui parcours la liste et affiche laclede chaque ´el´ement `a l"´ecran.

Qu"est-ce qui est affich´e `a l"´ecran ?

temp := premier; while (NOT (temp = NIL)) do begin

WriteLn(temp^.cle);

temp := temp^.suivant; end;

Il est affich´e :

0 1 4

4. Ecrire un algorithme qui rajoute un ´el´ement suppl´ementaire avec la valeur 1000au d´ebut

de la liste (la liste aura n+1 ´el´ements). Quelle est la complexit´e de votre algorithme ? Comparer avec l"exercice pr´ec´edente sur les tableaux dynamiques. La complexit´e de cet algorithme est O(1) compar´e `a O(n) pour les tableaux dynamiques.

New(element);

element^.cle :=1000; element^.suivant := premier; premier := element;

5. Ecrire un algorithme qui rajoute un ´el´ement suppl´ementaire avec la valeur 1000`a la finde

la liste. Quelle est la complexit´e de votre algorithme ? Comparer avec l"exercice pr´ec´edente

sur les tableaux dynamiques. 2 temp := premier;si temp = NIL alors

New(premier);

premier^.cle := 1000; premier^.suivant := NIL; sinon tant que (NOT (temp^.suivant = NIL)) faire temp := temp^.suivant; fin tant que

New(element);

element^.cle := 1000; temp^.suivant := element; element^.suivant := NIL; fin si La complexit´e de cet algorithme est O(n), comme pour les tableaux dy- namiques.

6. Que faut-il rajouter `a l"algorithme 2 pour r´eduire la complexit´e de rajouter un ´el´ement

suppl´ementaire avec la valeur 1000`a la finde la liste ? Ecrivez l"algorithme ! Il faut rajouter un pointeurdernierqui pointe toujours vers le dernier ´el´ement.

On r´eduit ainsi la complexit´e pour rajouter un ´el´ement `a la fin de la liste `a O(1).

var dernier : p_t_liste_simple; d´ebut { .. initialiser : }quotesdbs_dbs2.pdfusesText_3