QCM Algorithmes, structures de données et complexité – Partie 6

Questions pratiques pour testez vos connaissances sur la complexité en espace et en temps des algorithmes et des structures de données courants. Testez votre connaissance et travaillez sur les questions que vous trompez le plus souvent.

 

1. Lequel des cas suivants n’existe pas dans la théorie de la complexité?

A Meilleur cas

B Pire cas

C Moyenne cas

D Cas null

D

 

2. Quelle est la pire complexité temporelle du tri par insertion où la position des données à insérer est calculée à l’aide d’une recherche binaire?

A N

B NlogN

C N ^ 2

D N (logN) ^ 2

C
L’application de la recherche binaire pour calculer la position des données à insérer ne réduit pas la complexité temporelle du tri par insertion. En effet, l’insertion de données à une position appropriée implique deux étapes:

  1. Calculez la position.
  2. Déplacez les données de la position calculée de l’étape 1 d’une étape vers la droite pour créer un espace où les données seront insérées.

L’utilisation de la recherche binaire réduit la complexité temporelle de l’étape 1 de O(N) à O(logN). Cependant, la complexité temporelle de l’étape 2 reste toujours O(N). La complexité globale reste donc O(N ^ 2).

 

3. Quelle est la complexité temporelle de la fonction ci-dessous?
void algo(int n, int tab[])
{
    int i = 0, j = 0;
    for(; i < n; ++i)
        while(j < n && tab[i] < tab[j])
            j++;
}

A O(n)

B O(n^2)

C O(nlogn)

D O(n(logn)^2)

A
La complexité temporelle semble être O(n ^ 2) en raison de deux boucles. Mais notez bien que la variable j n’est pas initialisée pour chaque valeur de la variable i. Ainsi, la boucle interne s’exécute au maximum n fois. Veuillez observer la différence entre la fonction donnée en question et la fonction ci-dessous:

void algo2(int n, int tab[]) {
     int i = 0, j = 0;
     for(; i < n; ++i) {
          j = 0; 
          while(j < n && tab[i] < tab[j]) 
               j++; 
     } 
}

 

 

4. Le pire cas se produit dans l’algorithme de recherche linéaire lorsque ________?

A L’élément se trouve au milieu du tableau

B L’élément ne se trouve pas dans le tableau

C L’élément se trouve dans la dernière position du tableau

D L’élément se trouve dans la dernière position du tableau ou il n’existe pas

D

 

5. Considérons les boucles for suivantes:

A for(i = 0; i < n; i++)

B for(i = 0; i < n; i += 2)

C for(i = 1; i < n; i *= 2)

D for(i = n; i < -1; i /= 2)

Si n est la taille de l’entrée (positive), quelle boucle est la plus efficace ?

C
  • La complexité temporelle de la première boucle for est O(n).
  • La complexité temporelle de la seconde boucle est O(n / 2), ce qui équivaut à O(n) en analyse asymptotique.
  • La complexité temporelle de la troisième boucle for est O(logn).
  • La quatrième boucle for ne se termine pas.

 

6. Qu’est-ce que cela signifie quand on dit qu’un algorithme X est asymptotiquement plus efficace que Y?

A X sera un meilleur choix pour toutes les entrées

B X sera un meilleur choix pour toutes les entrées sauf les petites entrées

C X sera un meilleur choix pour toutes les entrées sauf les grandes entrées

D Y sera un meilleur choix pour les petits entrées

B
Dans l’analyse asymptotique, nous considérons la croissance de l’algorithme en termes de la taille d’entrée. Un algorithme X est dit asymptotiquement meilleur que Y si X prend moins de temps que y pour toutes les tailles d’entrée n supérieures à une valeur n0 où n0 > 0.

 

7. La complexité de l’algorithme de tri à bulles est _____?

A O(n)

B O(log n)

C O(n2)

D O(n log n)

C

 

8. Quelle est la complexité temporelle de l’algorithme de Floyd-Warshall pour calculer tous les chemins les plus courts d’une paire dans un graphe à n sommets?

A O(n ^ 2logn)

B Θ(n ^ 2logn)

C Θ(n ^ 4)

D Θ(n ^ 3)

D
L’algorithme Floyd – Warshall utilise trois boucles imbriquées pour calculer tous les chemins les plus courts. Donc, la complexité temporelle est Θ(n ^ 3).

 

9. La déclaration log(n!) = Θ(n log n) est-elle valide?

A Vrai

B Faux

A
Ordre de croissance de (log n!) et (n log n) est identique pour les grandes valeurs de n, c’est-à-dire Θ(log n!) = Θ(n log n). L’expression Θ(log n!) = Θ(n log n) peut facilement être déduite de l’approximation de log n! = n log n - n + O (log (n))

 

10. Les tableaux sont les meilleures structures de données

A Pour les collections de données relativement permanentes

B Pour les collections de données dont la structure changent constamment

C Tout les réponses sont vrais

D Aucun de ces réponses

A

 

Partagez cet article

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *