Algorithmes, structures de données et complexité questions à choix multiples (QCM)

Unknown

August 21, 2023 August 21, 2023

Un algorithme est une séquence d'instructions bien définies et ordonnées concue pour résoudre un problème spécifique ou accomplir une tâche donnée. En d'autres termes, c'est un ensemble d'étapes logiques et précises qui, lorsqu'elles sont suivies dans l'ordre approprié, permettent de transformer des entrées (données) en sorties (résultats) attendus.

Les algorithmes sont utilisés dans de nombreux domaines, tels que les sciences informatiques, les mathématiques, la logistique, la science des données et bien d'autres. Ce n'est pas la base de la solution automatique au problème, qui est fixée par les ordonnées de l'exécuteur du système de manière et répétable.

Un bon algorithme doit être précis, clair et efficace. Il doit être capable de produire les résultats souhaités pour toutes les entrées valides, et idéalement, il doit concevoir la juste manière optimale, en utilisant un minimum de ressources, comme le temps de calcul ou la mémoire.

Il n'y a aucune manière de représenter un algorithme, notamment à l'aide de descriptions en langage naturel, de pseudocode (une forme simplifiée de code), de diagrammes de flux et de langages de programmation spécifiques. Les algorithmes sont essentiels pour résoudre des problèmes complexes et pour automatiser des touches dans le domaine de l'informatique et au-delà.

1. Lequel des algorithmes de tri suivants présente la plus faible complexité dans le pire des cas?

A Tri à bulles

B Tri rapide

C Tri par sélection

D Tri par fusion

D

  Les pires de cas pour les algorithmes de tri ci-dessus sont les suivants:
Tri par fusion : n Logn
Tri à bulle de nLogn : n ^ 2
Tri rapide : n ^ 2
Tri par sélection : n ^ 2

2. Les éléments d’un tableau sont successivement stockés dans des zones de mémoire car...?

A) l’architecture de la mémoire de l’ordinateur ne permet pas aux matrices de stocker autre que série

B) De cette façon, l’ordinateur ne peut garder trace que de l’adresse du premier élément et les adresses des autres éléments peuvent être calculées

C) Aucun de ces réponses

D) Les deux A et B

B

3. Considérons la fonction suivante


 int fun(int n) {
    int i, j, k = 0;
    for (i  = n/2; i <= n; i++)
        for (j = 2; j <= n; j = j * 2)
            k = k + n/2;
    return k;
 }

Quelle est la valeur retournée par la fonction ci-dessus?

A Θ(n^3)

B Θ(n^2)

C Θ(n^2Logn)

D Θ(n^3Logn)

C

*La boucle externe s’exécute n / 2 ou Θ(n) fois.
*La boucle interne exécute Θ(Logn) fois (notez que j est multiplié par 2 à chaque itération).
*Donc, la déclaration « k = k + n / 2; » exécute Θ(nLogn) fois.
*L’instruction augmente la valeur de k de n / 2. Donc, la valeur de k devient n / 2 * Θ(nLogn) qui est Θ(n ^ 2Logn)

QCM

Tresor