Examen corrige
La pile est une liste chaînée où on insert/retire un élément depuis le sommet. La
file utilise obligatoirement deux pointeurs tete et queue pour qu'on puisse ...
part of the document
Université Africaine dAdrar
Faculté des Sciences et Sciences de lIngénieur
Département des Mathématiques et de lInformatique 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.
Lallocation mémoire dun tableau est statique dans la plupart des langages de programmation.
La représentation en mémoire dun tableau multidimensionnel est monodimensionnelle.
Dans le langage C, la primitive malloc() sert à ajouter un élément une liste chaînée.
Dans le langage C, on utilise la valeur de NULL pour rendre une liste chaînée vide.
La pile est une liste chaînée où on insert/retire un élément depuis le sommet.
La file utilise obligatoirement deux pointeurs tete et queue pour quon puisse insérer ou retirer des éléments.
La complexité dinsertion ou de suppression dans une pile/file est ((1).
Selon limplémentation, La complexité de vider une pile/file de n éléments est de ((1).
La complexité pour calculer la taille dune pile/file de n éléments est ((n).
La complexité de recherche dun élément dans une pile/file de n éléments est ((lg n).
Si la fonction CAR est appliquée sur la liste (A (B C) (D (E F))), on reçoit la liste (A).
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))).
La collision entre les clés est un inconvénient majeur pour le hachage par division.
Afin de résoudre le problème de collision, on utilise une fonction bijective dans ladressage fermé.
Ladressage ouvert essaie dassurer la distribution des clés sur la table de hachage.
Dans ladressage quadratique, le nombre possible des cellules pour stocker une clé égale (au moins) à la moitié des cellules existantes.
Le parcours pré-ordre dun arbre binaire de recherche nous affiche une liste triée par ordre décroissant.
Le parcours en-ordre dun arbre binaire de recherche nous affiche une liste triée par ordre croissant.
Le parcours post-ordre dun arbre binaire de recherche nous affiche une liste non triée (en général).
La complexité dinsertion dans un arbre binaire de recherche de n éléments est O(lg n).
La complexité de suppression dans un arbre binaire de recherche de n éléments est O(n).
La hauteur dun arbre binaire de recherche de n éléments égale à EMBED Equation.3 .
La complexité de rééquilibrage, après une insertion, dans un arbre AVL de n éléments est O(n).
La complexité de rééquilibrage, après une insertion, dans un arbre BB de n éléments est O(lg n).
La complexité de rééquilibrage, après une insertion, dans un arbre bicolore de n éléments est ((1).
Linvariant de boucle doit être valide avant lexécution de la boucle.
La phase de terminaison ne fait pas partie de la démonstration de la validité de linvariant.
La complexité de lalgorithme tri par tas de n éléments est O(2 n lg n).
La complexité de lalgorithme tri bulle dune liste triée (en ordre croissant) de n éléments est ((n).
La complexité de lalgorithme tri par sélection dune 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.
Pour m = 7, citez toutes les différentes permutations hi(k) pour la clé k = 8.
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 dinsertion 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
Quelles sont les valeurs affichées à la fin dexécution de H(1, 6) ?
En déduire la complexité (borne approchée) de H(1, n).
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 dexécution requis pour terminer H(1, n).
Exercice 4 : Exactitude (2 points)
Soit lalgorithme suivant qui calcule le minimum dun 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 lexactitude de cet algorithme.
Bonne Chance !!
- PAGE 2/ NUMPAGES 2-
