Final

Question 1

∑q^i

Answer 1

s=(q^(n+1)-1) / (q-1)

tip: s=… qs=… s-qs=…

Question 2

Insertion dans une pile ordonnée

Answer 2

Insérer(P,x)
  Si pilevide(P) ou x < P[sommet[P]]
    alors empiler(P,x)
  sinon  y:=depiler(P); insérer(P,x); empiler(P,y)

Question 3

File, vide ? pleine ?

Answer 3

Vide : Tete[F] = Queue[F]

Pleine : Tete[F] = (Queue[F] + 1) % longueur[F]

Question 4

Parcours infixe (dans l’ordre)

Answer 4

Parcours_infixe(x)
  Si x <> nil alors
    Parcours_infixe(gauche[x])
    Imprimer clé[x]
    Parcours_infixe(droit[x])

Question 5

Nombre de noeuds internes (arbre binaire complet de hauteur h)

Answer 5

2^h -1

Question 6

∑i, ∑k.i

Answer 6

∑k.i = k∑ = k.n(n+1)/2

tip: # of terms, 2s=…

Question 7

ABR : Rechercher(x, k)

Answer 7

Si x=nil ou k=cle[x] retourner x
sinon si k < cle[x] alors retourner Rechercher(gauche[x], k)
Sinon retourner Rechercher(droit[x], k)

Question 8

ABR : Minimum(x)

Answer 8

Tant que gauche[x] <> nil x=gauche[x]

Retourner x

Question 9

ABR : Successeur(x)

Answer 9

Si droit[x]<>nil retourner Minimum(droit[x])
y = pere[x]
Tant que y <> nil et x=droit(y)
  x=y; y=pere[y]
Retourner y

Question 10

ABR : Insérer(T,z)

Answer 10

y=nil; x=racine[T]
Tant que x <> nil
  y = x
  si clé[z] < clé[x] x=gauche[x]
  sinon x=droit[x]
pere[z] = y
Si y=nil racine[T] = z
sinon si clé[z] < cle[y] alors gauche[y] = z
sinon droit[y] = z

Question 11

ABR : Suppression

Answer 11

Si aucun fils, supprimer.
Si 1 fils, raccorder.
Si 2 fils, remplacer par le minimum de droit[x] puis supprimer ce minimum

Question 12

H-équilibré

Answer 12

