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

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. Laquelle des caractéristiques suivantes caractérise un algorithme efficace ?

A Il utilise un minimum de temps CPU

B Utilise un minimum de mémoire

C Est facile à mise en œuvre

D Toutes les réponses ci-dessus

D
Un algorithme efficace se caractérise par une utilisation minimale des ressources, notamment du temps de l’unité centrale(CPU) et de la mémoire, et par la facilité de sa mise en œuvre.

 

2. Qu’est-ce qui consiste à diviser un problème complexe en parties plus petites et plus faciles à gérer ?

A La décomposition

B L’abstraction

C Encapsulation

D Héritage

A
La décomposition est le processus qui consiste à diviser un problème complexe en parties plus petites et plus faciles à gérer, ce qui facilite sa résolution.

 

3. Quel est l’objectif principal du pseudocode ?

A Documenter les algorithmes en langage naturel

B Compiler et exécuter des algorithmes

C Déboguer le code

D Optimiser les algorithmes

A
Le pseudocode est utilisé pour documenter les algorithmes d’une manière lisible pour l’homme, représentant le fonctionnement d’un programme sans se soucier de la syntaxe.

 

 
 

4. Dans l’analyse des algorithmes, à quoi se réfère la complexité asymptotique ?

A La complexité dans le meilleur des cas

B La complexité dans le pire des cas

C La complexité dans le cas moyen

D Le comportement d’un algorithme lorsque la taille de l’entrée augmente

D
La complexité asymptotique fait référence au comportement d’un algorithme lorsque la taille de l’entrée augmente. Elle est généralement représentée par la notation Big O pour indiquer la limite supérieure de la durée d’exécution dans le pire des cas.

 

5. Quelle sera la sortie du pseudocode suivant si l’entrée est 5 ?
function factorial(n): if n == 1 return 1 else return n * factorial(n-1)

A 5

B 24

C 120

D Aucune de ces réponses

C
Le pseudocode définit une fonction récursive pour calculer la factorielle d’un nombre. Pour une entrée de 5, la fonction calculera 5*4*3*2*1, qui est égal à 120.

 

6. Considérons l’algorithme suivant pour calculer le nième nombre de Fibonacci:
function fib(n): if n <= 1 return n else return fib(n-1) + fib(n-2).

Quelle est la complexité temporelle de cet algorithme ?
 
A O(n)

B O(log n)

C O(n^2)

D O(2^n)

D
L'algorithme récursif donné pour calculer le nième nombre de Fibonacci a une complexité temporelle exponentielle, O(2^n), car il effectue deux appels récursifs pour chaque entrée autre que le cas de base, ce qui entraîne une augmentation significative du nombre d'opérations à mesure que n augmente.

 

 
 

7. Quelle notation Big O représente une complexité temporelle constante ?

A O(1)

B O(n)

C O(log n)

D O(n^2)

A
La complexité en temps constant, désignée par O(1), décrit un algorithme dont l'exécution prend le même temps, quelle que soit la taille de l'entrée.

 

8. Pour une recherche linéaire dans un tableau non trié de n éléments, quelle est la complexité temporelle moyenne ?

A O(1)

B O(n)

C O(log n)

D O(n^2)

B
La complexité temporelle moyenne de la recherche linéaire est O(n), car elle peut avoir à parcourir la moitié du tableau en moyenne avant de trouver l'élément cible.

 

9. Que signifie la notation Big O O(n^2) à propos du taux de croissance d'un algorithme ?

A Croissance linéaire

B Croissance quadratique

C Croissance logarithmique

D Croissance exponentielle

B
O(n^2) signifie une croissance quadratique, c'est-à-dire que la complexité temporelle augmente proportionnellement au carré de la taille de l'entrée.

 

 
 

10. En notation Big O, que représente typiquement O(log n) ?

A La complexité temporelle de la recherche binaire

B La complexité temporelle de la recherche linéaire

C La complexité spatiale des algorithmes de tri

D La complexité spatiale du hachage

A
O(log n) représente généralement la complexité temporelle des algorithmes qui divisent le problème en deux à chaque étape, comme la recherche binaire.

 

 

Laisser un commentaire

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