QCM : Graphes, dictionnaires et hachage — 26 questions

Explication

Une liste de longueur $n$ possède des indices entiers allant de 0 à $n-1$. L’indexation par des clés caractérise plutôt un dictionnaire, tandis que l’indice $n$ est hors limites.

Explication

La tranche commence à l’indice $i$ et s’arrête avant l’indice $j$. L’indice $j$ n’est donc pas inclus, contrairement à certaines bornes utilisées dans d’autres contextes.

Explication

Dans une pile, append ajoute un élément au sommet, situé à la fin de la liste, et pop retire puis retourne cet élément. Ce fonctionnement correspond au principe « dernier arrivé, premier sorti ».

Explication

Un dictionnaire associe des valeurs à des clés, qui peuvent notamment être des chaînes ou des tuples. Une liste est organisée par des indices entiers, et une liste ne peut pas servir de clé de dictionnaire.

Explication

Le plateau comporte deux rangées de six trous, et chaque trou contient quatre graines, soit $2 \times 6 \times 4 = 48$ graines. La répartition ne correspond donc ni à 24 graines ni à six trous.

Explication

La partie s’arrête lorsqu’un joueur possède au moins 25 graines dans sa réserve ou lorsqu’une situation empêche tout nouveau gain. Le seuil de 24 graines ne constitue pas la majorité annoncée.

Explication

Le joueur prend les graines d’une case non vide de son camp et les sème une par une dans le sens direct, sans ressemer dans la case de départ, avant une éventuelle récolte. La récolte intervient après la semence et retire des graines vers la réserve.

Explication

Une case jouable appartient au camp actif, n’est pas vide et ne doit pas vider complètement le camp adverse à la fin du tour. Les conditions « 2 ou 3 graines » concernent une case ramassable adverse, pas toute case jouable.

Explication

Un graphe non orienté est constitué d’un ensemble de sommets et d’un ensemble d’arêtes, chaque arête étant une paire de sommets. Contrairement à un graphe orienté, il ne distingue pas un sens entre les deux extrémités d’une arête.

Explication

Le degré d’un sommet correspond au nombre d’arêtes qui le contiennent, c’est-à-dire aux arêtes incidentes à ce sommet. Le nombre de chemins accessibles mesure une autre propriété du graphe et ne définit pas le degré.

Explication

Un arbre est un graphe connexe qui ne contient aucun cycle ; il peut aussi être organisé autour d’une racine et comporter des étiquettes. L’orientation, la pondération ou la représentation matricielle ne sont pas les critères définitoires d’un arbre.

Explication

Le coefficient correspondant à la ligne i et à la colonne j indique le nombre d’arêtes reliant les sommets i et j. Il ne donne pas directement la longueur d’un chemin ni la somme de leurs degrés.

Explication

Une liste d’adjacence associe chaque sommet à la liste de ses voisins. Une matrice d’adjacence réserve au contraire une case à chaque couple de sommets.

Explication

Le coefficient de $A^k$ en ligne i et colonne j donne le nombre de chemins de longueur k reliant i à j. Une arête directe correspond plutôt à une information de la matrice $A$ elle-même, sans puissance générale.

Explication

Le parcours en profondeur descend le long d’un voisin aussi loin que possible, puis revient vers un sommet précédent lorsqu’il ne peut plus avancer. Le parcours en largeur, lui, traite d’abord les voisins immédiats du sommet courant ou initial.

Explication

Le parcours en largeur explore d’abord les voisins du sommet initial, puis les niveaux suivants, en évitant les sommets déjà rencontrés. L’exploration d’un voisin aussi loin que possible correspond au parcours en profondeur.

Explication

Dijkstra détermine les plus courts chemins partant du sommet 0 dans un graphe pondéré, orienté ou non orienté. Il ne se limite donc pas à l’analyse des voisinages immédiats ni à la construction d’un cycle.

Explication

L’algorithme connaît initialement une distance nulle pour le sommet de départ et considère les autres distances comme infinies. Il sélectionne ensuite le sommet non exploité dont la distance estimée est minimale.

Explication

Dijkstra compare la distance déjà connue pour Y avec le trajet passant par X, calculé en additionnant la distance de X et le poids de l’arête X-Y. La plus petite de ces deux valeurs est conservée.

Explication

Une fonction de hachage associe une clé de l’ensemble E à un entier compris entre 0 et n − 1, afin de déterminer une position. Elle ne sert pas à établir un ordre entre les clés.

Explication

Il y a collision lorsque deux clés différentes sont envoyées vers la même valeur de hachage. Une valeur négative ou une case vide ne constitue pas, en elle-même, une collision.

Explication

Le reste de la division de x par n, noté $x\bmod n$, fournit un indice compris entre 0 et n − 1. Les autres opérations ne garantissent pas cet ensemble d’indices.

Explication

Le chaînage conserve plusieurs valeurs dans une même case, souvent au moyen d’une liste. Le stockage direct peut au contraire écraser la valeur qui s’y trouvait lors d’une collision.

Explication

En Python, __hash__() renvoie un entier signé sur 64 bits, dans l’intervalle allant de $-2^{63}$ à $2^{63}-1$. Cette valeur n’est pas directement une liste de collisions ni nécessairement un indice final de table.

Explication

La recherche dichotomique examine l’élément central et élimine la moitié de la liste qui ne peut pas contenir la clé. Elle évite ainsi le parcours séquentiel de toutes les positions.

Explication

Chaque étape de la recherche dichotomique divise approximativement par deux le nombre de positions candidates, ce qui conduit à une complexité logarithmique. L’insertion dans une liste triée peut toutefois rester linéaire à cause du déplacement des éléments.