2022 Metropole Sujet 1

(4 points) Cet exercice composé de deux parties A et B, porte sur les structures de données. Partie A : Expression correctement parenthésée On veut déterminer si une expression arithmétique est correctement parenthésée. Pour chaque parenthèse fermante ")" correspond une parenthèse précédemment ouverte "(". Exemples : - L’expression arithmétique "(2 + 3) × (18/(4 + 2))" est correctement parenthésée. - L’expression arithmétique "(2 + 3) × (18/(4 + 2" est non correctement parenthésée. Pour simplifier les expressions arithmétiques, on enregistre, dans une structure de données, uniquement les parenthèses dans leur ordre d’apparition. On appelle expression simplifiée cette structure. "(2 + 3) × (18/(4 + 2))" Expression arithmétique Structure de données

(4 points) Cet exercice porte sur les bases de données. On pourra utiliser les mots clés SQL suivants : SELECT, FROM, WHERE, JOIN, ON, INSERT, INTO, VALUES, UPDATE, SET, AND. Nous allons étudier une base de données traitant du cinéma dont voici le schéma relationnel qui comporte 3 relations : - la relation individu (id_ind, nom, prenom, naissance) - la relation realisation (id_rea, titre, annee, type) - la relation emploi (id_emp, description, #id_ind, #id_rea) Les clés primaires sont soulignées et les clés étrangères sont précédées d’un #. Ainsi emploi.id_ind est une clé étrangère faisant référence à individu.id_ind. Voici un extrait des tables individu et realisation :

(4 points) Cet exercice porte sur les représentations binaires et les protocoles de routage.

(4 points) Cet exercice, composé de deux parties A et B, porte sur le parcours des arbres binaires, le principe “diviser pour régner” et la récursivité. Cet exercice traite du calcul de la somme d’un arbre binaire. Cette somme consiste à additionner toutes les valeurs numériques contenues dans les nœuds de l’arbre. L’arbre utilisé dans les parties A et B est le suivant : Partie A : Parcours d’un arbre

(4 points) Cet exercice porte sur la Programmation Orientée Objet. Les participants à un jeu de LaserGame sont répartis en équipes et s’affrontent dans ce jeu de tir, revêtus d’une veste à capteurs et munis d’une arme factice émettant des infrarouges. Les ordinateurs embarqués dans ces vestes utilisent la programmation orientée objet pour modéliser les joueurs. La classe Joueur est définie comme suit : 1 class Joueur: 2 def __init__(self, pseudo, identifiant, equipe): 3 ’’’ constructeur ’’’ 4 self.pseudo = pseudo 5 self.equipe = equipe 6 self.id = identifiant 7 self.nb_de_tirs_emis = 0 8 self.liste_id_tirs_recus = [] 9 self.est_actif = True 10 def tire(self): 11 ’’’méthode déclenchée par l'appui sur la gachette’’’ 12 if self.est_actif == True: 13 self.nb_de_tirs_emis = self.nb_de_tirs_emis + 1 14 def est_determine(self): 15 ’’’methode qui renvoie True si le joueur réalise un 16 grand nombre de tirs’’’ 17 return self.nb_de_tirs_emis > 500 18 def subit_un_tir(self, id_recu): 19 ’’’méthode déclenchée par les capteurs de la 20 veste’’’ 21 if self.est_actif == True: 22 self.est_actif = False 23 self.liste_id_tirs_recus.append(id_recu)