QCM : Algorithmique et structures de données (39 questions)

Explication

Un tuple est non mutable : son contenu ne peut pas être modifié après sa création. Une liste, en revanche, peut être modifiée, mais les autres propositions décrivent des propriétés qui ne définissent pas les tuples.

Explication

L’opérateur + concatène les deux tuples en plaçant leurs éléments bout à bout. La répétition d’un tuple correspondrait à un clonage, tandis que l’ordre des éléments reste celui des opérandes.

Explication

L’affectation parallèle permet d’affecter simultanément à $a$ et $b$ les anciennes valeurs de $b$ et $a$. Les autres instructions dupliquent une valeur ou fournissent un nombre inadéquat d’éléments.

Explication

Les indices négatifs commencent à la fin de la liste : $L[-1]$ vaut 40 et $L[-2]$ vaut donc 30. L’indice 0 désigne le premier élément, ce qui explique l’erreur de la proposition correspondante.

Explication

Dans une tranche, la borne de début est incluse et la borne de fin est exclue : $L[1:4]$ contient donc les indices 1, 2 et 3. La proposition incluant l’élément d’indice 4 confond la borne finale avec une borne incluse.

Explication

Une chaîne est une séquence de type $str$ qui peut être indexée, mais dont le contenu ne peut pas être modifié directement. Les autres propositions lui attribuent à tort le type d’une liste, des propriétés numériques ou le type d’un tuple.

Explication

Une pile suit le principe LIFO : le dernier élément ajouté est le premier retiré, et seul le sommet est directement accessible. Le principe FIFO décrit une file, tandis que les deux autres propositions ne correspondent pas au fonctionnement d’une pile.

Explication

Une file suit le principe FIFO : les éléments entrent par la queue et sortent par la tête. Le fonctionnement d’une pile utilise un sommet, tandis que retirer par la queue ne respecte pas la définition donnée d’une file.

Explication

L’instruction $del(D["nom"])$ supprime l’association correspondant à la clé « nom » ; la méthode $D.pop("nom")$ aurait également convenu. Affecter une valeur modifie l’association, tandis que les autres instructions ne suppriment pas cette clé.

Explication

Le tri par sélection place progressivement le maximum de la partie non triée à sa position finale, en l’échangeant avec son dernier élément. Le décalage d’éléments pour insérer une valeur correspond au tri par insertion.

Explication

Le tri par insertion parcourt les éléments et décale les valeurs supérieures dans la partie déjà triée afin d’insérer l’élément à sa place. Les échanges entre voisins caractérisent plutôt le tri à bulles.

Explication

La recherche dichotomique exploite l’ordre de la liste et divise par deux la zone examinée à chaque étape. La recherche séquentielle parcourt les éléments successivement sans effectuer cette division.

Explication

Le mode a conserve le contenu existant et ajoute les nouvelles données à la fin du fichier. Le mode w peut écraser le contenu présent ou créer le fichier s’il n’existe pas.

Explication

La méthode close() ferme le fichier une fois les opérations terminées. La méthode write() sert à écrire des données et ne ferme pas le fichier.

Explication

read(t) lit t caractères depuis la position courante, readline() lit une ligne et readlines() fournit la liste des lignes. Les autres associations confondent les rôles des fonctions de lecture ou leur attribuent des opérations d’écriture.

Explication

Un tableau bidimensionnel Python est une liste de listes, chaque sous-liste représentant une ligne. Cette structure permet de décrire séparément le nombre de lignes et de colonnes.

Explication

La fonction array() convertit une liste ou une liste de listes en tableau NumPy. La fonction reshape() modifie une forme existante, tandis qu'append() ajoute des éléments et dot() effectue un produit.

Explication

reshape(5,3) modifie la forme du tableau pour obtenir 5 lignes et 3 colonnes sans changer ses éléments, soit quinze valeurs réparties autrement. La fonction append(), contrairement à reshape(), peut modifier le nombre d’éléments.

Explication

La fonction dot(A,B) réalise le produit matriciel de deux matrices, alors que vdot(A,B) calcule le produit scalaire de deux vecteurs. Les autres propositions attribuent à ces fonctions des opérations de forme ou de modification de tableau.

Explication

La fonction show rend la figure visible après sa préparation. La fonction plot construit la courbe, mais elle ne correspond pas à l’opération d’affichage elle-même.

