Scribd
Importer
244 vues1 page

Conception Et Analyse Des Algorithmes

L'examen porte sur la conception et l'analyse des algorithmes. Le premier exercice concerne l'analyse de la complexité mémoire et temporelle d'une pile implémentée avec un tableau redimensionnable. Le deuxième exercice demande d'écrire un algorithme itératif vérifiant l'égalité des parcours préordre de deux arbres binaires. Le troisième exercice consiste à dessiner un arbre binaire à partir de ses séquences d'ordre et de post-ordre données.

Transféré par

y20b18zera
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
244 vues1 page

Conception Et Analyse Des Algorithmes

L'examen porte sur la conception et l'analyse des algorithmes. Le premier exercice concerne l'analyse de la complexité mémoire et temporelle d'une pile implémentée avec un tableau redimensionnable. Le deuxième exercice demande d'écrire un algorithme itératif vérifiant l'égalité des parcours préordre de deux arbres binaires. Le troisième exercice consiste à dessiner un arbre binaire à partir de ses séquences d'ordre et de post-ordre données.

Transféré par

y20b18zera
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Université de Ghardaia 2023-2024

Département des Mathématiques et d'informatique 18/12/2023


1eme Annee Master SIEC (Semestre 1)
Durée: 01H 30mn
Examen Partiel
Conception et Analyse des Algorithmes
Documents,calculatrices, prêt des affaires personnelles (stylos, effaceurs, etc.) et téléphones portables sont
interdits.
Exercice 1:(6.00 points)
Considérez l'implémentation partielle suivante d'une pile d'entiers qui
redimensionnable. Supposons que l'implémentation triple la longueur du tableau lorsutilise
un tableau
push() si le d'une opération
tableau est plein, mais elle ne réduit jamais le tableau lors d'une opération pop().
publicclass StackOflnts (
private int|] a; //underlying array
private int n; // number of integers in the stack

1. Dans le pire des cas, donnez I'usage de l'espace mémoire d'un


cbjet StackOfints après avoir
appelépush() n fois consécutives sur une pile initialement vide ? Utilisez notre modèle de coût de
mémoire 64 bits. Utilisez la notation tilde pour simplifier votre réponse. 3 pts
2. Quel est la complexité (notation O), dans le pire des
cas, des opérations suivantes : 3 pts
o. push()
b. pop()
C. Toute séquence mélangée de m push() et popl), àpartir
d'une pile vide
Exercice 2: (9.00 points)
Dans ce problème, utilisez la définition suivante de l'arbre
classes ont les getters/setters standard. binaire. Vous pouvez supposer que les
public class BTNode<T> {
private T datta;
private 8TNode<T> leftChild;
private BTNode<T> rightChild;
private BTNOde<T> parent;
public void setData(T data);
public T getData();
public void setleftChild (BTNode<T> leftChild );
public void setrightChild (3TNode<T>
public 9TNode<T> getleftChild (); rightChild);
public BTNode<T> getrightChild ();

public class BinaryTree<T> {


private BTNode<T> root;
Écrivez une méthode itérative pour la classe BinaryTree qui
arbres ont le mêrne parcours préordre. Le temps obtient un autre arbre et vérifie si les
d'exécution
la taille du plus petit artbre. Par exemple, si un arbre a n
doit être 0(n) dans le pire des cas, oùn est
d'exécution doit être O(n). Expliquez votre algorithme et sonsommets
et l'autre n sommets, le temps
temps d'exécution.
public boolean samePreorder (BinaryTree<T> tree) { ... }
Exercice 3 : (5.00 points)
Dessiner un arbre binaire dont la séquence dans Il'ordre
(inorder) est (1,2,3,4,5,6,7,8] et post ordre
est [2,1,4,6,5,3,8,7]. Expliquer votre approche.
Bon corage

Page 1/1

Vous aimerez peut-être aussi