Questions de cours

Contrôle continu 2008-2009 Pointeurs - Récursivité - Listes Questions de cours (4 points) • Soit une liste de taille n. Quelle est l’occupation en mémoire d’une liste doublement chainée ? Si p est la taille d’un curseur et t la taille de l’information à stocker (2*p+t)*n, complexité O(n). • Quelle est la différence entre le type « pointeur » et le type « curseur » ? Un pointeur contient une adresse mémoire qui permettra d’accéder à un objet. Un curseur est un objet qui permet d’accéder à un objet. Un curseur peut être de type pointeur mais peut aussi être de type entier (index dans un tableau) • Dessinez la mémoire, après la suite d’opérations suivante : var p : ^tableau[1..6] de ^entier ; var c :^entier ; var i :entier ; new(p) ; pour i=1 à 6 par pas de 2 faire new(p^[i]) ; p^^[i]=i ; finpour L’instruction p^^[i]=i n’a pas de sens car c’est p^ qui est un tableau et pas p^^ ! Dans ce contexte, quel est le problème de la séquence suivante ? var I: entier ; I=p^[2]^ Cette instruction accède au 2ième élément du tableau pointé par p mais celui-ci est à NIL, donc il n’y a pas d’’entier associé à cette cellule. Exercice 1 (4 points) Soit la fonction fonction compte(ref T:tableau[1..NMAX] d’entier,val clé :entier) : entier ; var p,tmp :entier ; début tmp=0 ; pour p allant de 1 à NMAX faire si T[p]<=clé alors tmp=tmp+1 ; finsi ; ...