Explication

xlabel et ylabel servent respectivement à nommer les axes horizontal et vertical. title ajoute un titre, tandis que plot trace la courbe et show affiche la figure.

Explication

La condition de base arrête la récursion lorsqu’elle est atteinte. L’appel récursif produit au contraire une nouvelle activation de la fonction.

Explication

La récursivité multiple comporte plusieurs appels récursifs dans une même étape. Un seul appel correspond à la récursivité simple, tandis que les deux autres descriptions désignent d’autres formes.

Explication

Le tri fusion divise récursivement la liste jusqu’à obtenir des sous-listes d’un élément, puis les fusionne dans l’ordre. Les autres descriptions correspondent à d’autres stratégies de tri.

Explication

Un arbre binaire est vide ou possède une racine et deux sous-arbres binaires disjoints, gauche et droit. Le nombre de sous-arbres et la présence d’une racine le distinguent des autres structures.

Explication

La profondeur d’un nœud est sa distance à la racine, tandis que la hauteur de l’arbre est la profondeur maximale de ses nœuds. Ainsi, la racine a une profondeur de 0 et la hauteur décrit l’arbre entier.

Explication

Le parcours préfixe suit l’ordre NGD : nœud, gauche, droite. Le parcours infixe place la racine entre les deux sous-arbres, tandis que le parcours suffixe la place après eux.

Explication

Le parcours en largeur explore l’arbre niveau par niveau, alors que le parcours en profondeur complète une branche avant de passer à la suivante. Les autres propositions confondent leurs stratégies ou leur attribuent des opérations étrangères.

Explication

Une valeur inférieure à celle d’un nœud est placée dans son sous-arbre gauche, tandis qu’une valeur supérieure va dans le sous-arbre droit. La placer à droite inverserait la règle d’organisation de cet arbre.

Explication

Un arbre maximier est un arbre parfait où chaque nœud possède une valeur supérieure à celles de ses deux fils. La propriété porte donc sur la comparaison entre chaque nœud et ses descendants immédiats, et non sur l’ordre global des niveaux.

Explication

La comparaison avec la racine permet de sélectionner le sous-arbre correspondant au sens de l’inégalité, ce qui évite d’explorer l’autre sous-arbre. Explorer les deux branches correspondrait davantage au comportement d’une recherche dans un arbre sans propriété d’ordre.

Explication

La complexité algorithmique évalue le coût d’exécution en fonction de la taille des données d’entrée, notamment au moyen du nombre d’opérations de base. La correction concerne la justesse du résultat et constitue une notion différente.

Explication

Une croissance proportionnelle à la taille de l’entrée relève de la classe linéaire $\Theta(n)$. Une complexité constante ne dépend pas de cette taille, tandis que les classes logarithmique et quadratique suivent des croissances différentes.

Explication

La notation O conserve le terme dominant et ignore les constantes multiplicatives ainsi que les termes additifs secondaires, ce qui donne $O(n^2)$. Le calcul exact pourrait conserver ces détails, mais l’analyse asymptotique les écarte.

Explication

À chaque étape, la recherche dichotomique élimine environ la moitié des éléments encore possibles, d’où une croissance logarithmique $\Theta(\log_2(n))$. Examiner chaque élément une fois conduirait plutôt à une complexité linéaire.

Explication

Un graphe non orienté est un couple composé d’un ensemble de sommets et d’un ensemble d’arêtes, chaque arête étant une partie à deux éléments de cet ensemble. Les couples ordonnés et la distinction origine-destination caractérisent plutôt les graphes orientés.

Explication

Un arc orienté est un couple de sommets dans lequel l’ordre distingue l’origine de la destination : $\left(x,y\right)$ et $\left(y,x\right)$ sont donc différents. Cette distinction n’existe pas pour une arête non orientée.

Explication

Chaque arête non orientée contribue une unité au degré de chacun de ses deux sommets, donc la somme des degrés vaut $S=2a$. Le nombre de sommets correspond à l’ordre du graphe et ne détermine pas directement cette somme.

Explication

Un cycle eulérien existe si le graphe est connexe et si tous ses sommets ont un degré pair. La connexité seule ne suffit pas, et la présence de sommets de degré impair empêche cette propriété.