QCM Algorithmes, structures de données et complexité – Partie 23
Les algorithmes, les structures de données et la complexité sont des concepts fondamentaux en informatique, essentiels pour concevoir des systèmes performants et efficaces. Que vous soyez étudiant, professionnel en développement logiciel ou passionné par l’informatique, comprendre ces notions est crucial pour résoudre des problèmes complexes et optimiser les performances des applications. Dans cet article, nous vous proposons un QCM (Questionnaire à Choix Multiples) couvrant ces trois domaines clés. À travers ce test, vous pourrez évaluer vos connaissances en matière de conception d’algorithmes, de choix de structures de données appropriées et d’analyse de la complexité des algorithmes. Que vous soyez débutant ou confirmé, ce QCM vous aidera à tester vos compétences et à améliorer votre compréhension de ces concepts fondamentaux.
1. Quelle est la principale caractéristique d’un « graph » orienté ?
A Les arêtes n’ont pas de direction
B Les arêtes ont une direction
C Les arêtes sont pondérées
D Les sommets sont les mêmes dans les deux sens
B
Un graphe orienté (ou dirigé) est un graphe dans lequel les arêtes ont une direction. Cela signifie que chaque arête va d’un sommet à un autre, contrairement aux graphes non orientés où les arêtes sont bidirectionnelles.
2. Quelle est la principale caractéristique d’un arbre binaire ?
A Chaque nœud a au plus deux enfants
B Chaque nœud a un seul enfant
C Chaque nœud a un nombre illimité d’enfants
D Chaque nœud a trois enfants
A
Un arbre binaire est une structure dans laquelle chaque nœud a au plus deux enfants, souvent appelés « fils gauche » et « fils droit ». Cela en fait une structure très utilisée pour les recherches et le tri.
3. Quel est la complexité en temps de l’algorithme suivant ?
Algorithme Exemple
Entrée : un entier n
Sortie : Affichage des couples (i, j) où i et j vont de 0 à n-1
Début
Pour i allant de 0 à n-1 faire
Pour j allant de 0 à n-1 faire
Afficher i, j
Fin Pour
Fin Pour
Fin
A O(n)
B O(n log n)
C O(n²)
D O(log n)
C
L’algorithme contient deux boucles imbriquées, chacune allant de 0 à n−1, donc le nombre total d’itérations est n × n = n². La complexité est donc O(n²).
4. Quel est la complexité en temps de l’algorithme suivant ?
Algorithme Exemple
Entrée : un entier n
Sortie : Affichage des couples (i, j) où i va de 0 à n-1 et j va de i à n-1
Début
Pour i allant de 0 à n-1 faire
Pour j allant de i à n-1 faire
Afficher i, j
Fin Pour
Fin Pour
Fin
A O(n)
B O(n log n)
C O(n²)
D O(n³)
C
La première boucle s’exécute n fois. La deuxième boucle s’exécute de i à n, donc pour chaque i, le nombre d’itérations de la deuxième boucle est n − i. La somme des itérations est:
Cela donne une complexité de O(n²).
Cela donne une complexité de O(n²).
5. Quelle est la complexité en temps du code suivant ?
int example(int n) {
if (n <= 1) {
return n;
} else {
return example(n - 1) + example(n - 1);
}
}
A O(1)
B O(n)
C O(2^n)
D O(n²)
C
Le code effectue deux appels récursifs pour chaque valeur de n, donc le nombre total d'appels récursifs double à chaque niveau d'appel. Cela entraîne une complexité exponentielle de O(2^n).
6. Quelle est la complexité en temps du code suivant ?
void example(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; j++) {
printf("%d, %d\n", i, j);
}
}
}
A O(n)
B O(n log n)
C O(n²)
D O(n² / 2)
C
La première boucle s'exécute n fois, et la deuxième boucle s'exécute n/2 fois. Le nombre total d'itérations est donc n × n/2 = n² / 2, mais en termes de complexité asymptotique, la constante est ignorée, donc la complexité est O(n²).
7. Quelle est la complexité en temps du code suivant ?
void example(int n) {
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
printf("%d\n", i);
}
}
}
A O(1)
B O(n)
C O(n log n)
D O(n²)
B
La boucle s'exécute n fois, et à chaque itération, une condition est vérifiée. Le fait que l'on affiche les éléments uniquement lorsque i est pair ne change pas la complexité en termes de croissance. La complexité est donc O(n).
8. Quelle est la complexité en temps du code suivant ?
void example(int n) {
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
printf("%d, %d\n", i, j);
}
}
for (int k = 0; k < n; k++) {
printf("%d\n", k);
}
}
A O(n)
B O(n²)
C O(n log n)
D O(2n)
B
La première partie du code avec deux boucles imbriquées a une complexité de O(n²), comme analysé dans une question précédente. La deuxième boucle a une complexité de O(n). Comme la complexité totale est dominée par la partie la plus complexe, la complexité totale est O(n²).
9. Quelle est la complexité en temps du code suivant ?
void example(int n) {
int i = 1;
while (i < n) {
printf("%d\n", i);
i *= 2;
}
}
A O(n)
B O(log n)
C O(n log n)
D O(2^n)
B
À chaque itération, i est multiplié par 2. Cela signifie que le nombre d'itérations est de l'ordre de O(log2(n)), donc la complexité en temps est O(log n).
10. Quelle est la complexité en temps du code suivant ?
void example(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
for (int k = 0; k < j; k++) {
printf("%d, %d, %d\n", i, j, k);
}
}
}
}
A O(n)
B O(n²)
C O(n³)
D O(n⁴)
C
La première boucle s'exécute n fois, la deuxième boucle i fois (qui varie de 0 à n−1), et la troisième boucle j fois (qui varie de 0 à i−1). Le nombre total d'itérations est de l'ordre de O(n³).
- QCM Algorithmes – Notions de base – Partie 1
- QCM Algorithmes – Notions de base – Partie 2
- QCM Algorithmes – Notions de base – Partie 3
- QCM Algorithmes, structures de données et complexité – Partie 4
- QCM Algorithmes, structures de données et complexité – Partie 5
- QCM Algorithmes, structures de données et complexité – Partie 6
- QCM Algorithmes, structures de données et complexité – Partie 7
- QCM Algorithmes, structures de données et complexité – Partie 8
- QCM Algorithmes, structures de données et complexité – Partie 9
- QCM Algorithmes, structures de données et complexité – Partie 10
- QCM Algorithmes, structures de données et complexité – Partie 11
- QCM Algorithmes, structures de données et complexité – Partie 12
- QCM Algorithmes, structures de données et complexité – Partie 13
- QCM Algorithmes, structures de données et complexité – Partie 14
- QCM Algorithmes, structures de données et complexité – Partie 15
- QCM Algorithmes, structures de données et complexité – Partie 16
- QCM Algorithmes, structures de données et complexité – Partie 17
- QCM Algorithmes, structures de données et complexité – Partie 18
- QCM Algorithmes, structures de données et complexité – Partie 19
- QCM Algorithmes, structures de données et complexité – Partie 20
- QCM Algorithmes, structures de données et complexité – Partie 21
- QCM Algorithmes, structures de données et complexité – Partie 22
- QCM Algorithmes, structures de données et complexité – Partie 23
- QCM Algorithmes, structures de données et complexité – Partie 24
- QCM Algorithmes, structures de données et complexité – Partie 25
- QCM Algorithmes, structures de données et complexité – Partie 26
- QCM Algorithmes, structures de données et complexité – Partie 27
- QCM Algorithmes, structures de données et complexité – Partie 28
- QCM Algorithmes, structures de données et complexité – Partie 29
- QCM Algorithmes, structures de données et complexité – Partie 30
- 100 Exercices Corrigés En Algorithme avec les Organigrammes – Partie 1
- 100 Exercices Corrigés En Algorithme avec les Organigrammes – Partie 2
- 100 Exercices Corrigés En Algorithme avec les Organigrammes – Partie 3
- 100 Exercices Corrigés En Algorithme avec les Organigrammes – Partie 4
- 100 Exercices Corrigés En Algorithme avec les Organigrammes – Partie 5
- Exercices Corrigés En Algorithme – Les boucles
- Exercices Corrigés En Algorithme – Les tableaux
- Exercices Corrigés En Algorithme – Structure conditionnelle
- Exercices Corrigés En Algorithme – Fonctions et Procédures
- Différence entre Graphe et Arbre
- Différence entre pile et file dans structure des données
- Différence entre la programmation dynamique et la récursivité
- Différence entre un problème NP-Complet et NP-Difficile
QCMs qui pourraient vous intéresser :
- Questions techniques sur MYSQL
- QCM MySQL Corrigé – Optimisation de requêtes
- QCM Base de données avec correction
- QCM sur PHP
- QCM Symfony
- QCM AngularJS
- QCM React
- QCM HTML / CSS
- QCM Java – Programmation Orientée Objet
- QCM Python
- QCM Cloud Computing
- QCM Framework Spring
- QCM Javascript
- QCM jQuery
- QCM Oracle
- QCM sur GIT – Gestionnaire de version
- QCM Linux – Gestion de processus
- QCM Réseau
- QCM Architecture des ordinateurs
- QCM Securité informatique
- QCM En Informatique Générale
- QCM en C
- QCM en C#
- QCM sur l'algorithmique
- QCM Word
- QCM Excel
- QCM PowerPoint
- QCM Access