Si pour tout x, |equilibre[x]| <= 1
equilibre(x) = hauteur(droit(x)) - hauteur(gauche(x))
(hauteur(x) = 1, hauteur(nil) = -1

Question 13

ABR : Rotd(A, x)

Answer 13

Si x<>nil et gauche[x]<>nil alors
  y = gauche[x]
  c = droit[y]
  pere[y] = pere[x]
  Si pere[x] <> nil alors
    si x=gauche[pere[x]] alors gauche[pere[x]] = y
    sinon droit[pere[x]] = y
  Sinon racine[A] = y
  droit[y] = x
  pere[x] = y
  gauche[x] = c
  Si c<>nil alors pere[c] = x

Question 14

ABR : enraciner(racine, e)

Answer 14

Si cle[racine] = e alors retourner racine
Si clé[racine] > e alors
  enraciner(gauche[racine], e)
  retourner Rotd(racine)
Si clé[racine] < e alors
  enraciner(droit[racine], e)
  retourner Rotg(racine)
Complexité O(h) = O(n)

Question 15

max(A,B) + C
C - max(A,B)
max(A,B)

Answer 15

= max(A+C, B+C)
= - max(A-C,B-C)
= - min(-A,-B)

Question 16

Rotation gauche-droite

Answer 16

x/y-E/B-z/C-D puis x/z-E/y-D/B-C puis z/y-x/B-C-D-E

Question 17

Propriétés tas

Answer 17

T[1] racine. Fils de T[i] : T[2i] et T[2i+1]
T[i] <= ses fils, père de T[i] = T[i/2]
Arbre binaire parfait de taille n. Si 2*i = n alors i n’a qu’un fils. Tous les éléments i > n/2 sont des feuilles.

Question 18

Tas : entasser(A,i)

Answer 18

Gauche et droit sont des tas.
l = gauche(i)
r = droit(i)
Si l<=taille[A] et A[l] > A[i] alors max = l
sinon max = l
Si r <= taille[A] et A[r] > A[max] alors max = r
Si max ≠ i alors
  échanger(A[i], A[max])
  entasser(A, max)

Question 19

Tas : construire_tas(A)

Answer 19

taille[A] = longueur[A]
Pour i de longueur[A]/2 à 1 faire
entasser(A,i)
Complexité O(n) !

Question 20

Tas : trier_tas(A)

Answer 20

Construire_tas(A)
Pour i de longueur[A] à 2 faire
  échange(A[1], A[i])
  taille[A] = taille[A] - 1
  entasser(A,1)
Complexité O(n.log(n))

Question 21

Tas : extraire_max(A)

Answer 21

Si taille[A] < 1 erreur
max = A[1]
A[1] = A[taille[A]]
taille[A] = taille[A] - 1
entasser(A,1)
Retourner max
Complexité O(log(n))

Question 22

Nb min-max de sommets dans un tas de hauteur h

Answer 22

2^h min, 2^(h+1) -1 max (donc h ~log(n))

Question 23

Tas : insérer_tas(A, cle)

Answer 23

taille[A] = taille[A] + 1
i = taille[A]
Tant que i > 1 et A[Pere[i]] < clé faire
  A[i] = A[pere[i]]
  i = pere[i]
A[i] = clé
Complexité O(log(n))

Question 24

Complexité tri comparatif

Answer 24

O(n.log(n))

Question 25

Tri par insertion

Answer 25

Stable si <=, O(n^2) ou O(n) si trié (par décalage ou permutation, on place chaque élément par comparaison avec les éléments suivants) ``` Tri_insertion(T) n = taille[T] Pour i de 2 à n faire X = T[i]; j = i-1 Tant que j >= 1 et T[j] < X faire T[j+1] = T[j] j = j -1 T[j+1] = X ```

Question 26

Tri par bulles

Answer 26

``` À chaque parcours, plus grand élément mis à sa place, n parcours, O(n^2) ou O(n) si trié Tri_bulle(T) ok = 1 j = taille[T] Tant que OK Ok = 0 Pour i de 1 à j-1 faire Si T[i]>T[i+1] échanger(T[i], T[i+1]); Ok = 1 j = j-1 ```

Question 27

Tri par sélection

Answer 27

à chaque itération on place le minimum au début (O(n^2)) ``` Tri selection(T) Pour i de 1 à taille(T)-1 min = i Pour j allant de i+1 à taille(T) Si T[j] inf t[min] min=j Si min not i échanger(t[i],t[min]) ```

Question 28

Tri rapide

Answer 28

``` O(n^2) mais moyenne O(n.log(n)) Tri_rapide(A,p,r) Si p < r alors Q = partitionner(A,r,p) Tri-rapide(A,p,q) Tri-rapide(A,q+1,r) ``` ``` Partitionner(A,p,r) x=A[p], i=p-1, j=r+1 Tant que vrai faire Répéter j=j-1 jusqu'à A[j]<=x Répéter i=i+1 jusqu'à A[i]>=x Si i inf j échanger(a[i],a[j]) Sinon retourner j ```

Question 29

Tri par dénombrement

Answer 29

O(k) exact, k nombre max (ensemble dénombrable) ``` Tri_denombrement(A,B,k) Pour i = 1 à k faire C[i] = 0 Pour j = 1 à longueur[A] faire C[A[j]] = C[A[j]] + 1 Pour i = 2 à k faire C[i] = C[i] = C[i-1] Pour j = longueur[A] à 1 faire (sinon perte stabilité) B[C[A[j]]] = A[j] C[A[j]] = C[A[j]] -1 ```