QCM Algorithmes, structures de données et complexité – Partie 10
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. Quelle est la complexité temporelle de l’accès à un élément d’un tableau par son index ?
A O(1)
B O(n)
C O(log n)
D O(n^2)
A
L’accès à un élément d’un tableau par son index est une opération O(1) car elle calcule directement l’emplacement de l’élément sans avoir à parcourir le tableau.
2. Dans un tableau d’entiers non triés, quelle est la meilleure complexité temporelle réalisable pour la recherche d’une valeur spécifique ?
A O(1)
B O(n)
C O(log n)
D O(n^2)
B
Dans un tableau non trié, la meilleure complexité temporelle réalisable pour la recherche d’une valeur spécifique est O(n), car il peut être nécessaire de vérifier chaque élément jusqu’à ce que la valeur souhaitée soit trouvée.
3. Si l’on considère un tableau de caractères représentant une chaîne de caractères, quelle est la complexité spatiale du stockage de cette chaîne ?
A O(1)
B O(n)
C O(log n)
D O(n^2)
B
La complexité spatiale du stockage d’une chaîne de caractères dans un tableau de caractères est O(n), où n est le nombre de caractères de la chaîne, car chaque caractère nécessite une quantité fixe d’espace.
4. Quelle opération a une plus grande complexité temporelle dans un tableau dynamique lorsqu’il doit augmenter sa taille ?
A Accès à un élément par l’index
B Ajout d’un élément à la fin
C Insérer un élément au début
D Recherche d’un élément
C
L’insertion d’un élément au début d’un tableau dynamique lorsqu’il doit augmenter sa taille implique le déplacement de tous les éléments existants, ce qui en fait une opération coûteuse. L’ajout est généralement efficace en raison du temps constant amorti, mais l’expansion nécessite de copier des éléments dans un nouveau tableau, ce qui est moins fréquent.
5. Qu’est-ce qui distingue une liste simple d’une liste double ?
A Chaque nœud possède un pointeur dans une liste simple et deux dans une liste doublement chaînée.
B Les listes simples sont plus rapides
C Les listes doublement chaînées ne peuvent pas avoir de cycles
D Toutes les réponses ci-dessus
A
Dans une liste simple, chaque nœud pointe vers le nœud suivant, alors que dans une liste doublement liée, chaque nœud possède deux pointeurs : un pour le nœud suivant et un pour le nœud précédent, ce qui offre une plus grande flexibilité dans la navigation.
6. Quelle opération est généralement plus efficace dans une liste chaînée que dans un tableau ?
A L’accès à un élément par son index
B L’ajout d’un élément à la fin de la liste
C Insérer un élément au début
D Recherche d’un élément
C
L’insertion d’un élément au début d’une liste chaînée est généralement plus efficace que dans un tableau, car elle ne nécessite pas de déplacer des éléments, mais seulement de mettre à jour des pointeurs.
7. Pour lequel des scénarios suivants une liste chaînée NE convient-elle PAS ?
A Lorsque les éléments doivent être accédés de manière séquentielle
B Lorsque l’utilisation de la mémoire est un problème
C Lorsqu’un accès rapide aux éléments par index est nécessaire
D Lorsque des éléments sont fréquemment ajoutés ou supprimés
C
Les listes chaînées ne permettent pas d’accéder directement aux éléments par leur index, ce qui les rend inadaptées aux scénarios nécessitant un accès rapide et aléatoire. En revanche, elles sont idéales pour les situations où les ajouts et les suppressions sont fréquents.
8. Dans une liste chaînée, que signifie le pointeur « head » ?
A Le nœud central de la liste
B Le dernier nœud de la liste
C Le premier nœud de la liste
D Un nœud aléatoire dans la liste
C
Le pointeur « head » d’une liste chaînée indique le premier nœud de la liste et sert de point d’entrée pour accéder à tous les autres nœuds en parcourant la liste.
9. Comment détecter un cycle dans une liste chaînée ?
A En vérifiant si le pointeur suivant d’un nœud est nul
B En utilisant une table de hachage pour stocker les nœuds visités
C En comparant chaque nœud avec tous les autres nœuds
D Utilisation de deux pointeurs à des vitesses différentes
D
La technique consistant à utiliser deux pointeurs (souvent appelés pointeurs lent et rapide, le pointeur rapide se déplaçant deux fois plus vite que le pointeur lent) permet de détecter les cycles. Si les deux pointeurs se rencontrent, il existe un cycle ; si le pointeur rapide atteint la fin de la liste, celle-ci n’a pas de cycle.
10. Quelle est la complexité temporelle de la recherche de l’élément central d’une liste chaînée ?
A O(1)
B O(n)
C O(log n)
D O(n^2)
B
La recherche de l’élément central d’une liste chaînée nécessite de parcourir la moitié de la liste en moyenne, ce qui se traduit par une complexité temporelle O(n), puisqu’elle dépend linéairement de la longueur de la liste.
- 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
- 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
