←
Questions de révision

Questions de révision

1 .
Pourquoi avons-nous introduit les structures de données arborescentes comme alternative aux structures de données linéaires ?
  1. Certaines données complexes ne peuvent être représentées qu'avec une structure de données arborescente.
  2. Certaines données simples ne peuvent être représentées qu'avec une structure de données arborescente.
  3. Les structures de données linéaires ne peuvent pas implémenter les ensembles et les cartes.
  4. Les structures de données arborescentes sont généralement plus efficaces pour implémenter les ensembles et les cartes.
2 .
En quoi le type de données abstrait graphe diffère-t-il des autres types de données abstraits ?
  1. Il peut modéliser les relations entre les éléments.
  2. Il est plus efficace que les autres types de données abstraits.
  3. Il peut résoudre des problèmes que d'autres types de données abstraits ne peuvent pas résoudre.
  4. Il ne spécifie pas une implémentation de structure de données particulière.
3 .
Quel type de données abstrait les tas binaires implémentent-ils le plus couramment ?
  1. listes
  2. ensembles
  3. cartes
  4. files de priorité
4 .
Quelle est une façon de décrire la relation entre les algorithmes, les problèmes et la modélisation ?
  1. Les algorithmes sont le fondement des modèles de problèmes.
  2. Les algorithmes résolvent un modèle d'un problème.
  3. Chaque algorithme ne peut être utilisé que pour résoudre un seul problème.
  4. Chaque problème ne peut avoir qu'un seul modèle.
5 .
À quel moment les informaticiens appliquent-ils les patrons de conception d'algorithmes ?
  1. lors de l'apprentissage des algorithmes canoniques
  2. lors de la modélisation d'un problème
  3. lors de la résolution de nouveaux problèmes
  4. lors de l'analyse d'un algorithme
6 .
Comment le modèle de calcul se rapporte-t-il au modèle de problème ?
  1. Le modèle de calcul est synonyme du modèle de problème.
  2. Les modèles de problèmes contraignent le modèle de calcul.
  3. Le modèle de calcul contraint le processus de modélisation du problème.
  4. Le modèle de calcul décrit un seul algorithme pour chaque modèle de problème.
7 .
Pourquoi l'analyse de cas est-elle importante ?
  1. L'analyse de cas offre une alternative à l'analyse asymptotique.
  2. L'analyse de cas se concentre sur les petites entrées.
  3. L'analyse de cas simplifie le comptage des étapes en introduisant un modèle de coût.
  4. L'analyse de cas prend en compte des facteurs autres que la taille du problème.
8 .
Qu'est-ce qui est vrai concernant l'ordre de grandeur de la recherche binaire par rapport à la taille de la liste triée ?
  1. Dans le meilleur des cas, l'ordre de grandeur de la recherche binaire est constant.
  2. Dans le meilleur des cas, l'ordre de grandeur de la recherche binaire est logarithmique.
  3. Dans le pire des cas, l'ordre de grandeur de la recherche binaire est constant.
  4. Dans le pire des cas, l'ordre de grandeur de la recherche binaire est linéaire.
9 .
Comment la complexité temporelle se rapporte-t-elle à la complexité spatiale ?
  1. La complexité temporelle mesure l'efficacité en fonction de la taille du problème, tandis que la complexité spatiale ne le fait pas.
  2. La complexité temporelle et la complexité spatiale mesurent toutes deux l'efficacité des algorithmes en ce qui concerne la nature du problème.
  3. La complexité temporelle se concentre sur l'analyse asymptotique, tandis que la complexité spatiale se concentre sur l'analyse expérimentale.
  4. La complexité temporelle et la complexité spatiale peuvent toutes deux appliquer des méthodes issues de l'analyse asymptotique et de l'analyse expérimentale.
10 .
Quelles sont les trois étapes des algorithmes diviser pour régner ?
11 .
Pourquoi de nombreux algorithmes gloutons ne parviennent-ils pas à calculer la meilleure solution à un problème combinatoire ?
12 .
Quelles sont les trois étapes des algorithmes de réduction ?
13 .
Quel est le patron de conception d'algorithme et le paradigme algorithmique de quicksort ?
  1. Quicksort est une application du patron de conception d'algorithme d'arbre binaire de recherche et un exemple du paradigme algorithmique diviser pour régner.
  2. Quicksort est une application du patron de conception d'algorithme d'arbre binaire de recherche et un exemple du paradigme algorithmique par force brute.
  3. Quicksort est une application du patron de conception d'algorithme d'arbre binaire de recherche et un exemple du paradigme algorithmique glouton.
  4. Quicksort est une application du patron de conception d'algorithme d'arbre binaire de recherche et un exemple du paradigme algorithmique de construction incrémentale randomisée.
14 .
Quels problèmes de graphe le parcours en largeur peut-il résoudre ?
  1. arbre à nœuds exponentiels
  2. arbres couvrants minimaux
  3. plus courts chemins non pondérés
  4. plus courts chemins pondérés
15 .
Quel est un inconvénient majeur du hachage ?
  1. Il peut y avoir des collisions car le même élément peut être haché à plusieurs valeurs.
  2. Il peut y avoir des collisions entre plusieurs éléments qui hachent à la même valeur.
  3. Le hachage est plus lent que la recherche binaire pour les problèmes de recherche.
  4. Le hachage est plus rapide que la recherche binaire pour les problèmes de recherche.
16 .
Quelle est la relation entre les machines de Turing et les modèles de calcul ?
17 .
Quelle est l'une des trois idées clés de la machine de Turing ?
  1. mémoire infinie par virtualisation
  2. une banque de mémoire pour stocker des données
  3. utiliser diviser pour régner pour toujours réduire un algorithme à une exécution en O(n)
  4. utiliser diviser pour régner pour toujours réduire un algorithme à une exécution en O(1)
18 .
Qu'est-ce que P versus NP ?
  1. P fait référence à la classe de complexité temporelle polynomiale, tandis que NP fait référence à la classe de complexité temporelle polynomiale non déterministe.
  2. P fait référence à toute notation grand O au-delà de O(N3), tandis que NP fait référence à toute notation grand O inférieure à O(N3).
  3. NP est une exécution constante, tandis que P est une exécution polynomiale.
  4. P fait référence à une exécution constante, tandis que NP est une exécution linéaire.