Exemples de Questions d’Examen

8/16/2019 Exemples de Questions d’Examen

1/16

!"#$%' )# *+#',-./' 0+" #"0$#/'

1. Déterminez l’ordre de croissance du temps d’exécution des algorithmes suivants, en fonctionde n, en utilisant la notation asymptotique. Justifiez vos réponses.

"#$%&'( &)*+ &,) '- ..&/

0

"#$%&'( 1)*+ 1 ,) 2'3'+ 1../

0 4

4

55555555555

6#&7 "%&'( '/0

"#$%&'( &)8+ &,29:83'+ &../

;#= %& A 8/

0

& ) &BC+

4

2. Soit un entier naturel n. Considérez les fonctions de n suivantes.

a)

n log2(n) b) n1/2 c)

22n d) n ln(n) + 5ne) 2n

D#EFG$=$ >=H #$7$=H 7= ;$#&HHG';= 7= ;=H "#';('H =( >=H #$7#''=$ 7< F>#$HP


2/16

>Q#$7$= 7= ;$#&HHG';= 7= "%'/ =H( H($&;(=E='( F>


3/16

baromètre et exprimez votre réponse en utilisant la notation asymptotique. Vous devez justifier votre réponse. On suppose que le vecteur a est trié avant l’appel de cette fonction.

