Examen corrige

Université Africaine d'Adrar
Faculté des Sciences et Sciences de l'Ingénieur
Département des Mathématiques et de l'Informatique Janvier
2008
2ème Année Informatique
Module : Algorithmiques et Structures de Données 1

Examen Final

Partie I : Vrai ou Faux (7.5 points)
- La réponse par plus de 5 Vrai ou 5 Faux successifs vaut « un zéro » pour
toute la partie.
- Les complexités requises dans les questions ci-dessous sont considérées
toujours dans le pire des cas.
1. L'allocation mémoire d'un tableau est statique dans la plupart des
langages de programmation.
2. La représentation en mémoire d'un tableau multidimensionnel est
monodimensionnelle.
3. Dans le langage C, la primitive malloc() sert à ajouter un élément une
liste chaînée.
4. Dans le langage C, on utilise la valeur de NULL pour rendre une liste
chaînée vide.
5. La pile est une liste chaînée où on insert/retire un élément depuis le
sommet.
6. La file utilise obligatoirement deux pointeurs tete et queue pour
qu'on puisse insérer ou retirer des éléments.
7. La complexité d'insertion ou de suppression dans une pile/file est
((1).
8. Selon l'implémentation, La complexité de vider une pile/file de n
éléments est de ((1).
9. La complexité pour calculer la taille d'une pile/file de n éléments
est ((n).
10. La complexité de recherche d'un élément dans une pile/file de n
éléments est ((lg n).
11. Si la fonction CAR est appliquée sur la liste (A (B C) (D (E F))), on
reçoit la liste (A).
12. Si la fonction CDR est appliquée sur la liste (A (B C) (D (E F))), on
reçoit la liste ((B C) (D (E F))).
13. La collision entre les clés est un inconvénient majeur pour le hachage
par division.
14. Afin de résoudre le problème de collision, on utilise une fonction
bijective dans l'adressage fermé.
15. L'adressage ouvert essaie d'assurer la distribution des clés sur la
table de hachage.
16. Dans l'adressage quadratique, le nombre possible des cellules pour
stocker une clé égale (au moins) à la moitié des cellules existantes.
17. Le parcours pré-ordre d'un arbre binaire de recherche nous affiche une
liste triée par ordre décroissant.
18. Le parcours en-ordre d'un arbre binaire de recherche nous affiche une
liste triée par ordre croissant.
19. Le parcours post-ordre d'un arbre binaire de recherche nous affiche
une liste non triée (en général).
20. La complexité d'insertion dans un arbre binaire de recherche de n
éléments est O(lg n).
21. La complexité de suppression dans un arbre binaire de recherche de n
éléments est O(n).
22. La hauteur d'un arbre binaire de recherche de n éléments égale à
[pic].
23. La complexité de rééquilibrage, après une insertion, dans un arbre AVL
de n éléments est O(n).
24. La complexité de rééquilibrage, après une insertion, dans un arbre BB
de n éléments est O(lg n).
25. La complexité de rééquilibrage, après une insertion, dans un arbre
bicolore de n éléments est ((1).
26. L'invariant de boucle doit être valide avant l'exécution de la boucle.
27. La phase de terminaison ne fait pas partie de la démonstration de la
validité de l'invariant.
28. La complexité de l'algorithme tri par tas de n éléments est O(2 n lg
n).
29. La complexité de l'algorithme tri bulle d'une liste triée (en ordre
croissant) de n éléments est ((n).
30. La complexité de l'algorithme tri par sélection d'une liste triée (en
ordre décroissant) de n éléments est O(n2).
Partie II : (12.5 points)

Exercice 1 : Hachage (3 points)
On désire de stocker des entiers en utilisant le mode adressage ouvert
quadratique, où hi(k) = ( k + i2) mod m.
1. Pour m = 7, citez toutes les différentes permutations hi(k) pour la
clé k = 8.
2. Insérer les entiers suivants dans un tableau de 7 cellules : 8, 10,
15, 18, 19, 25, 31.

Exercice 2 : Arbres (4,5 points)
Insérer la liste [1, 2, 3, 4, 5, 6, 7] dans un arbre AVL, un arbre
BB et un arbre bicolore. Elaborer, en détails, les étapes d'insertion
pour chaque arbre.

Exercice 3 : Complexité (3 points)
Soit la fonction H suivante :
H(a, b : Entier)
Debut
Si a = b Alors Ecrire(a)
Sinon Si a > b Alors
Debut
H(a, a + (b - a)/3)
H(a + (b - a)/3 + 1, a + 2*(b - a)/3)
H(a + 2*(b - a)/3 + 1, b)
Fin
Fin
1- Quelles sont les valeurs affichées à la fin d'exécution de H(1, 6) ?


2- En déduire la complexité (borne approchée) de H(1, n).
3- Trouver (avec démonstration) une borne approchée pour la complexité
de la fonction H(1, n). Conseil : On peut considérer T(n) comme le
temps d'exécution requis pour terminer H(1, n).

Exercice 4 : Exactitude (2 points)
Soit l'algorithme suivant qui calcule le minimum d'un tableau de 10
entiers :
T : Tableau(10) de Entier
i, min : Entier
Debut
Pour i ( 1, 10 Faire
Lire(T[i])
min ( T[1]
Pour i ( 2, 10 Faire
Si min > T[i] Alors min ( T[i]
Ecrire(min)
Fin
- Trouver un invariant de boucle utile, et démontrer l'exactitude de
cet algorithme.
Bonne Chance !!