Les principes des langages de programmation

Amphi 9

Question 0 : Le parcours DFS infixe d'un arbre binaire de recherche énumère les éléments dans
le désordre
l'ordre croissant
l'ordre décroissant

Question 1 : La borne inférieure d'un algorithme de tri est
n!
n ln(n)
n

Question 2 : Le tri fusion est
quasilinéaire en moyenne et dans le pire des cas
quadratique en moyenne et quasilinéaire dans le pire des cas
quasilinéaire en moyenne et quadratique dans le pire des cas
quadratique en moyenne et dans le pire des cas

Question 3 : Le tri rapide est
quasilinéaire en moyenne et dans le pire des cas
quadratique en moyenne et quasilinéaire dans le pire des cas
quasilinéaire en moyenne et quadratique dans le pire des cas
quadratique en moyenne et dans le pire des cas

Question 4 : Si on sait qu'un tableau est déjàtrié l'algorithme le plus rapide pour le trier est en temps
constant
ln(n)
n ln(n)

Question 5 : La recherche, l'insertion et la suppression d'un élément dans un arbre de recherche est
logarithmique en la taille de l'arbre
linéaire en la hauteur de l'arbre
c'est la même chose

Question 6 : En insérant des éléments ordonnés dans un arbre de recherche on obtient
un arbre de hauteur minimale
un arbre de hauteur maximale