int findElement( const std::vector & a, const int & x ){

int min = 0;

int max = a.size( ) - 1;while( min


4/16

const_iterator begin() const;iterator end();const_iterator end() const;

private:int m_size; /*!


5/16

9. Considérez l’implémentation (partielle) suivante de List. Écrivez le corps des méthodesinsert() et erase() selon les spécifications mentionnées dans les commentaires.

templateclass List{

private:struct Node{Node(const Object & d = 0, Node* p = 0, Node* n = 0) :

data(d), prev(p), next(n) { }Object data;Node* prev;Node* next;

}; //Node

public:

class iterator{public:

iterator() : current(0) { }

Object & operator*(){

return current->data;}

iterator & operator++(){

current = current->next;return *this;

}iterator & operator--(){

current = current->prev;return *this;

}

private:Node* current;iterator(Node* p) : current(p) { }

friend class List;

};//iterator

public: //ListList() {init();}~List() { . . . }


6/16

// \brief insertion de x précédant le nœud pointé par itr// \param[in] l’objet x à insérer// \param[in] l’itérateur itr pointant sur un nœud// \pre s’il y en a ...// \return iterator pointant sur le nœud inséré contenant xiterator insert( const iterator & itr, const Object & x)

{//CODE À ÉCRIRE

}

// \brief suppression du nœud pointé par itr// \param[in] l’itérateur itr pointant sur le nœud à supprimer// \pre s’il y en a ...// \return iterator pointant sur le nœud suivant le nœud suppriméiterator erase(const iterator & itr){//CODE À ÉCRIRE

}private: //List

int theSize;Node * head;Node * tail;void init()//création des sentinelles

{theSize = 0;head = new Node;tail = new Node;head->next = tail;tail->prev = head;head->prev = tail->next = 0;

}}; //List


7/16

10. Écrivez le code du constructeur de copie et des méthodes operator=, empiler et dépiler pourl’implémentation suivante de Pile. L’utilisation des méthodes de est fortementencouragée.

#include #include

#include "ContratException.h"

template class Pile{public:

Pile() { }Pile(const Pile& source){ insérez ici le code du constructeur de copie

}

~Pile() { laPile.clear() ; }

const Pile& operator=(const Pile& p){ insérez ici le code de l’opérateur =

}

void empiler(const T& source);{ insertion du code ici

}

T depiler(){ insertion du code ici

}

int taille() const { return laPile.size() ; }

private:std::list laPile;

} ;


8/16

1. Vous disposez de la classe suivante

template class Arbre{

private:

class Noeud{public:

E data;Noeud *gauche;Noeud *droite;int hauteur;Noeud(const E & d): gauche(0),data(d),droite(0),hauteur(0) { }

};

Noeud * racine; //racine de l'arbrelong cpt; // Nombre de noeuds dans l'arbre

std::vector _parcoursEnOrdre(Noeud*, std::vector&) const;std::vector _parcoursPostOrdre(Noeud*, std::vector&) const;std::vector _parcoursPreOrdre(Noeud*, std::vector&) const;

public:

std::vector parcoursEnOrdre() const{

std::vector v; //pour stocker les résultats du parcours _parcoursEnOrdre(racine, v);return v;

}std::vector parcoursPostOrdre() const

{std::vector v; //pour stocker les résultats du parcours

_parcoursPostOrdre(racine, v);return v;

}std::vector parcoursPostOrdre() const{

std::vector v; //pour stocker les résultats du parcours _parcoursPreOrdre(racine, v);return v;

}

};

(a) Les méthodes publiques parcoursEnOrdre(), parcoursPostOdre() et parcoursPreOrdre()

permettent, respectivement, de visiter l’arbre binaire de recherche selon le parcours en-ordre

(parcours symmétrique), pré-ordre et post-ordre. Pour cela, elles font appel à des méthodes

privées de nom similaires. Fournissez l’implantation de ces méthodes aux endroits prévues à

cette fin ci-dessous.


9/16

template void Arbre::_parcoursPreOrdre(Noeud* arb, std::vector & v){

}template void Arbre::_parcoursEnOrdre(Noeud* arb, std::vector & v){

}template void Arbre::_parcoursPostOrdre(Noeud* arb, std::vector & v){

}

(b) Donnez le temps d’exécution de ces méthodes à l’aide de la notation asymptotique en

justifiant vos réponses.

(c) Considérant que cette classe met en œuvre un arbre binaire de recherche comme

conteneur de données, expliquez comment chaque donnée se trouvant dans cet arbre est

positionnée par rapport aux autres

(c)

S’il y a un ordre respecté dans ce positionnement, comment est-il défini en terme du type

générique E utilisé pour cette classe? Pour ce faire, est-ce qu’il est souhaitable de

surcharger certains opérateurs pour le type E? Si oui, lesquels?


10/16

(d)

Quelle est la définition de la «hauteur d’un nœud» dans un arbre binaire de recherche?

Quelle est la définition de la «profondeur d’un nœud»? Quelle est la définition de la

hauteur d’un arbre binaire de recherche? Quelle relation existe-t-il entre la hauteur d’un

nœud, sa profondeur et la hauteur de l’arbre binaire de recherche auquel il appartient?

4.

V#&( >G HMP


11/16

représentation arborescente pour illustrer les différentes étapes de la reconstruction du tasaprès avoir enlevé l’élément 22.

YK LME#'($=N PG @GQG$I$= \R] "&'G> HG H


12/16

aK b$#= F>=G EG($&;= 7= 6G>#$HP>G'( 7= & _ 1 (=> P=H H#EE=(H &'(=$EM7&G&$=H H#'( (#


13/16

*CK D#'H&7M$=N P= 7= H=H

H#EE=(H- \ 7MH&J'= >Q='H=EI>= 7= H=H G$;H =( ? =H( >G "#';(' 7= 6G>QG>J#$&(@E= 7= n=>>EG'5o#$7 W

!"#$%&'!" $%&'() *%+)",- .&/!- $012 32 45 ), !" 6*77), 6*!%8) 6 9) 1:

)*$#+&' ;),*!%") 6?+/ )@+6,) !" 8A8/) 9) '*+96 "-B&,+C: 1+"*"2 %),*!%") D;3E ), %),*!%") /&/*"B!)!% 90.5 ), /) '%-9-8)66)!% '0.5 9! '/!6 8*!%, 8()7+" &//&", 9) 6 F . '*!% ,*!, 6*77), . 9)1:

GH=; ,*!, . 9&"6 1 >G'( 7= H _ 6K


14/16

11. Considérez l’algorithme de tri suivant :

template void sort( vector & a ){

vector tmpArray( a.size( ) ); _sort( a, tmpArray, 0, a.size( ) - 1 );

}

template void _sort( vector & a,

vector & tmpArray, int left, int right){

if( left < right ){

int center = ( left + right ) / 2;

_sort( a, tmpArray, left, center ); _sort( a, tmpArray, center + 1, right ); _tri( a, tmpArray, left, center + 1, right );

}}

template void _tri( vector & a, vector & tmpArray,

int leftPos, int rightPos, int rightEnd){

int leftEnd = rightPos - 1;int tmpPos = leftPos;int numElements = rightEnd - leftPos + 1;

while( leftPos


15/16

Trouvez le temps d’exécution de cet algorithme en pire cas, en cas moyen et en meilleur cas.

Vous devez justifier vos réponses et les exprimer en utilisant la notation asymptotique en

fonction de la taille n du vecteur a.

--------------------------------

12.

(a) Quelle structure de données choisiriez-vous pour la mise en œuvre d’un conteneur de néléments vous assurant que les opérations suivantes s’effectuent en O(log n) en pire cas : larecherche d’un élément, l’insertion d’un élément, la suppression d’un élément, trouverl’élément de valeur maximale et trouver l’élément de valeur minimale? (b) Quelle structurede données choisiriez-vous pour la mise en œuvre d’un conteneur de n éléments vous assurantque les opérations suivantes s’effectuent en O(1) dans la presque totalité des cas : la recherched’un élément, l’insertion d’un élément, la suppression d’un élément?

13.

Vous disposez d’une table de dispersion comportant 10 entrées, numérotées de 0 à 9. Vousdésirez insérer dans cette table (et dans cet ordre, de gauche à droite) les entiers non signés

suivants 23, 22, 42, 64, 53. Pour y arriver, vous utilisez la fonction de hachage h(x) = x mod10. Indiquez à quelle entrée de la table sera positionné chaque élément (a) si vous utilisez unsondage linéaire vu en classe, (b) si vous utilisez le sondage quadratique vu en classe, (c) sivous utilisez un double hachage avec la fonction de hachage auxiliaire h’(x) = 7 – x mod 7.

14.

Vous disposez d’une table de dispersion comportant 10 entrées, numérotées de 0 à 9. Vousdésirez insérer dans cette table (et dans cet ordre, de gauche à droite) les entiers non signéssuivants 15, 14, 65, 44, 54, 35. Pour y arriver, vous utilisez la fonction de hachage h(x) = xmod 10. Indiquez à quelle entrée de la table sera positionné chaque élément (a) si vousutilisez un sondage linéaire, (b) si vous utilisez le sondage quadratique, (c) si vous utilisez undouble hachage avec la fonction de hachage auxiliaire h’(x) = 7 – x mod 7.


16/16

1.

Ajoutez le code manquant en C++ dans la fonction mergeSortAA() ci-dessous afin que lafonction mergeSort() puisse effectuer correctement le tri fusion sur le vecteur a. On suppose ici que letype Comparable surcharge operator= et operator

Documents

Exemples de Questions d’Examen