Fiche d’exercices de Algorithmes et complexité avec corrigé

Que signifie qu'une opération s'exécute en temps O(1) ?

1. AElle prend toujours exactement une seconde
2. BElle ne peut être exécutée qu'une seule fois
3. CSon temps d'exécution n'augmente pas avec la taille de l'entrée
4. DElle traite exactement un élément par seconde de temps d'exécution

Quelle est la complexité temporelle de la recherche linéaire dans un tableau non trié de n éléments (pire cas) ?

1. AO(n²)
2. BO(n)
3. CO(1)
4. DO(log n)

Quelles sont les trois étapes d'un algorithme « diviser pour régner » ?

1. ADeviner, vérifier, recommencer
2. BLire, calculer, écrire
3. CTrier, chercher, renvoyer
4. DDiviser, régner, combiner

Quelle est la complexité temporelle de : pour i = 1 à n : (j = 1 ; tant que j < n : j = j × 2) ?

1. AO(n log n)
2. BO(log n)
3. CO(n²)
4. DO(n)

Le parcours en largeur (BFS) sur un graphe non pondéré trouve :

1. AUn ordre topologique dans tous les graphes
2. BL'arbre couvrant de poids minimal
3. CLes plus courts chemins dans les graphes qui contiennent des poids d'arêtes négatifs
4. DLes plus courts chemins en nombre d'arêtes depuis le nœud de départ

Pourquoi la programmation dynamique n'apporte-t-elle aucune accélération réelle au tri fusion ?

1. ASes sous-problèmes ne se chevauchent pas, il n'y a donc rien à réutiliser
2. BLa programmation dynamique ne fonctionne que sur les problèmes de graphes, pas sur les tableaux
3. CLe tri fusion est déjà en O(n)
4. DLe tri fusion n'a pas de structure récursive

Quelle est la complexité temporelle de la construction d'un tas binaire à partir de n éléments non triés avec la méthode ascendante (bottom-up) ?

1. AO(n)
2. BO(n²)
3. CO(log n)
4. DO(n log n)

Quel algorithme trouve un arbre couvrant de poids minimal en ajoutant de façon répétée l'arête la moins coûteuse qui ne forme pas de cycle ?

1. AL'algorithme de Kruskal
2. BL'algorithme de Dijkstra
3. CFloyd-Warshall
4. DL'algorithme de Prim à partir d'un seul nœud