Qu'est-ce qu'une liste de taille n en Python ?
Un n-uplet numérique ordonné d'indices de 0 à n−1 et de longueur n.
Comment concatène-t-on deux listes en Python ?
Avec l'opérateur +.
Comment répète-t-on une liste en Python ?
Avec un entier multiplicateur.
Que fait la tranche L[i:j] sur une liste ?
Elle extrait les éléments d'indices i inclus à j exclu.
Quelles opérations courantes peut-on faire sur une liste ?
len, del, in, sort, reverse, min, max, insert, remove et count.
Qu'est-ce qu'une pile en programmation ?
Une liste où pop retire le dernier élément et append ajoute à la fin.
Qu'est-ce qu'un dictionnaire en Python ?
Une structure associant des valeurs à des clés.
Quelles clés ne peuvent pas être utilisées dans un dictionnaire ?
Les listes ne peuvent pas être des clés.
Que font les méthodes keys(), values() et items() d'un dictionnaire ?
Elles extraient respectivement clés, valeurs et couples clé-valeur.
Que permet une deque en Python ?
D'ajouter et retirer des éléments à gauche avec appendleft et popleft.
Comment importe-t-on une deque en Python ?
Depuis le module collections.
Combien de graines contient chaque trou au départ de l’awalé ?
Chaque trou contient 4 graines au départ.
Combien de graines y a-t-il en tout au départ sur le plateau d’awalé ?
Il y a 48 graines en tout au départ.
Quand la partie d’awalé s’arrête-t-elle ?
La partie s’arrête si un joueur a au moins 25 graines en réserve ou si aucun gain n’est possible.
Que fait un coup d’awalé ?
Il consiste à semer les graines d’une case choisie dans le sens direct sans ressemer la case de départ, puis éventuellement récolter.
Qu’est-ce qu’une case ramassable à l’awalé ?
C’est une case adverse contenant exactement 2 ou 3 graines.
Quelles conditions doit remplir une case jouable à l’awalé ?
Elle doit appartenir au camp actif, être non vide et ne pas vider complètement le camp adverse.
Qu'est-ce qu'un graphe non orienté ?
Un couple (S,A) avec S sommets et A paires de sommets appelées arêtes.
Comment se définit le degré d'un sommet ?
C'est le nombre d'arêtes contenant ce sommet.
Qu'est-ce qu'un arbre en théorie des graphes ?
Un graphe connexe sans cycle.
Un arbre peut-il être organisé autour d'une racine ?
Oui, il peut être organisé autour d'une racine.
Un arbre peut-il avoir des étiquettes aux nœuds ?
Oui, il peut être muni d’étiquettes aux nœuds.
Que signifie l'ordre d'un graphe ?
Le nombre de sommets du graphe.
Quel est le nombre maximal d'arêtes dans un graphe d'ordre n ?
Le nombre de paires de sommets parmi n, soit .
Qu'est-ce que la matrice d’adjacence d’un graphe à n sommets ?
Une matrice carrée où chaque coefficient aij indique le nombre d’arêtes entre i et j.
Que contient le coefficient de la matrice d’adjacence dans un graphe pondéré ?
La pondération de l’arête entre les deux sommets.
Que représente une liste d’adjacence pour un graphe ?
La liste des sommets adjacents à chaque sommet.
Que représente le coefficient à la ligne i et colonne j de la matrice ?
Le nombre de chemins de longueur k reliant i à j.
Comment fonctionne le parcours en profondeur dans un graphe ?
Il explore un voisin puis poursuit aussi loin que possible avant de revenir.
Que fait le parcours en largeur après avoir exploré les voisins du sommet initial ?
Il explore les voisins des voisins en évitant les sommets déjà visités.
Quelle structure utilise un parcours de graphe pour éviter de visiter plusieurs fois un sommet ?
Un dictionnaire ou une structure de marquage.
Quel est l'objectif de l'algorithme de Dijkstra ?
Chercher les plus courts chemins depuis le sommet 0 dans un graphe pondéré.
Comment Dijkstra initialise-t-il les distances au début ?
La distance du sommet de départ est 0, les autres sont à l'infini.
Quel sommet Dijkstra sélectionne-t-il à chaque étape ?
Le sommet non exploité de distance minimale.
Que compare Dijkstra pour chaque voisin X de distance connue ?
La distance actuelle de Y avec la somme de la distance de X et du poids de l’arête X-Y.
Que conserve Dijkstra après la comparaison des distances pour un voisin ?
La plus petite distance entre la distance actuelle et la nouvelle somme calculée.
Quel est le plus court chemin de A vers E dans l'exemple ?
Le chemin ABE.
Quelle est la longueur du plus court chemin de A vers E dans l'exemple ?
La longueur est 5.
Qu'est-ce qu'une fonction de hachage ?
Une application d'un ensemble de clés vers {0,…,n−1}.
Quand se produit une collision en hachage ?
Quand deux clés distinctes ont la même valeur de hachage.
Quelle formule donne un exemple de hachage pour une clé entière x ?
.
Comment place-t-on une clé dans un dictionnaire haché ?
On place la valeur dans la case d'indice donné par la fonction de hachage.
Comment le chaînage gère-t-il les collisions ?
En stockant plusieurs valeurs dans une même case sous forme de liste.
Quelle plage de valeurs renvoie __hash__() en Python ?
Un entier signé sur 64 bits entre −2^63 et 2^63 − 1.
Comment calcule-t-on l'indice d'une clé dans une table de hachage Python ?
On utilise la valeur de hachage de la clé modulo la taille de la table.
Que fait-on avec les valeurs partageant un même indice dans une table de hachage ?
On les regroupe ensemble.
Comment fonctionne la recherche dichotomique dans une liste triée ?
Elle compare la clé à l'élément central et élimine la moitié incompatible à chaque étape.
Quelle est la complexité de la recherche dichotomique dans une liste triée ?
Elle est en O(log n).
Quelle hypothèse est faite pour que la recherche dichotomique soit en O(log n) ?
Que le calcul de la fonction d’ordre est en O(1).
Quel avantage apporte le tri dans la recherche d'une clé ?
Il facilite la recherche d'une clé.
Pourquoi l'insertion dans une liste triée peut-elle être coûteuse ?
À cause du déplacement des éléments.
Teste tes connaissances avec un QCM de 26 questions sur Graphes, dictionnaires et hachage.
1. Pour une liste Python de longueur , quelles positions d’indices sont valides ?
2. Que contient l’expression Python lorsque est une liste ?
Révisez le cours complet dans la fiche de révision de Graphes, dictionnaires et hachage.
Voir la fiche →Importe ton cours et l'IA génère des flashcards en 30 secondes.
Générateur de flashcards