Études pour examen

Question 1

Donnez la complexité asymptotique en pire cas d’un findMin()

Answer 1

O(1)

Question 2

Donnez la complexité asymptotique en pire cas d’un deleteMin()

Answer 2

O(lg(n))

Question 3

Donnez la complexité asymptotique en meilleur cas d’un buildHeap()

Answer 3

O(n)

Question 4

Donnez la complexité asymptotique en pire cas d’un buildHeap()

Answer 4

O(n)

Question 5

Donnez la complexité asymptotique en cas moyen d’un insert(AnyType x)

Answer 5

O(1)

Question 6

Donnez la complexité asymptotique en meilleur cas d’un insert(AnyType x)

Answer 6

O(1)

Question 7

Donnez la complexité asymptotique en meilleur cas d’un findmin()

Answer 7

O(1)

Question 8

Donnez la complexité asymptotique en cas moyen d’un findmin()

Answer 8

O(1)

Question 9

Donnez la complexité asymptotique en cas moyen d’un deleteMin()

Answer 9

O(lg(n))

Question 10

Donnez la complexité asymptotique en meilleur cas d’un deleteMin()

Answer 10

O(1)

Question 11

Donnez la complexité asymptotique en cas moyen d’un buildHeap()

Answer 11

O(n)

Question 12

Donnez la complexité asymptotique en pire cas d’un insert(AnyType x)

Answer 12

O(lg(n))

Question 13

Donnez la complexité asymptotique en cas moyen d’un insert(AnyType x)

Answer 13

O(1)

Question 14

Donnez la complexité asymptotique en pire cas d’un percolateDown()

Answer 14

O(lg(n))

Question 15

Donnez la complexité asymptotique en meilleur cas d’un percolateDown()

Answer 15

O(1)

Question 16

Donnez la complexité asymptotique en moyen cas d’un percolateDown()

Answer 16

O(lg(n))

Question 17

Donnez la complexité asymptotique en pire cas d’un changeKey(AnyType x,AnyType y)

Answer 17

O(1)

Question 18

Donnez la complexité asymptotique en pire cas d’un changeKey(AnyType x,AnyType y)

Answer 18

O(lg(n))

Question 19

Quel est la complexité de l’algorithme naïf?

Answer 19

O(m(n-m+1))

Question 20

Quel est la complexité de l’algorithme Rabin-Karp?

Answer 20

O(m(n-m+1))

Question 21

Le tri monceau est un tri interne.

Answer 21

Vrai, puisqu’il n’utilise pas de mémoire supplémentaire.

Question 22

Soit G = (V, E) un graphe dirigé. GT
(le graphe transposé de G) possède au moins
deux composantes fortement connexes si et seulement si G est connexe.

Answer 22

Faux. Si G est connexe, alors GT aussi, et il ne possède qu’une seule CFC.

Question 23

Les algorithmes issus des méthodes de programmation dynamique requièrent un
espace mémoire proportionnel à O(n
2
) (les besoins en mémoire croissent quadratiquement avec
la taille du problème).

Answer 23

Faux. Cela varie d’un problème à l’autre. Exemple Fibonnaci peut-être résolu avec un espace
mémoire (n), et même O(1).

Question 24

Un algorithme glouton est un algorithme dont les besoins en mémoire sont
proportionnels à O(n
2
) (croissent quadratiquement avec la taille du problème).

Answer 24

Faux. O(n) pour Kruskal par exemple.

Question 25

La solution vue en classe au problème de parenthésage des matrices est un
algorithme glouton.

Answer 25

Faux, algorithme issu des méthodes de programmation dynamique.

Question 26

Partant d’un sommet quelconque d’un graphe dirigé, le parcours DFS permet de
statuer sur la connexité du graphe (dire si le graphe est fortement connexe ou pas).

Answer 26

Vrai. Si le graphe est fortement connexe, DFS visitera tous les nœuds en partant d’un sommet
quelconque. Si ce n’est pas le cas lorsque le graphe n’est pas connexe.

Question 27

Si la longueur m d’un patron P[1 :m] est le quart de la longueur n du texte T[1 :n]
dans lequel il est recherché (m=n/4), alors pour des valeurs de n suffisamment grandes,
l’utilisation d’un automate est plus rapide que l’algorithme naïf, même en incluant le temps de
construction de l’automate

Answer 27

Faux. La construction du monceau se fait en O(dm). Si m est proportionnel à n, l’algorithme a
une complexité exponentielle.

Question 28

La structure de données d’ensembles disjoints vue en classe permet d’identifier
l’ensemble auquel appartient un élément en O(lg(n)) dans le pire cas.

Answer 28

Faux. O(n) en pire cas.