2022 Metropole Sujet 2

(4 points) Cet exercice porte sur les arbres binaires de recherche, la programmation orientée objet et la récursivité. Dans cet exercice, la taille d’un arbre est le nombre de nœuds qu’il contient. Sa hauteur est le nombre de nœuds du plus long chemin qui joint le nœud racine à l’une des feuilles (nœuds sans sous-arbres). On convient que la hauteur d’un arbre ne contenant qu’un nœud vaut 1 et la hauteur de l’arbre vide vaut 0.

(4 points) Cet exercice porte sur les structures de données. La poussette est un jeu de cartes en solitaire. Cet exercice propose une version simplifiée de ce jeu basée sur des nombres. On considère une pile constituée de nombres entiers tirés aléatoirement. Le jeu consiste à réduire la pile suivant la règle suivante : quand la pile contient du haut vers le bas un triplet dont les termes du haut et du bas sont de même parité, on supprime l'élément central. Par exemple :  Si la pile contient du haut vers le bas, le triplet 1 0 3, on supprime le 0.  Si la pile contient du haut vers le bas, le triplet 1 0 8, la pile reste inchangée. On parcourt la pile ainsi de haut en bas et on procède aux réductions. Arrivé en bas de la pile, on recommence la réduction en repartant du sommet de la pile jusqu'à ce que la pile ne soit plus réductible. Une partie est « gagnante » lorsque la pile finale est réduite à deux éléments exactement. Voici un exemple détaillé de déroulement d'une partie.

(4 points) Cet exercice porte sur les réseaux et les protocoles de routages. Rappels : Une adresse IPv4 est composée de 4 octets, soit 32 bits. Elle est notée a.b.c.d, où a, b, c et d sont les valeurs des 4 octets. La notation a.b.c.d/n signifie que les n premiers bits de l’adresse IP représentent la partie « réseau », les bits qui suivent représentent la partie « machine ». L’adresse IPv4 dont tous les bits de la partie « machine » sont à 0 est appelée « adresse du réseau ». L’adresse IPv4 dont tous les bits de la partie « machine » sont à 1 est appelée « adresse de diffusion ». On considère le réseau représenté sur la Figure 1 ci-dessous : Figure 1 : schéma du réseau

(4 points) Cet exercice porte sur les bases de données relationnelles et le langage SQL. L’énoncé de cet exercice utilise les mots clefs du langage SQL suivants : SELECT, FROM, WHERE, JOIN ON, UPDATE, SET, INSERT INTO VALUES, COUNT, ORDER BY.  La clause ORDER BY suivie d'un attribut permet de trier les résultats par ordre croissant de l'attribut ;  COUNT(*) renvoie le nombre de lignes d'une requête ; Un musicien souhaite créer une base de données relationnelle contenant ses morceaux et interprètes préférés. Pour cela il utilise le langage SQL. Il crée une table morceaux qui contient entre autres les titres des morceaux et leur année de sortie : id_morceau titre annee id_interprete 1 Like a Rolling Stone 1965 1 2 Respect 1967 2 3 Imagine 1970 3 4 Hey Jude 1968 4 5 Smells Like Teen Spirit 1991 5 6 I Want To hold Your Hand 1963 4 Il crée la table interpretes qui contient les interprètes et leur pays d'origine : id_interprete nom pays 1 Bob Dylan États-Unis 2 Aretha Franklin États-Unis 3 John Lennon Angleterre 4 The Beatles Angleterre 5 Nirvana États-Unis id_morceau de la table morceaux et id_interprete de la table interpretes sont des clés primaires. L’attribut id_interprete de la table morceaux fait directement référence à la clé primaire de la table interpretes. 22-NSIJ2ME1 Page : 11/14

(4 points) Cet exercice aborde la programmation objet et la méthode diviser pour régner. Un labyrinthe est composé de cellules possédant chacune quatre murs (voir ci- dessus). La cellule en haut à gauche du labyrinthe est de coordonnées (0, 0). On définit la classe Cellule ci-dessous. Le constructeur possède un attribut murs de type dict dont les clés sont ’N’, ’E’, ’S’ et ’O’ et dont les valeurs sont des booléens (True si le mur est présent et False sinon). class Cellule: def __init__(self, murNord, murEst, murSud, murOuest): self.murs={'N':murNord,'E':murEst, 'S':murSud,'O':murOuest}