QCM : Introduction aux Structures de Données et Algorithmes — 22 questions

Explication

Une pile fonctionne en LIFO : on retire d’abord le dernier élément inséré. La FIFO correspond au fonctionnement d’une file, pas d’une pile.

Explication

La méthode __init__ est utilisée pour initialiser les attributs d’un objet au moment de sa création. Elle ne gère ni l’héritage ni le parcours des objets.

Explication

Par défaut, parcourir un dictionnaire en boucle itère sur ses clés. Pour parcourir les valeurs ou les couples clé-valeur, on utilise respectivement values() et items().

Explication

On ajoute ou modifie une entrée avec une affectation sur la clé, sous la forme dictionnaire[cle] = valeur. append et insert ne sont pas des opérations de dictionnaire.

Explication

Dans un ABR, les valeurs du sous-arbre gauche sont inférieures à celle du nœud, et celles du sous-arbre droit lui sont supérieures. C’est la règle qui permet la recherche efficace.

Explication

La hauteur correspond au nombre d’arêtes entre la racine et le nœud le plus profond, et vaut -1 si l’arbre est vide. Cela distingue bien un arbre vide d’un arbre de hauteur nulle.

Explication

Le parcours infixe visite d’abord le sous-arbre gauche, puis la racine, puis le sous-arbre droit. Dans un ABR, cela produit les valeurs dans l’ordre croissant.

Explication

Un AVL est un ABR auto-équilibré qui maintient une hauteur logarithmique, ce qui améliore la recherche. Un ABR non équilibré peut au contraire dégénérer et coûter linéairement.

Explication

Dans une matrice d’adjacence, la case i,j contient l’information sur l’arête de i vers j, notamment son poids si le graphe est pondéré. Une valeur nulle indique généralement l’absence d’arête.

Explication

DFS, ou parcours en profondeur d’abord, avance au maximum dans une branche avant de revenir en arrière. Le parcours en largeur, lui, explore niveau par niveau avec une file.

Explication

Une clé primaire sert à identifier de façon unique chaque ligne d’une table. La clé étrangère sert, elle, à établir un lien avec une autre table.

Explication

Le symbole # indique qu’un attribut est une clé étrangère. Une clé primaire est plutôt représentée par un soulignement dans le schéma.

Explication

Une table de routage contient notamment la destination, l’interface de sortie et la passerelle à utiliser. Ces éléments servent à déterminer le prochain saut.

Explication

RIP est basé sur l’échange périodique de tables entre routeurs et utilise le nombre de sauts comme métrique. Le calcul de coût minimal correspond plutôt à OSPF.

Explication

Le cas de base est la condition qui stoppe la récursion. Sans lui, la fonction risquerait de s’appeler indéfiniment.

Explication

Le tri fusion combine ensuite les deux moitiés déjà triées en comparant leurs premiers éléments. C’est cette fusion qui reconstruit la liste finale triée.

Explication

La fonction dir() affiche les noms accessibles dans un module ou un objet. Pour la documentation, on utilise plutôt help().

Explication

Avec from module import fonction, la fonction peut être appelée directement, sans écrire le nom du module devant. Cela s’oppose à import module, où le préfixe reste nécessaire.

Explication

Le tri par insertion déplace vers la droite les éléments plus grands que la valeur à insérer, puis insère cette valeur à sa place. Il construit ainsi progressivement une zone triée.

Explication

Le tri par sélection repère le minimum dans la partie restante puis l’échange avec l’élément courant. C’est ce qui le distingue du tri par insertion.

Explication

Deux nombres sont congrus modulo $n$ lorsque $n$ divise leur différence $a-b$. Cette définition est la base du calcul en congruence modulo $n$.

Explication

L’algorithme d’Euclide étendu calcule le PGCD et donne aussi des coefficients vérifiant l’identité de Bézout. Les autres propositions décrivent d’autres notions mathématiques, mais pas cet algorithme.