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

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. Le facteur temps pour déterminer l’efficacité de l’algorithme est mesuré par _____?

A Compter les microsecondes

B Compter le nombre d’opérations

C Compter le nombre de déclarations

D Compter les kilo-octets d’algorithme

Réponse

2. Quelle est la complexité temporelle du code suivant?

int compteur2(int n)
{
  int c = 0;
  for (int i = 0; i < n; i++)
     for (int j = i; j > 0; j--)
        c = c + 1;
  return c;
}

A O(n)

B O(n^2)

C O(n*Logn)

D O(n*Logn*Logn)

Réponse  

3. Laquelle des structures de données suivantes n’est pas une structure de données linéaire?

A Tableaux

B Liste chaînée

C Les deux A et B

D Aucune des réponses ci-dessus

Réponse

4. Quelle est la complexité temporelle du code suivant?

int compteur (int n)
{
   int c = 0;
   for(int i = n; i > 0; i/= 2)
      for(int j = 0; j < i; j++)
         c += 1;
   return c;
}

A O(n^2)

B O(n*Logn)

C O(n)

D O(n*Logn*Logn)

Réponse

5. La relation de récurrence capturant le temps optimal du problème de la tour de Hanoi avec n disques est. _______?

A T (n) = 2T (n – 2) + 2

B T (n) = 2T (n – 1) + n

C T (n) = 2T (n / 2) + 1

D T (n) = 2T (n – 1) + 1

Réponse

6. La complexité de l’algorithme Recherche Linéaire est _____?

A O(n)

B O(log n)

C O(n2)

D O(n * log n)

Réponse  

7. La complexité en moyenne se produit dans l’algorithme Recherche Linéaire. Quand l’élément recherché _______?

A Se trouve au milieu du tableau

B Ne se trouve pas dans le tableau

C Est le dernier élément du tableau

D Est le dernier élément du tableau ou n’y est pas du tout

Réponse

8. Quelle est la récurrence pour le pire de cas de l’algorithme du tri rapide et quelle est la complexité temporelle dans le pire des cas?

A La récurrence est T (n) = T (n-2) + O (n) et la complexité temporelle est O (n ^ 2)

B La récurrence est T (n) = T (n-1) + O (n) et la complexité temporelle est O (n ^ 2)

C La récurrence est T (n) = 2T (n / 2) + O (n) et la complexité temporelle est O (n*Logn)

D La récurrence est T (n) = T (n / 10) + T (9n / 10) + O (n) et la complexité temporelle est O (n*Logn)

Réponse

9. Laquelle des structures de données suivantes est une structure de données linéaire?

A Arbres

B Graphes

C Tableaux

D Aucun de ces réponses

Réponse  
10. Supposons que nous ayons un algorithme de temps O (n) qui trouve la médiane d’un tableau non trié. Considérons maintenant une implémentation de l’algorithme du tri rapide où nous trouvons d’abord la médiane en utilisant l’algorithme du tri rapide, puis utilisons la médiane comme pivot. Quelle sera la pire complexité temporelle de cet algorithme modifié?
 
A O(n^2 * Logn)

B O(n^2)

C O(n*Logn*Logn)

D O(n*Logn)

Réponse